Играем с квантовой монеткой

Привет, Хабр!

Свой первый пост я решил посвятить квантовой информатике и ее приложению к теории игр. Эта идея абсолютна не нова и своими корнями уходит в статью Жиля Брассарда 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.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 26
  • +3
    Где то посередине нить потерял. В конце испугался за Алису после применения оператора Адамара, как бы она не сыграла в ящик, но статья понравилась, спасибо.
    • +1
      Разве абзац «Квантовый вариант» начинается с середины? Вроде чуть выше.
      • 0
        Вентиль Адамара точно посередине. Я понял что Алиса жульничает, но не понял где-, не буду с ней играть
        • +1
          Да пока и не получится, реализаций подобных алгоритмов нет в эксперименте. Нужна надежная квантовая память для хранения квантового состояния, а с этим пока неувязки.
          • +1

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

          • +1
            Ну перед абзацем просто некое предупреждение, чтобы не шокировать сразу
          • +1
            Да не, с ней всё в порядке, она же специалист в квантовой теории передачи информации. Рад что понравилось.
          • +2

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

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

              Правда, понимания квантовой механики мне это не прибавило, но любопытно «как оно там интересно устроено, однако» :)
              • +1
                Да, что-то в этом роде. Согласен, меня тоже очень удивляют подобные применения квантовой механики — такие, более наглядные и прикладные чтоли.
                • +2
                  Думаю, в виде матриц было бы понятнее.
                  1. До хода Алисы монетка была в состоянии (1, 0), т.е. орел с вероятностью 1.
                  2. Алиса умножает монетку на матрицу Адамара (см тут, не умею я матрицы в комментарии вставлять), получается состояние (1/√2, 1/√2), т.е. орел или решка с вероятностями 1/2.
                  3. Боб может оставить все как есть (умножение на единичную матрицу), а может перевернуть монетку (поменяв местами вероятности), т.е. его ход ничего не меняет, что бы он ни выбрал.
                  4. Алиса применяет преобразование Адамара еще раз, получая состояние (1, 0) — т.е. с вероятностью 1 орел. Победа!
                  • 0
                    Матрицы это хорошо=) Ну тут дело вкуса, мне привычнее работать со скобками Дирака, так как если у нас в задаче более одного кубита, то проще записать a|01010101>+b|10111110> чем вектор размерности 256… не говоря уж про запись гейтов
                    • 0
                      Мне тоже в большинстве случаев удобнее работать со скобками Дирака, но здесь, мне кажется, неподготовленному читателю так понятнее.
                      • 0
                        Учту в дальнейшем, спасибо!
                • 0
                  Если я правильно понял, в начале игры Алиса не знает значение кубита. Так что описанный фокус ей ничего не дает.
                  • +3
                    Да нет, написано: «Перед началом игры кладем монету орлом вверх, и завязываем глаза..»
                    • 0
                      Изначально монетка лежит лицом вверх, но после применения оператора Н она переходит в состояние суперпозиции и с этого момента за ней наблюдать нельзя вплоть до конца игры.
                    • +1
                      Отличная история о том как применять теорию на практике :).
                      Между А и Б, всегда найдется Ä, которая не противоречит правилам игры.
                      • 0
                        Мне квантовые вычисления всегда почему то напоминают недетерминированную машину Тьюринга.
                        Быстро находит решение сложных задач, но никто не знает как.
                        • +1
                          Скорее «Квантовую машину Тьюринга», чем по сути они и являются.
                          Я бы сказал так: быстро находит решение сложных задач, многие понимают как и никто не может адекватно реализовать:)
                          • 0
                            Не вижу различий.
                            Детализация принятия решения головкой машины абсолютно неважна, квантовая она или еще какая цветная.
                            Главное, что есть правильный ход и она его может сделать.
                        • +4
                          Рискну привести геометрическую аналогию. Есть обычный шестигранный кубик, две противоположные стороны которого помечены «чет» и «нечет». Остальные грани пустые. Наверху изначально либо «чет», либо «нечет».
                          Алиса и Боб крутят по очереди кубик на 180 градусов вокруг оси X. Это описывается матрицей поворота, как в статье. После таких трансформаций наверху либо «чет», либо «нечет».

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

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

                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.