Й. Айсерт и М. Уилкенс
(Jens Eisert and Martin Wilkens) ${ }^{1}$
М. Левенштайн
(Maciej Lewenstein) $^{2}$
Мы предлагаем распространить классическую теорию игр на квантовую территорию. Д.тя частного случая Дилеммы Заключенного показано, что эта игра перестает быть дилеммой, если в ней разрешены квантовые стратегии. Также построена конкретная квантовая стратегия, которая всегда обеспечивает преимущество при игре против любой классической стратегии. Обсуждаются возможные приложения для квантовой теории информации.

Возможно, тот факт, что физика и игры могут иметь что-либо общее, вызовет удивление. В конце концов, считается, что такие игры, как шахматы или покер, основаны на блефе, догадках и других действиях нефизического характера. Более того, как было показано фон Нейманом и Моргенштерном [1], разумный выбор не является существенным для теории игр. На более абстрактном уровне, теория игр занимается величинами, которые могут быть максимизированы или минимизированы в результате некоторых действий [2]. Поэтому для специалиста по квантовой теории естественно задаться вопросом, что произойдет, если будут разрешены линейные суперпозиции таких действий, т. е. если распространить игры на квантовую территорию.

Имеются несколько причин, по которым квантовые игры могут быть интересны. Во-первых, классическая теория игр является хорошо развитой отраслью прикладной математики [3], нашедшей многочисленные приложения в экономике, психологии, экологии и биологии $[2,3,4,5,6]$. То, что она в большой мере основана на вероятности,
${ }^{1}$ Institut für Physik, Universität Potsdam, 14469 Potsdam, Germany.
${ }^{2}$ Institut für Theoretische Physik, Universität Hannover, 30167 Hannover, Germany. Перевод И. о. Чередникова.
Таблица 3. Матрица выигрыша для Дилеммы Заключенного. Первое число в скобках обозначает выигрыш Алисы, а второе – Боба. Численные значения выбраны по [5]. С учетом ур. (3) этот выбор соответствует $r=3$ («награда»), $p=1$ («наказание»), $t=5$ («искушение»), и $s=0$ («выигрыи простака»).

обусловливает фундаментальный интерес к обобщению этой теории на область квантовых вероятностей [7]. Во-вторых, если «эгоистичные гены» («Selfish Genes») [6] — реальность, то можно предположить, что игры выживания $[5,6]$ разыгрываются уже на молекулярном уровне, где правила диктует квантовая механика. В-третьих, недавно обнаружилось, что подслушивание при передаче информации по квантовому каналу $[8,9,10]$ и оптимальное размножение [11] могут быть просто представлены как стратегические игры между двумя или более игроками, с целью получить как можно больше информации при заданных условиях [12]. Наконец, было показано, что в квантовых вычислениях некоторые задачи, не поддающиеся обработке согласно классической теории сложности, становятся разрешимыми при использовании квантовых алгоритмов [13]. В квантовой теории игр делается предположение о том, что существуют квантовые стратегии, более эффективные по сравнению с чисто классическими [7]. В данной работе будет показано, что это действительно так.

Рассмотрим для определенности квантовую теорию бинарных игр с выбором для двух игроков. Одним из элементов этого класса, нашедшего широкое применение во многих областях науки, является Дилемма Заключенного. В Дилемме Заключенного каждый из двух игроков, Алиса и Боб, должен независимо решить, следует ли ему или ей предать другого (стратегия $D$ ), или действовать с ним заодно (сотрудничать) (стратегия $C$ ). В зависимости от принятых решений, каждый игрок получает некий выигрыш – см. табл. 1. Целью каждого игрока является максимизация своего индивидуального выигрыша. Ловушкой в данной дилемме становится то, что $D$-доминантная стратегия, т. е. рациональные аргументы подталкивают каждого к предательству, что существенно ухудшает ситуацию по сравнению с той, когда оба решили бы сотрудничать $[14]$. В терминах теории игр, взаимное предательство
является также равновесием Нэша [3]: при ретроспективном размышлении о варианте $D D$ каждый игрок приходит к выводу, что он или она не мог бы сделать лучший ход, односторонне меняя свою стратегию [15].

