18.09.2017 16:29
FasT93 26 7000 Источник
Привет, Хабр!

Свой первый пост я решил посвятить квантовой информатике и ее приложению к теории игр. Эта идея абсолютна не нова и своими корнями уходит в статью Жиля Брассарда 1999 года [1]. Квантовая механика сама по себе удивительная вещь, а возможность ее использования в играх вдвойне удивляет!


«Если квантовая механика вас не потрясла до глубины души, значит, вы ее еще не поняли.» (Нильс Бор)
В этом посте речь пойдет о самой примитивной игре — подбрасывании монетки. Хотя вернее будет сказать переворачивании монетки. Суть игры в следующем:

Описание игры


Есть два игрока (назовем их Алиса и Боб), монетка и ящик. Перед началом игры кладем монетку в ящик орлом вверх. Алисе и Бобу завязывают глаза и начинается игра: первый ход за Алисой, второй — Боба, а третий ход снова Алисы. Каждый из игроков в свой ход может перевернуть монетку, либо оставить ее в прежнем состоянии (напоминаю, что игроки не видят какой стороной вверх лежит монетка). Если по окончанию третьего хода монетка лежит орлом вверх, то побеждает Алиса, если решкой — Боб.

Классический вариант


Данная игра совсем простенькая, поэтому тут легко рассмотреть все варианты развития событий. Перебирать все исходы удобно в виде таблицы (подобная таблица в теории игр называется матрицей выигрышей).


Буквы «П» и «Н» соответствуют действиям игрока: перевернуть монетку и ничего не делать. В каждой ячейке таблицы указано имя победителя. Отсюда сразу видно, что вероятность выигрыша Алисы равна $inline$\frac{1}{2}$inline$. К каким бы стратегиям не прибегали игроки, вероятность выигрыша каждого из них остается постоянной. И все бы хорошо, но Алиса оказалась очень азартным игроком: ей хочется выигрывать чаще чем в половине случаев! И квантовая механика способна помочь ей в этом!

Для дальнейшего чтения желательно быть знакомым с основами квантовой механики и кубитологии. Товарищ devpony опубликовал пост в котором на качественном уровне все это объяснено. Так же можно почитать соответствующую литературу [2].

Квантовый вариант


Давайте теперь представим, что у нас есть все тот же ящик, но внутри него лежит «квантовая монетка». В качестве этой монетки может выступать любая двухуровневая квантовая система (кубит): электрон со спином вверх/вниз, фотон с поляризацией по и против часовой стрелки или сверхпроводниковый кубит, состояние которого определяется направлением протекания тока. Вариантов огромное множество. Но мы будем работать с абстрактной моделью кубита, не зависящей от физической реализации. И тут играет крайне важную роль тот факт, что игроки не видят монетку. Наблюдение за состоянием монетки соответствует процедуре измерения, что убивает всю соль — возможность монетки находиться в состоянии суперпозиции орла и решки.

Введем два состояния для случаев «монета орлом вверх» и «монета решкой вверх»:


Теперь нужно определить квантовые операции, соответствующие классическим действиям игроков. Ну, тут все просто: переворачиванию монетки соответствует квантовый гейт NOT


который переводит состояние $inline$|орел\rangle$inline$ в $inline$|решка\rangle$inline$ и наоборот. А действие «ничего не делать» соответствует тождественному преобразованию


Будем считать, что Алиса внимательно слушала курс квантовой механики в институте и знает, что кроме этих двух преобразований (аналогичных классическим действиям), над кубитом можно выполнить любое преобразование, которое описывается унитарной матрицей. А Боб был тунеядцем, и считает, что квантовая механика ничем не отличается от классической, и над ней можно выполнять только две вышеупомянутые операции.

Алиса выбирает вентиль Адамара. Данный вентиль важен тем, что с его помощью можно создать суперпозицию состояний

На наши «монетные» состояние он действует следующим образом:

Последние обозначения введены для удобства дальнейшего использования.

Боб же с некоторой вероятностью (неизвестной для Алисы) выполняет одно из действий: $inline$X$inline$ или $inline$I$inline$. К сожалению подобное преобразование нельзя описать унитарной матрицей. Но теория открытых квантовых систем говорит нам, что подобное преобразование можно описать с помощью так называемых операторов Крауса [3]. Для дальнейшего рассмотрения нам потребуется представить наше состояние в виде матрицы плотности. Это более общая форма представления квантовых состояний, которая имеет очень широкое применение (подробнее почитать можно здесь [4]). Однако сейчас нам достаточно самого простого определения: если есть исходное состояние $inline$|\psi\rangle$inline$, то соответствующая ему матрица плотности будет задаваться как $inline$\rho=|\psi\rangle\langle\psi|$inline$. Это матрица размерности два с единичным следом и действительными неотрицательными собственными значениями (можете попробовать доказать эти два факта). Унитарная эволюция в терминах матриц плотности задается следующим образом


Если же квантовое преобразование представлено операторами Крауса, то формула немного изменяется


где $inline$E_k$inline$ — операторы Крауса, удовлетворяющие условию разложения единицы

