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

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

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

В этом посте речь пойдет о самой примитивной игре — подбрасывании монетки. Хотя вернее будет сказать переворачивании монетки. Суть игры в следующем:

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

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

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

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


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

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

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

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

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


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


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


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

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

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

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

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


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


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

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

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


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

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

• Ход 0) Монетка находится в ящике в состоянии $\$inline\$|орел\backslash rangle\$inline\$$, соответствующая матрица плотности есть $\$inline\$\backslash rho\_0=|орел\backslash rangle\backslash langleорел|\$inline\$$.
• Ход 1) Первой ходит Алиса: она применяет преобразование Адмара
  
• Ход 2) Теперь очередь Боба, он с вероятностью $\$inline\$p\$inline\$$ переворачивает монетку
  
  
  
  Отдельно рассмотрим действие гейта NOT на состояние суперпозиции: $\$inline\$X|+\backslash rangle=\backslash frac\{1\}\{\backslash sqrt\{2\}\}(X|орел\backslash rangle+X|решка\backslash rangle)=\backslash frac\{1\}\{\backslash sqrt\{2\}\}(|решка\backslash rangle+|орел\backslash rangle)=|+\backslash rangle\$inline\$$. Оказывается, оно его не изменяет, следовательно:
  
  
  
  мы получили состояние, такое же, как после хода Алисы, то есть, ход Боба вообще ни на что не влияет! Именно этот факт позволяет Алисе выиграть в игре.
• Ход 3) Победный ход Алисы: применение оператора Адамара
  
  
  

По окончанию всех ходов монетка будет находиться в состоянии $\$inline\$|орел\backslash 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.

Original source: habrahabr.ru (comments, light).