Квантовая судейская игра

Квантовая судейская игра в квантовой обработке информации — это класс игр общей теории квантовых игр . В нем участвуют два игрока, Алиса и Боб, и его решает судья. Судья выводит выигрыш игрокам после взаимодействия с ними в течение фиксированного количества раундов, одновременно обмениваясь квантовой информацией .

Определение

Ан $n$-поворот квантовый судья выполняет $n$ раунды взаимодействия с игроком Алисой и Бобом. Каждое взаимодействие включает в себя получение некоторых квантовых состояний от Алисы и Боба, обработку квантовых состояний вместе с «остаточным» состоянием от предыдущего взаимодействия, создание некоторого выходного состояния и отправку части выходного состояния игрокам. В конце $n$ раундов судья обрабатывает окончательное состояние, полученное от игроков, и определяет выигрыш Алисы и Боба. Роль рефери — передать кубиты игрокам Алисе и Бобу. Задача судьи — запутать кубиты, что, как утверждается, крайне важно в квантовых играх. Когда Алиса и Боб возвращают кубиты рефери, тот проверяет их окончательное состояние.

Квантовые судейские игры

С математической точки зрения, арбитр в n-ходах — это измеряющая ко-стратегия. $\{R_{a}:a\in \Sigma \}$ чьи входные пространства ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}$ и выходные пространства ${\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}$ имеют форму

${\mathcal {X}}_{k}={\mathcal {A}}_{k}\otimes {\mathcal {B}}_{k}$ и ${\mathcal {Y}}_{k}={\mathcal {C}}_{k}\otimes {\mathcal {D}}_{k}$

для комплексных евклидовых пространств ${\mathcal {A}}_{k},{\mathcal {B}}_{k},{\mathcal {C}}_{k}$ и ${\mathcal {D}}_{k},\ 1\leq k\leq n$.

${\mathcal {A}}_{k},{\mathcal {B}}_{k}$ представляет собой сообщение, отправленное рефери Алисе и Бобу во время хода $k$, и ${\mathcal {C}}_{k},{\mathcal {D}}_{k}$ соответствуют их ответам. В конце $n$ повороты, рефери производит вывод $a\in \Sigma$

Ан $n$-игра с квантовым судейством состоит из n-ходового судьи и функций $V_{A},V_{B}:\Sigma \mapsto \mathbb {R}$ который отображает каждый выход измерения $a$ к выигрышу Алисы и Боба.

Отдельные игры с квантовым судейством могут накладывать определенные ограничения на стратегии, которые могут выбирать Алиса и Боб. Например, в нелокальных играх и псевдотелепатические игры, Алисе и Бобу разрешено разделять запутанные ситуации, но им запрещено общаться. В целом такие ограничения могут не применяться в играх с квантовым судейством.

Считается, что язык L имеет рецензируемую игру с ошибкой ε, если он имеет верификатор с полиномиальным временем, удовлетворяющий этим условиям: для каждой строки xεL Алиса (доказывающая да) может убедить рефери принять x с вероятностью не менее 1- ε независимо от стратегии Боба (не доказывающий), и для каждой строки x∉L Боб может убедить рефери отклонить x с вероятностью не менее 1-ε независимо от стратегии Алисы.

Игры с нулевой суммой

Подобно классической игре с нулевой суммой , квантовая судейская игра с нулевой суммой это квантовая судейская игра с дополнительным ограничением $V_{A}(a)+V_{B}(a)=0$.

Естественно предположить, что Алиса и Боб играют независимые стратегии в квантовой судейской игре с нулевой суммой, поскольку обоим игрокам одновременно не может быть выгодно общаться напрямую друг с другом или изначально разделять состояние запутанности {ссылка}. В этом случае стратегию Алисы и Боба можно представить в виде

$A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})$ и $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$

где ${\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots n})$ - это набор всех n-ходовых стратегий, имеющих входное пространство ${\mathcal {X}}_{1},\cdots ,{\mathcal {X}}_{n}$ и выходное пространство ${\mathcal {Y}}_{1},\cdots ,{\mathcal {Y}}_{n}$.

Тогда комбинированная стратегия $A\otimes B$.

Теорема Мин-Макса

Определять $V(a)=V_{A}(a)=-V_{B}(a)$, и $R=\sum _{a\in \Sigma }V(a)R_{a}$, то ожидаемый выигрыш Алисы равен $\sum _{a\in \Sigma }V(a)\langle A\otimes B,R_{a}\rangle =\langle A\otimes B,R\rangle$

Тогда оптимальная стратегия для Алисы будет заключаться в задаче мин-макса.

$\max _{A}\min _{B}\langle A\otimes B,R\rangle =\min _{B}\max _{A}\langle A\otimes B,R\rangle$.