В этой статье мы покажем, что Дилемма Заключенного перестает быть дилеммой, если игрокам разрешено использовать квантовые стратегии. Более того, мы продемонстрируем, что: (i) существует определенная пара квантовых стратегий, которая всегда дает выигрыш и является равновесием Нэша, и (ii) существует определенная квантовая стратегия, которая всегда дает выигрыш при игре против любой классической стратегии.

Физически, данная бинарная игра для двух игроков с выбором легко реализуется с помощью (i) источника двух битов, один бит на каждого игрока, (ii) набора физических методов, позволяющих игроку манипулировать со своим битом в соответствие с избранной стратегией, и (iii) измеряющего прибора, определяющего выигрыш игроков, исходя из совокупного состояния двух битов. Все три составляющих (источник, физические методы игроков и прибор для измерения выигрыша) считаются полностью известными обоим игрокам.

Квантовая формулировка дополняется заданием возможных результатов классических стратегей $D$ и $C$ с помощью двух базисных векторов $|D\rangle$ и $|C\rangle$ в гильбертовом пространстве двухуровневой системы, т. е. кубитов. В каждом случае состояние игры описывается вектором в пространстве тензорного произведения с базисом классической игры $|C C\rangle,|C D\rangle,|D C\rangle$ и $|D D\rangle$, где первый и второй элементы относятся к кубитам Алисы и Боба соответственно.

Реализация квантовой игры может быть представлена как простая квантовая сеть [16] с источниками, обратимыми однобитовыми и двубитовыми гейтами и стоками (см. рис. 1). Обозначим начальное состояние игры как $\left|\psi_{0}\right\rangle$. Удобно рассматривать $\left|\psi_{0}\right\rangle$ как унитарное преобразование фиксированного вектора $|C C\rangle$,
\[
\left|\psi_{0}\right\rangle=\widehat{\mathcal{J}}|C C\rangle
\]

где $\widehat{\mathcal{J}}$ – унитарный оператор, который известен обоим игрокам. В честной игре $\widehat{\mathcal{J}}$ должен быть симметричным по отношению к перестановке игроков.

Стратегии выполняются на упорядоченной паре кубитов в состоянии $\left|\psi_{0}\right\rangle$. Стратегические ходы Алисы и Боба задаются унитарными операторами $\widehat{U}_{A}$ и $\widehat{U}_{B}$ соответственно, которые выбираются из стратегического пространства $S$. Независимость игроков обусловливает то, что $\widehat{U}_{A}$ и $\widehat{U}_{B}$ действуют исключительно на кубиты Алисы и Боба соответственно. Стратегическое пространство $S$ может, следовательно, быть отождествлено с некоторым подпространством группы унитарных $2 \times 2$ матриц.

Сделав свои ходы, приведшие к состоянию игры ( $\widehat{U}_{A} \otimes$ $\left.\otimes \widehat{U}_{B}\right) \widehat{\mathcal{J}}|C C\rangle$, Алиса и Боб направляют свои кубиты для окончательного измерения, которое определит их выигрыш. Это измерение может быть выполнено с помощью приготовления-к-измерению, соответствующего уни-
Рис. 1. Реализация квантовой игры для двух игроков. тарному оператору $\tilde{\mathcal{J}}$. Положим с условием, что это будет подтверждено в дальнейшем, $\dot{\mathcal{J}}=\widehat{\mathcal{J}}^{\dagger}$, так что конечное состояние игры перед измерением $\left|\psi_{f}\right\rangle=\left|\psi_{f}\left(\widehat{U}_{A}, \widehat{U}_{B}\right)\right\rangle$ задается как
\[
\left|\psi_{f}\right\rangle=\widehat{\mathcal{J}}^{\dagger}\left(\widehat{U}_{A} \otimes \widehat{U}_{B}\right) \widehat{\mathcal{J}}|C C\rangle .
\]

Выигрыш каждого игрока есть эрмитов оператор, который мы считаем диагональным в базисе классической игры. Для Дилеммы Заключенного оператор выигрыша Алисы имеет вид
\[
\begin{aligned}
\$_{A} & =r|C C\rangle\langle C C|+p| D D\rangle\langle D D|+ \\
& +t|D C\rangle\langle D C|+s| C D\rangle\langle C D|,
\end{aligned}
\]