Легко видеть, что унитарная эволюция является частным случаем эволюции в терминах операторов Крауса (когда имеется всего одна компонента в сумме).

Возвращаемся к Бобу. Он с вероятностью $inline$p$inline$ переворачивает монетку, и соответственно, с вероятностью $inline$1-p$inline$ не изменяет ее состояние. Это действие описывается двумя операторами Крауса:


Взятие корня обусловлено необходимостью удовлетворить условию разложения единицы о котором шла речь выше.

Теперь у нас есть все необходимые инструменты для детального анализа этой игры. Давайте же наконец-то поиграем вместе с Алисой и Бобом!

  • Ход 0) Монетка находится в ящике в состоянии $inline$|орел\rangle$inline$, соответствующая матрица плотности есть $inline$\rho_0=|орел\rangle\langleорел|$inline$.
  • Ход 1) Первой ходит Алиса: она применяет преобразование Адмара
  • Ход 2) Теперь очередь Боба, он с вероятностью $inline$p$inline$ переворачивает монетку

    Отдельно рассмотрим действие гейта NOT на состояние суперпозиции: $inline$X|+\rangle=\frac{1}{\sqrt{2}}(X|орел\rangle+X|решка\rangle)=\frac{1}{\sqrt{2}}(|решка\rangle+|орел\rangle)=|+\rangle$inline$. Оказывается, оно его не изменяет, следовательно:

    мы получили состояние, такое же, как после хода Алисы, то есть, ход Боба вообще ни на что не влияет! Именно этот факт позволяет Алисе выиграть в игре.
  • Ход 3) Победный ход Алисы: применение оператора Адамара


По окончанию всех ходов монетка будет находиться в состоянии $inline$|орел\rangle$inline$ с вероятностью 1. Используя данный метод Алиса может побеждать во всех играх (до тех пор пока ей не встретится соперник, который также знает квантовую механику).

Литература


[1] G. Brassard, R. Cleve, A. Tapp «The cost of exactly simulating quantum entanglement with classical communication», 1999, arxiv.org/pdf/quant-ph/9901035.pdf.
[2] Дж. Прескилл «Квантовая информация и квантовые вычисления», 2008.
[3] Х.-П. Бройер, Ф. Петруччионе «Теория открытых квантовых систем», 2010.
[4] Нильсен М., Чанг И. «Квантовые вычисления и квантовая информация», 2006.