Приведенное выше равенство имеет место, поскольку $A,B$ извлекаются из компактных и выпуклых множеств ${\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})$ и ${\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$. Это называется теоремой о мин-максе для квантовых игр с нулевой суммой.

Игры в один ход

Квантовые судейские игры с одним ходом представляют собой подмножество квантовых судейских игр (QRG), в которых есть два неограниченных игрока (Алиса и Боб) и судья, ограниченный в вычислительном отношении. Их называют играми с одним ходом или QRG1, потому что в каждой игре делается только один ход. В игре каждый игрок отправляет матрицу плотности рефери, который затем подключает эти состояния к своей квантовой схеме. Победитель игры определяется исходом схемы, где Алиса выигрывает в большинстве случаев, когда схема создает состояние «да» или |1>, а Боб выигрывает в большинстве случаев, когда схема выдает «нет» или «|1>». Состояние |0> создается схемой. Ход состоит из того, что рефери отправляет сообщение доказывающему (Алисе или Бобу), а затем Алиса или Боб отправляют ответ рефери. Порядок игры следующий: Алиса отправляет рефери свою матрицу плотности, затем рефери обрабатывает состояние Алисы и отправляет состояние Бобу, затем Боб измеряет состояние и отправляет классический результат рефери, затем рефери проверяет состояние Боба. измерение и либо дает «да», что означает победу Алисы, либо дает «нет», и Боб выигрывает.

Игры штата Белл

В квантовой судейской игре штата Белл участвуют три участника: Алиса, Боб и судья. Игра состоит из трёх дверей. За каждой дверью находится либо x, либо o (состояние вращения вверх или вниз). Рефери дает Алисе и Бобу три условия относительно того, что находится за каждой из дверей. Например, условия могут быть такими: 1) Двери 1 и 2 одинаковы. 2) Двери 2 и 3 одинаковые. 3) Двери 1 и 3 разные.

Цель этой игры — Алиса и Боб найти за дверями подходящую пару. В квантовых терминах это означает, что Алиса и Боб создают состояния совпадающей плотности. Во время игры Алисе и Бобу не разрешается общаться, но им разрешено вырабатывать стратегию до начала игры. Они делают это, разделяя запутанную пару фотонов. Разработка стратегии позволяет Алисе и Бобу максимизировать свои изменения в выигрыше. Без разработки стратегии Алиса и Боб имеют шанс на победу 2/3. Благодаря разработке стратегии вероятность Алисы и Боба создать совпадающие квантовые состояния увеличивается с 2/3 до 3/4.

Квантовое интерактивное доказательство с конкурирующими пруверами

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

Классические игры

В классической постановке РГ можно рассматривать как следующую задачу. Алисе, Бобу и рефери дают какое-то заявление. Алиса пытается убедить рефери в том, что утверждение верно, а Боб пытается убедить рефери в том, что утверждение ложно. Рефери, обладающий ограниченными вычислительными мощностями, рассмотрит доказательства, предоставленные Алисой и Бобом, задаст им вопросы и в конце дня решит, какой игрок прав (победит). Цель состоит в том, чтобы рефери нашел алгоритм, при котором, если утверждение истинно, у Алисы есть способ выиграть с вероятностью, большей 3/4, а если утверждение ложно, у Боба есть способ выиграть с вероятность больше 3/4. Эта вероятность равна 1-ε.

На языке теории сложности проблема обещаний $L=(L_{\text{yes}},L_{\text{no}})$ имеет классическую судейскую игру (классическую РГ), если существует судья, описываемый рандомизированными вычислениями за полиномиальное время , такой, что

1. для каждого $x\in L_{\text{yes}}$, существует стратегия победы Алисы с вероятностью ≥ 3/4, и

2. для каждого $x\in L_{\text{no}}$, существует стратегия победы Боба с вероятностью ≥ 3/4.

Известно, что RG = EXP .

Квантовые игры

Квантовые интерактивные системы доказательств с конкурирующими доказывающими являются обобщением классической РГ, где судья теперь ограничен квантовыми схемами, генерируемыми с полиномиальным временем , и может обмениваться квантовой информацией с игроками. Таким образом, QRG можно рассматривать как следующую проблему. Алисе, Бобу и рефери дается какое-то утверждение (оно может включать квантовое состояние). Алиса пытается убедить рефери, что утверждение верно, а Боб пытается убедить рефери, что утверждение ложно. Рефери может задавать вопросы испытателям через квантовые состояния, получать ответы в квантовых состояниях и анализировать полученные квантовые состояния с помощью квантового компьютера. После общения с Алисой и Бобом за $n$ раундов судья решает, является ли утверждение правдивым или ложным. Если у судьи есть возможность принять правильное решение с вероятностью ≥ 3/4, игра проходит в QRG. Эта вероятность ≥ 1-ε.