а выигрыш Боба получается заменой $t \leftrightarrow s$ в двух последних элементах (численные значения см. в табл. 1). Ожидаемый выигрыш игрока $\alpha=A, B$ является квантово-механическим средним $P_{\alpha}=\left\langle\psi_{f}\left|\$_{\alpha}\right| \psi_{f}\right\rangle$ [18]. Отметим, что ожидаемый выигрыш Алисы $P_{A}$ зависит не только от ее выбора стратегии $\widehat{U}_{A}$, но таюже от выбора Боба $\widehat{U}_{B}$.

Удобно ограничить пространство стратегий 2-параметрическим множеством унитарных $2 \times 2$ матриц
\[
\widehat{U}(\theta, \phi)=\left(\begin{array}{cc}
e^{i \phi} \cos \theta / 2 & \sin \theta / 2 \\
-\sin \theta / 2 & e^{-i \phi} \cos \theta / 2
\end{array}\right),
\]
где $\theta \in[0, \pi]$ и $\phi \in[0, \pi / 2]$. Для определенности поставим в соответствие чистой стратегии «сотрудничество» оператор $\widehat{C} \equiv \widehat{U}(0,0)$,
\[
\widehat{C}=\left(\begin{array}{ll}
1 & 0 \\
0 & 1
\end{array}\right),
\]

а чистой стратегии «предательство» – переворот спина, $\widehat{D} \equiv \widehat{U}(\pi, 0)$,
\[
\widehat{D}=\left(\begin{array}{rr}
0 & 1 \\
-1 & 0
\end{array}\right) .
\]

Для классической игры представляют интерес также смешанные стратегии, когда сотрудничество выбирается с вероятностью $p$. Эти стратегии представляются $\widehat{U}(\theta, 0)$, где $p=\cos ^{2} \theta / 2$. Заметим, что все классические стратегии, чистые или смешанные, характеризуются $\phi=0$.

Чтобы гарантировать, что классическая версия данной игры представлена верно, наложим вспомогательное условие
\[
\left[\widehat{\mathcal{J}}, \widehat{U}(\theta, 0) \otimes \widehat{U}\left(\theta^{\prime}, 0\right)\right]=0
\]

для всех $\theta, \theta^{\prime} \in[0, \pi]$. Условие (7) вместе с $\tilde{\mathcal{J}}=\widehat{\mathcal{J}}^{\dagger}$ гарантирует, что любая пара классических стратегий, чистых или смешанных, дает соответствующий классический выигрыш. Например, пара $\widehat{D} \otimes \widehat{C}$ приводит игру в конечное состояние $\left|\psi_{f}\right\rangle=|D C\rangle$, что дает $P_{A}(\widehat{D}, \widehat{C})=5$ и $P_{B}(\widehat{D}, \widehat{C})=0$, в согласии с классической матрицей выигрыша (табл. 1).

После выделения абелевых подгрупп, дающих не что иное, как перепараметризацию квантового сектора пространства стратегий $S$, peшение (7) выглядит как
\[
\widehat{\mathcal{J}}=\exp \{i \gamma \widehat{D} \otimes \widehat{D}\},
\]

где $\gamma \in[0,2 \pi]$ – действительный параметр. В самом деле, $\gamma$ является мерой скрещения игры. Для $\gamma=0\left|\psi_{0}\right\rangle=|C C\rangle$, и скрещения нет. В этом случае присутствует соответствие много-в-одно по отношению к ожидаемому выигрышу между всеми возможными стратегиями и множеством классически смешанных стратегий. На рис. 2 показан ожидаемый выигрыш Алисы для $\gamma=0$. Как видно из рисунка, для любого выбора
Рис. 2. Выигрыш Алисы в игре без скрещения. На этом и следующем графиках мы выбрали такую параметризацию, что стратегии $\widehat{U}_{A}$ и $\widehat{U}_{B}$ зависят только от одного параметра $t \in[-1,1]$ : мы положили $\widehat{U}_{A}=\widehat{U}(t \pi, 0)$ для $t \in[0,1]$ и $\widehat{U}_{A}=\widehat{U}(0,-t \pi / 2)$ для $t \in[-1,0)$ (как и для Боба). Предательство $\widehat{D}$ соответствует значению $t=1$, сотрудничество $\widehat{C}-t=0$ и $\widehat{Q}$ представлется $t=-1$.
Боба $\widehat{U}_{B}$ выигрыш Алисы максимизируется, если она выбирает $\widehat{D}$. Действительно, факторизованные квантовые игры не обнаруживают никаких свойств, выводящих за пределы классической игры со смешанными стратегиями. В частности, $\widehat{D} \otimes \widehat{D}$ – равновесие доминантных стратегий.