Комментарии (26)


  1. Sdima1357
    18.09.2017 19:42
    #10422328
    +3

    Где то посередине нить потерял. В конце испугался за Алису после применения оператора Адамара, как бы она не сыграла в ящик, но статья понравилась, спасибо.


    1. robert_ayrapetyan
      18.09.2017 22:32
      #10422654
      +1

      Разве абзац «Квантовый вариант» начинается с середины? Вроде чуть выше.


      1. Sdima1357
        18.09.2017 22:46
        #10422668

        Вентиль Адамара точно посередине. Я понял что Алиса жульничает, но не понял где-, не буду с ней играть


        1. FasT93 Автор
          18.09.2017 23:37
          #10422730
          +1

          Да пока и не получится, реализаций подобных алгоритмов нет в эксперименте. Нужна надежная квантовая память для хранения квантового состояния, а с этим пока неувязки.


        1. Hardcoin
          19.09.2017 17:42
          #10425070
          +1

          Она ставит монетку на ребро лицом к Бобу. Боб потом поворачивает её на 180 градусов (или не поворачивает), по сути крутит вокруг центра, а Алиса потом кладет обратно. Бобу же запрещено смотреть состояние монетки.


      1. FasT93 Автор
        18.09.2017 23:35
        #10422726
        +1

        Ну перед абзацем просто некое предупреждение, чтобы не шокировать сразу


    1. FasT93 Автор
      18.09.2017 23:34
      #10422724
      +1

      Да не, с ней всё в порядке, она же специалист в квантовой теории передачи информации. Рад что понравилось.


  1. Siddthartha
    18.09.2017 20:49
    #10422476
    +2

    не было бы нагляднее расписать произведение матриц? и где же вентиль для вечной решки?)


    1. FasT93 Автор
      18.09.2017 23:39
      #10422736
      +1

      Это довольно громоздко, но я специально привел матричный вид операторов и состояний, чтобы любой желающий мог убедиться в честности вычислений.


  1. Quiensabe
    18.09.2017 21:34
    #10422574
    +4

    Как я понял статью: Алиса «наполовину» перевернула монетку, так что та стала, как бы, «ни то, ни сё». Соответственно Боб, как бы ее не крутил — все равно осталось «ни то, ни сё». Ну а третьим ходом, Алиса вновь положила монетку как надо и выиграла…

    Правда, понимания квантовой механики мне это не прибавило, но любопытно «как оно там интересно устроено, однако» :)


    1. FasT93 Автор
      18.09.2017 23:41
      #10422738
      +1

      Да, что-то в этом роде. Согласен, меня тоже очень удивляют подобные применения квантовой механики — такие, более наглядные и прикладные чтоли.


    1. alexeykuzmin0
      19.09.2017 15:29
      #10424490
      +2

      Думаю, в виде матриц было бы понятнее.
      1. До хода Алисы монетка была в состоянии (1, 0), т.е. орел с вероятностью 1.
      2. Алиса умножает монетку на матрицу Адамара (см тут, не умею я матрицы в комментарии вставлять), получается состояние (1/v2, 1/v2), т.е. орел или решка с вероятностями 1/2.
      3. Боб может оставить все как есть (умножение на единичную матрицу), а может перевернуть монетку (поменяв местами вероятности), т.е. его ход ничего не меняет, что бы он ни выбрал.
      4. Алиса применяет преобразование Адамара еще раз, получая состояние (1, 0) — т.е. с вероятностью 1 орел. Победа!


      1. FasT93 Автор
        19.09.2017 17:14
        #10424974

        Матрицы это хорошо=) Ну тут дело вкуса, мне привычнее работать со скобками Дирака, так как если у нас в задаче более одного кубита, то проще записать a|01010101>+b|10111110> чем вектор размерности 256… не говоря уж про запись гейтов


        1. alexeykuzmin0
          19.09.2017 17:16
          #10424986

          Мне тоже в большинстве случаев удобнее работать со скобками Дирака, но здесь, мне кажется, неподготовленному читателю так понятнее.


          1. FasT93 Автор
            19.09.2017 17:30
            #10425022

            Учту в дальнейшем, спасибо!


  1. koldyr
    18.09.2017 21:56
    #10422600

    Если я правильно понял, в начале игры Алиса не знает значение кубита. Так что описанный фокус ей ничего не дает.


    1. Vkuvaev
      18.09.2017 23:15
      #10422708
      +3

      Да нет, написано: «Перед началом игры кладем монету орлом вверх, и завязываем глаза..»


    1. FasT93 Автор
      18.09.2017 23:38
      #10422734

      Изначально монетка лежит лицом вверх, но после применения оператора Н она переходит в состояние суперпозиции и с этого момента за ней наблюдать нельзя вплоть до конца игры.


  1. kirmorozov
    19.09.2017 02:25
    #10422868
    +1

    Отличная история о том как применять теорию на практике :).
    Между А и Б, всегда найдется A, которая не противоречит правилам игры.


  1. ChePeter
    19.09.2017 11:15
    #10423454

    Мне квантовые вычисления всегда почему то напоминают недетерминированную машину Тьюринга.
    Быстро находит решение сложных задач, но никто не знает как.


    1. FasT93 Автор
      19.09.2017 11:19
      #10423466
      +1

      Скорее «Квантовую машину Тьюринга», чем по сути они и являются.
      Я бы сказал так: быстро находит решение сложных задач, многие понимают как и никто не может адекватно реализовать:)


      1. ChePeter
        21.09.2017 10:38
        #10429326

        Не вижу различий.
        Детализация принятия решения головкой машины абсолютно неважна, квантовая она или еще какая цветная.
        Главное, что есть правильный ход и она его может сделать.


  1. PapaBubaDiop
    19.09.2017 13:46
    #10423994
    +4

    Рискну привести геометрическую аналогию. Есть обычный шестигранный кубик, две противоположные стороны которого помечены «чет» и «нечет». Остальные грани пустые. Наверху изначально либо «чет», либо «нечет».
    Алиса и Боб крутят по очереди кубик на 180 градусов вокруг оси X. Это описывается матрицей поворота, как в статье. После таких трансформаций наверху либо «чет», либо «нечет».

    И тут Алиса начинает адамарить. То есть первым ходом поворачивает кубик набок (вокруг оси Z). Теперь наверху пустая грань (состояние неопределенности), а Боб, как честный, крутит кубик по прежним правилам — в результате наверху всегда любая из четырех пустых граней (Боб даже может вполоборота крутить). «Чет» остается там куда его Алиса положила. Ну и вернуть кубик в нужное состояние Алисе не сложно.

    И тут


    1. FasT93 Автор
      19.09.2017 15:57
      #10424620
      +1

      Ваша аналогия абсолютно верная но очень упрощенная. Геометрическая интерпретация по сути здесь такая: Алиса и боб могут поворачивать вектор в гильбертовом пространстве размерности 2 (один кубит — вектор столбец размерности 2 с комплексными числами). Подобные однокубитные вращения очень наглядно описываются на сфере Блоха (https://en.wikipedia.org/wiki/Bloch_sphere). Здесь также вращения задаются матрицами поворота. Боб может крутить переводя вектор кубита из одного полюса в другой (поворот вокруг оси X). А Алиса в свой ход переводит его в плоскость ХY (точнее даже — точно на ось X). Теперь Боб может крутить как угодно вокруг оси Х… вектор кубита все равно останется в том же положении. И далее Алиса возвращает его на место просто.


      1. alexeykuzmin0
        19.09.2017 16:05
        #10424654
        +2

        По сути, это то же самое. Только уважаемый PapaBubaDiop сферу Блоха на куб спроецировал.


        1. FasT93 Автор
          19.09.2017 16:13
          #10424694

          Да, аналогия очень хорошая и наглядная, я лишь указал на то, что это аналогия далеко не во всех подобных задачах будет работать.