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

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


«В мире нет ничего особенного. Никакого волшебства. Только физика.» (Чак Паланик)

Перед прочтением


Для полного понимания материала необходимо знание базовых терминов квантовой информатики: кубиты, измерение кубитов и запутанность. Про все это можно почитать в [1], там описана краткая теория и приведен набор задач по каждой теме.

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


John Clauser, Michael Horne, Abner Shimony и Richard Holt разработали альтернативный подход к неравенствам Белла и представили его в виде простой игры, назвав ее CHSH Game. Суть довольна проста. Два наших стандартных игрока (Алиса и Боб) играют по следующим правилам:

  1. Некий судья генерирует два случайных бита $x$ и $y$ (назовем их входными битами). Затем отправляет бит $x$ Алисе, а бит $y$ – Бобу.
  2. Алиса и Боб, глядя на полученные биты (каждый из игроков видит только свой бит), отвечает судье опять-таки одним битом. Введем обозначения: $a$ — выходной бит Алисы, $b$ – выходной бит Боба.
  3. Судья на основе битов Алисы и Боба выносит вердикт – победа игроков или их поражение. Условие победы выглядит следующим образом: $x \cdot y=a \oplus b$, где $x \cdot y$ — логическое «И», а $a \oplus b$ — операция «XOR».
    PS. Считаем судью честным на 100%.

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

Классическая стратегия


Сначала рассмотрим классическую стратегию игры, и какие плоды она может принести. Тут все просто: так как функция $x \cdot y$ равна нулю в 75 процентах случаев, то наиболее выгодной стратегией будет отправка судье битов $a=0$, $b=0$. Таким образом, вероятность выигрыша равна

$P_{Classic}=\frac{3}{4}$


Квантовая стратегия


Возможность применения квантовой стратегии объясняется наличием некой связи между игроками на уровне квантовомеханических явлений. Эту связь Жиль Брассард в одной из своих работ [2] назвал псевдотелепатией и предложил учитывать ее с помощью запутанных квантовых состояний, разделенных между игроками.

Так и поступим: возьмем двухкубитное запутанное состояние $|\psi_{AB}\rangle=\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$. Первый кубит из этой пары отдадим Алисе, а второй – Бобу. Далее будем разбираться, как это использовать.

После получения входных битов Алиса и Боб выбирают базис, в котором они будут измерять свои половинки запутанного состояния. Обозначим этот базис как

$|\nu_0(\theta)\rangle=\cos\theta|0\rangle+\sin\theta|1\rangle \\ |\nu_1(\theta)\rangle=\sin\theta|0\rangle-\cos\theta|1\rangle$

где $\theta$ — произвольный угол. Легко убедиться, что этот базис является ортонормированным. Пусть Алиса использует для измерения угол $\alpha_0$, если получила входной бит $x=0$, и угол $\alpha_1$, если входной бит $x=1$. Аналогично Боб использует углы $\beta_0$ и $\beta_1$, если получил входной бит $y=0$ и $y=1$ соответственно. Измерение определяет выходной бит каждого из игроков. Если при измерении он получил состояние $|\nu_0(\theta)\rangle$, то он отправляет судье ноль, а если получил $|\nu_1(\theta)\rangle$, то отправляет единицу. То есть квантовая механика будет определять стратегию игры!

Переберем теперь всевозможные комбинации входных битов:

  1. $x=0$, $y=0$
    Алиса и Боб выиграют, если ответят $a=0$, $b=0$ или $a=1$, $b=1$. Вероятность выигрыша в этом случае будет

    $P(x=0,y=0)=|\langle \nu_0(\alpha_0),\nu_0(\beta_0)|\psi_{AB}\rangle|^2+|\langle \nu_1(\alpha_0),\nu_1(\beta_0)|\psi_{AB}\rangle|^2$

    Путем несложных, но довольно утомительных, вычислений получаем

    $P(x=0,y=0)=\cos^2(\alpha_0-\beta_0)$

  2. $x=0$, $y=1$
    Алиса и Боб выиграют, если ответят $a=0$, $b=0$ или $a=1$, $b=1$. Вероятность этого

    $P(x=0,y=1)=|\langle \nu_0(\alpha_0),\nu_0(\beta_1)|\psi_{AB}\rangle|^2+|\langle \nu_1(\alpha_0),\nu_1(\beta_1)|\psi_{AB}\rangle|^2=\cos^2(\alpha_0-\beta_1)$

  3. $x=1$, $y=0$
    Алиса и Боб выиграют, если ответят опять-таки $a=0$, $b=0$ или $a=1$, $b=1$. Вероятность этого

    $P(x=1,y=0)=|\langle \nu_0(\alpha_1),\nu_0(\beta_0)|\psi_{AB}\rangle|^2+|\langle \nu_1(\alpha_1),\nu_1(\beta_0)|\psi_{AB}\rangle|^2=\cos^2(\alpha_1-\beta_0)$

  4. $x=1$, $y=1$
    Алиса и Боб выиграют, если ответят $a=0$, $b=1$ или $a=1$, $b=0$. Вероятность этого

    $P(x=1,y=1)=|\langle \nu_0(\alpha_1),\nu_1(\beta_1)|\psi_{AB}\rangle|^2+|\langle \nu_1(\alpha_1),\nu_0(\beta_1)|\psi_{AB}\rangle|^2=\sin^2(\alpha_1-\beta_1)$


Так как значения входных битов равновероятны, то общая вероятность, определяющая успех при использовании квантовой стратегии, задается формулой

$P_{Quantum}=\frac{1}{4}[P(x=0,y=0)+P(x=0,y=1)+P(x=1,y=0)+P(x=1,y=1)]$

или

$P_{Quantum}=\frac{1}{4}[\cos^2(\alpha_0-\beta_0)+\cos^2(\alpha_0-\beta_1)+\cos^2(\alpha_1-\beta_0)+\sin^2(\alpha_1-\beta_1)]$

Так как мы не накладывали никаких ограничений на углы измерительных базисов, то выберем следующие значения: $\alpha_0=0$, $\alpha_1=\frac{\pi}{4}$, $\beta_0=\frac{\pi}{8}$ и $\beta_1=-\frac{\pi}{8}$. Тогда получим довольно неожиданное значение вероятности

$P_{Quantum}=\frac{1}{2}+\frac{1}{2\sqrt{2}} \approx0.854$

Ну или тот же самый результат можно получить, решив задачу оптимизации функции $P_{Quantum}$ любым подходящим способом.

Для примера, листинг минималистичной программки на языке Python, решающей эту задачу:

from scipy.optimize import minimize
from math import sin, cos, pi
f = lambda x: -(cos(x[0] - x[2])**2 + cos(x[0] - x[3])**2 + cos(x[1] - x[2])**2 + sin(x[1] - x[3])**2) / 4
res = minimize(f, [pi] * 4, method='Nelder-Mead')
print("Max value =", abs(f(res.x)))

И результат выполнения:

Max value = 0.8535533904794891

То есть мы получили, что $P_{Quantum}>P_{Classic}$. Следовательно, используя квантовую стратегию, Алиса и Боб увеличивают свои шансы на победу.

Выводы


Учите кванты и побеждайте!

Литература


[1] В.-Х. Стиб, Й. Харди Задачи и их решения в квантовых вычислениях и квантовой теории информации, Изд. Регулярная и хаотическая динамика, 2007.
[2] Gilles Brassard, Anne Broadbent, Alain Tapp Quantum Pseudo-telepathy, Foundations of Physics, Vol. 35, Issue 11, 2005.