Ситуация становится принципиально отличной, когда начальное состояние является максимально скрещенными состоянием $\left|\psi_{0}\right\rangle=$ $=(|C C\rangle+i|D D\rangle) / \sqrt{2}$, т. е. $\gamma=\pi / 2$. Здесь существуют пары стратегий, не имеющих аналогов в классической области, хотя на основании (7) игра ведет себя как полностью классическая, если оба игрока выбирают $\phi=0$. На рис. 3 показан выигрыш Алисы в Дилемме Заключенного как функция стратегий $\widehat{U}_{A}, \widehat{U}_{B}$. Если Боб выбирает $\widehat{D}$, наилучшим ответом для Алисы будет $\widehat{Q} \equiv \widehat{U}(0, \pi / 2)$,
\[
\widehat{Q}=\left(\begin{array}{cc}
i & 0 \\
0 & -i
\end{array}\right),
\]

в то время как для выбора Боба $\widehat{C}$ наилучшей стратегией Алисы будет предательство $\widehat{D}$. Таким образом, для Алисы нет доминантной стратегии. Поскольку игра симметрична, то же верно и для Боба, т. е. $\widehat{D} \otimes \widehat{D}$ не является больше равновесием в доминантных стратегиях.
Рис. 3. Выигрыш Алисы для максимального скрещения. Параметризация выбирается такая же, как и на рис. 2.

Интересно, что $\widehat{D} \otimes \widehat{D}$ перестает быть равновесием Нэша, когда оба игрока могут улучшить ситуацию путем одностороннего отклонения от стратегии $\widehat{D}$. Однако, исчезновению равновесия $\widehat{D} \otimes \widehat{D}$ сопутствует новое равновесие $\widehat{Q} \otimes \widehat{Q}$ с выигрышем $P_{A}(\widehat{Q}, \widehat{Q})=P_{B}(\widehat{Q}, \widehat{Q})=3$. В самом деле,
\[
P_{A}(\widehat{U}(\theta, \phi), \widehat{Q})=\cos ^{2} \frac{\theta}{2}\left(3 \sin ^{2} \phi+\cos ^{2} \phi\right) \leqslant 3
\]

для всех $\theta \in[0, \pi]$ и $\phi \in[0, \pi / 2]$ и аналогично $P_{B}\left(\widehat{Q}, \widehat{U}_{B}\right) \leqslant P_{B}(\widehat{Q}, \widehat{Q})$ для всех $\widehat{U}_{B} \in S$, так что никто не может выиграть от одностороннего отклонения от $\widehat{Q} \otimes \widehat{Q}$. Можно показать [19], что $\widehat{Q} \otimes \widehat{Q}$ есть единственное равновесие, т. е. рациональные доводы заставляют обоих игроков выбирать $\widehat{Q}$ как оптимальную стратегию.

Интересно отметить, что $\widehat{Q} \otimes \widehat{Q}$ должен быть оптимальным по Паpeтo [3], т. е. отклонением от этой пары стратегий невозможно повысить выигрыш одного из игроков, не понижая при этом выигрыша другого. В классической игре только взаимное сотрудничество является оптимальным по Парето, но это не равновесное решение. Можно сказать, что при допущении квантовых стратегий игрокам удается избежать дилеммы.