Более формально, QRG обозначает класс сложности для всех задач обещания, в которых квантовые игры с судейством определяются следующим образом. Учитывая строку $x$, проблема с обещанием $L=(L_{\text{yes}},L_{\text{no}})$ находится в QRG, если существует судья, представленный квантовой схемой, генерируемой с полиномиальным временем, такой, что

1. если $x\in L_{\text{yes}}$, существует стратегия победы Алисы с вероятностью ≥ 3/4, и

2. если $x\in L_{\text{no}}$, существует стратегия победы Боба с вероятностью ≥ 3/4.

Оказывается, что QRG = EXP — разрешение рефери использовать квантовую схему и отправлять или получать квантовую информацию не дает рефери каких-либо дополнительных полномочий. EXP ⊆ QRG следует из того, что EXP = RG ⊆ QRG. доказал QRG ⊆ EXP, формулируя QRG с использованием полуопределенных программ (SDP).

Semidefinite program formulation

В квантовой игре с судейством в конце всех взаимодействий судья выводит один из двух возможных результатов. $\{a,b\}$ чтобы указать, выиграет ли Алиса $(a)$ или Боб победит $(b)$.

Параметр $V(a)=1,V(b)=0$ приводит к квантовой судейской игре, ценность которой равна максимальной вероятности выигрыша Алисы.

Используя те же обозначения, что и в квантовой игре с нулевой суммой, описанной выше, судья представлен операторами $\{R_{a},R_{b}\}$, Алиса может выбрать стратегию из $A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n})$и Боб из $B\in {\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})$. Определять

$\Omega _{a}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{a})$ , и

$\Omega _{b}(A)=\operatorname {Tr} _{{\mathcal {C}}_{1\cdots n}\otimes {\mathcal {A}}_{1\cdots n}}((A\otimes I_{{\mathcal {D}}_{1\cdots n}\otimes B_{1\cdots n}})R_{b})$,

где $\operatorname {Tr} _{\mathcal {X}}(Z)$ — оператор частичной трассировки .

Выводы судьи $a$ с вероятностью $\langle A\otimes B,R_{a}\rangle =\langle B,\Omega _{a}(A)\rangle$, и $b$ с вероятностью $\langle A\otimes B,R_{b}\rangle =\langle B,\Omega _{b}(A)\rangle$. $\{\Omega _{a}(A),\Omega _{b}(A)\}$ можно рассматривать как совместную стратегию, объединяющую стратегию Алисы и стратегию рефери.

Для любой конкретной стратегии $A$ Алиса выбирает, максимальная вероятность выигрыша Боба равна

$\max _{B}\langle B,\Omega _{b}(A)\rangle$,

которое по свойству стратегии представления равно

$\min\{p\geq 0:\Omega _{b}(A)\leq pQ,\ Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\}$.

Следовательно, чтобы максимизировать вероятность выигрыша Алисы, $p$, максимальная вероятность выигрыша Боба, должна быть минимизирована для всех возможных стратегий. Цель состоит в том, чтобы вычислить

${\begin{array}{rl}\min &p\\{\text{subject to}}&\Omega _{b}(A)\leq pQ,\\&A\in {\mathcal {S}}_{n}({\mathcal {A}}_{1\cdots n},{\mathcal {C}}_{1\cdots n}),\\&Q\in {\text{co-}}{\mathcal {S}}_{n}({\mathcal {B}}_{1\cdots n},{\mathcal {D}}_{1\cdots n})\end{array}}$.

Эту задачу минимизации можно выразить следующей задачей SDP:

${\begin{array}{rll}\min &\operatorname {Tr} (P_{1})\\{\text{subject to}}&\Omega _{b}(A_{n})\leq Q,\\&\operatorname {Tr} _{{\mathcal {C}}_{k}}(A_{k})=A_{k-1}\otimes I_{{\mathcal {A}}_{k}}&(2\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {C}}_{1}}(A_{1})=I_{{\mathcal {A}}_{1}},\\&Q_{k}=P_{k}\otimes I_{{\mathcal {D}}_{k}}&(1\leq k\leq n),\\&\operatorname {Tr} _{{\mathcal {B}}_{k}}(P_{k})=Q_{k-1}&(2\leq k\leq n),\\&A_{k}\in \operatorname {Pos} ({\mathcal {C}}_{1\cdots k}\otimes A_{1\cdots k})&(1\leq k\leq n),\\&Q_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\&P_{k}\in \operatorname {Pos} ({\mathcal {D}}_{1\cdots k}\otimes B_{1\cdots k})&(1\leq k\leq n),\\\end{array}}$.

Размерность входного и выходного пространства этого SPD является экспоненциальной (из состояний тензорного произведения) в $n$, а SDP имеет полиномиальный размер от размерности входного и выходного пространства. Поскольку существуют эффективные алгоритмы, которые могут решать SDP за полиномиальное время, отсюда следует, что QRG ⊆ EXP.

См. также

• Теорема Мин-Макса
• Полуопределенное программирование
• КИП (сложность)