Искусство побеждать или что такое квантовая псевдотелепатия05.04.2018 11:48

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

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

_nv9pqp48jeyyr3rw7lzmn0-8ko.png

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

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


Для полного понимания материала необходимо знание базовых терминов квантовой информатики: кубиты, измерение кубитов и запутанность. Про все это можно почитать в [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}$» />. Следовательно, используя квантовую стратегию, Алиса и Боб увеличивают свои шансы на победу.</p> <h2>Выводы</h2> <p><br /> Учите кванты и побеждайте! </p> <p>Литература<br /> [1] <i>В.-Х. Стиб, Й. Харди</i> Задачи и их решения в квантовых вычислениях и квантовой теории информации, Изд. Регулярная и хаотическая динамика, 2007.<br /> [2] <i>Gilles Brassard, Anne Broadbent, Alain Tapp</i> Quantum Pseudo-telepathy, Foundations of Physics, Vol. 35, Issue 11, 2005.</p> <p class=© Habrahabr.ru