До сих пор мы рассматривали честные игры, когда оба игрока имеют доступ к общему стратегическому пространству. А что произойдет, если мы введем нечестную ситуацию: Алиса может использовать квантовую стратегию, т. е. ее стратегическое пространство по прежнему $S$, в то время как Боб вынужден применять только классические стратегии, чистые либо смешанные? В этом случае наилучшим способом действий для Алисы будет игра $\widehat{M}=\widehat{U}(\pi / 2, \pi / 2)$,
\[
\widehat{M}=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}
i & 1 \\
-1 & -i
\end{array}\right)
\]
(«чудесный ход»), что дает ей по меньшей мере выигрыш $r=3$, поскольку $P_{A}(\widehat{M}, \widehat{U}(\theta, 0)) \geqslant 3$ для любых $\theta \in[0, \pi]$, и оставляет Бобу $P_{B}(\widehat{M}, \widehat{U}(\theta, 0)) \leqslant 1 / 2$ (см. рис. $\left.4(\mathrm{a})\right)$. Таким образом, если в нечестной игре Алиса может быть уверена, что Боб играет $\widehat{U}(\theta, 0)$, она может выбрать «Всегда- $\widehat{M}$ » как предпочтительную стратегию в повторной игре. Это определенно превосходит око за око, но следует помнить, что для этого весьма существенна предположенная ранее асимметрия.

Интересно также исследовать зависимость преимущества Алисы при нечестной игре от степени скрещения начального состояния $\left|\psi_{0}\right\rangle$. Минимальный ожидаемый выигрыш $m$ Алисы всегда может быть достигнут выбором подходящей стратегии $U_{A}$ :
\[
m=\max _{\widehat{U}_{A} \in S} \min _{\widehat{U}_{B}=\widehat{U}(\theta, 0)} P_{A}\left(\widehat{U}_{A}, \widehat{U}_{B}\right) ;
\]

Алиса не может выиграть меньше данной величины. Рассматривая $m$ как функцию параметра скрещения $\gamma \in[0, \pi / 2]$, легко понять, что $m(0)=1$ (т.к. в этом случае доминантная стратегия $\widehat{D}$ есть оптимальный выбор), тогда как при минимальном скрещении имеем $m(\pi / 2)=3$, что достигается при игре $\widehat{M}$. Рис. 4(b) показывает $m$ как функцию параметра скрещения $\gamma$. Мы видим, что в действительности $m$ есть монотонно растущая функция $\gamma$, и максимальное преимущество достигается только при максимальном скрещении. Далее, Алисе следует отказаться от стратегии $\widehat{D}$, если и только если степень скрещения превышает определенное пороговое значение $\gamma_{\text {th }}=\arcsin (1 / \sqrt{5}) \approx 0.464$. Такое пороговое поведение напоминает фазовый переход первого порядка для оптимальной стратегии Алисы: на пороге она должна дискретно поменять свою стратегию с $\widehat{D}$ на $\widehat{Q}$.

Итак, мы показали, что при распространении классических игр, таких как Дилемма Заключенного, на квантовую территорию возникают новые интересные особенности. Весьма аналогично случаю квантовой криптографии и вычислений обнаружено, что квантовые стратегии наилучшим образом реализуются при наличии скрещения $[20,21]$.
Рис. 4. Квантовые и классические стратегии: (а) Выигрыш Алисы как функция $\theta$, когда Боб играет $\widehat{U}(\theta, 0)(\widehat{U}(0,0)=\widehat{C}$ и $\widehat{U}(\pi, 0)=\widehat{D})$ и выборы Алисы $\widehat{C}$ (сплошная линия), $\widehat{D}$ (точки) или $\widehat{M}$ (штрихи). (b) Ожидаемый выигрыш Алисы, который всегда может быть достигнут в нечестной игре, как функция параметра скрещения $\gamma$.

В нашем случае, скрещение вводилось таким образом, что при желании можно было бы играть в класеическую игру. Такой принцип соответствия гарантирует возможность беспристрастного сравнения классической и квантово-механической игр. Вообще, способ квантования данной классической игры не является единственным. Можно использовать, например, возможность того, что оба игрока могут измерять состояние своих кубитов перед стратегической манипуляцией, или допустить приготовление-к-измерению, которое не отменяет скрещения, введенного приготовлением начального состояния игры [19].

Это исследование было стимулировано вдохновляющей лекцией Артура Экерта о квантовых вычислениях. Мы также признательны Ральфу Думу, Тимо Фелбингеру и Анне Сапера за плодотворные обсуждения.