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

Квантовая реферируемая игра в квантовой обработке информации - это класс игр в общей теории квантовых игр . ^[1] Игра проводится между двумя игроками, Алисой и Бобом, и разрешается судьей. Судья выводит выигрыш для игроков после взаимодействия с ними в течение фиксированного количества раундов, при этом обмениваясь квантовой информацией .

Определение [ править ]

Квантовый рефери An -turn выполняет раунды взаимодействия с игроком Алисой и Бобом. Каждое взаимодействие включает в себя получение некоторых квантовых состояний от Алисы и Боба, обработку квантовых состояний вместе с «оставшимся» состоянием от предыдущего взаимодействия, создание некоторого выходного состояния и отправку части выходного состояния игрокам. В конце раундов судья обрабатывает окончательное состояние, полученное от игроков, и принимает решение о выплате Алисе и Бобу. Роль судьи - передавать кубиты игрокам Алисе и Бобу. Задача рефери - запутать кубиты, что, как утверждается, важно в квантовых играх. Когда Алиса и Боб возвращают кубиты рефери, рефери проверяет их окончательные состояния. ^[2] ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle n}$

Квантовые Реферированные Игры

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

{\ Displaystyle {\ mathcal {X}} _ {k} = {\ mathcal {A}} _ {k} \ otimes {\ mathcal {B}} _ {k}}

а также

{\ displaystyle {\ mathcal {Y}} _ {k} = {\ mathcal {C}} _ ​​{k} \ otimes {\ mathcal {D}} _ {k}}

для сложных евклидовых пространств и . ${\ displaystyle {\ mathcal {A}} _ {k}, {\ mathcal {B}} _ {k}, {\ mathcal {C}} _ {k}}$ ${\ displaystyle {\ 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$ $V_{A},V_{B}:\Sigma \mapsto \mathbb {R}$ $a$

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

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

Квантовая рецензируемая игра с нулевой суммой [ править ]

Подобно классической игре с нулевой суммой, квантовая игра с нулевой суммой ^[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})

где - множество всех n-поворотных стратегий, имеющих входное и выходное пространство . ${\mathcal {S}}_{n}({\mathcal {X}}_{1\cdots n},{\mathcal {Y}}_{1\cdots 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})$

One Turn Quantum Refereed Game [ править ]

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

Квантовая реферируемая игра Bell State [ править ]

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

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

CHSH Quantum Refereed Game [ править ]

Реферированная игра ЧШ [ править ]

Одним из примеров квантовой реферируемой игры является квантовая реферированная игра CHSH. Игра CHSH использует двоичную форму для представления выходных данных (например, 0 и 1). В этой игре Алиса и Боб вместе играют против гипотетического дома, и им не разрешено общаться друг с другом. Алисе и Бобу судья дает случайный кубит. Чтобы выиграть игру, им нужно обеспечить выходы (a и b), которые максимизируют a⊕b = xy. ^[7]

Классический анализ реферированной игры CHSH [ править ]

Диаграмма вероятностей игры ЧШ ^[7]
(х, у) \| (а, б)	(0,0)	(0,1)	(1,0)	(1,1)
(0,0)	1/2	0	0	S * (1/2)
(0,1)	1/2	0	0	1/2
(1,0)	1/2	0	0	1/2
(1,1)	0	1/2	1/2	0

Лучшая стратегия для Алисы и Боба - всегда возвращать рефери состояние 0. ^[7] Если они сделают это, как показано на графике, они выиграют с вероятностью 75%. ^{[7] На основании} этих вероятностей казино решает, что если Алиса и Боб выиграют, они получат 1 очко, а если проиграют, то потеряют 3 очка. Это дает вероятность выплаты . Это гарантирует, что все останутся безубыточными. $1*(3/4)-3*(1/4)=0$

Квантовый анализ квантовой реферируемой игры CHSH [ править ]

Алиса и Боб могут использовать запутанные состояния, чтобы настроить игру в свою пользу. Алиса и Боб оба получают фотон в запутанном состоянии | ψ⟩ = √2 [| 0⟩ | 0⟩ + | 1⟩ | 1⟩]. ^[7] Если Алиса получает x = 1, она может применить унитарную Û (π / 4) к своему кубиту и затем измерить его, если она получает x = 0, все, что ей нужно сделать, это измерить свой кубит. Если Боб получает y = 0, он применяет Û (π / 8) и измеряет его, а если он получает y = 1, он применяет Û (-π / 8), а затем измеряет его. ^[7] Использование этой стратегии позволяет им иметь максимальную вероятность выигрыша S = , что позволяет Алисе и Бобу выигрывать каждый раз. ^[7] $2{\sqrt {2}}$

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

Квантовое интерактивное доказательство с двумя конкурирующими доказывающими сторонами является обобщением системы квантовых интерактивных доказательств с одним доказывающим устройством . ^[8]^[9] Это может быть смоделировано играми с нулевой суммой рефери, в которых Алиса и Боб выступают в роли соревнующихся доказывающих, а судья - проверяющим. Предполагается, что рефери ограничен в вычислительном отношении (квантовая схема полиномиального размера), в то время как Алиса и Боб могут быть неограниченными в вычислительном отношении. Алиса, Боб и судья получают общую строку, и после фиксированных раундов взаимодействий (обмена квантовой информацией между доказывающими и судьей) судья решает, выиграет Алиса или Боб.

Классическая художественная гимнастика [ править ]

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

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

1. для каждого существует стратегия, позволяющая Алисе выиграть с вероятностью ≥ 3/4, и

x\in L_{\text{yes}}

2. для каждого из них есть стратегия, позволяющая Бобу выиграть с вероятностью ≥ 3/4.

x\in L_{\text{no}}

Известно, что RG = EXP . ^[10]^[11]

QRG [ править ]

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

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

1. если существует стратегия, позволяющая Алисе выиграть с вероятностью ≥ 3/4, и

x\in L_{\text{yes}}

2. если существует стратегия, позволяющая Бобу выиграть с вероятностью ≥ 3/4.

x\in L_{\text{no}}

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

Формулировка полуопределенной программы [ править ]

В квантовой игре с рефери в конце всех взаимодействий судья выводит один из двух возможных результатов, чтобы указать, выиграет Алиса или Боб . $\{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: ^[1]

{\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 является экспоненциальной (из состояний тензорного произведения) в , а SDP имеет полиномиальный размер в размерности входного и выходного пространства. Поскольку существуют эффективные алгоритмы, которые могут решить SDP за полиномиальное время ^[12]^[13]^[14], отсюда следует, что QRG ⊆ EXP. $n$

См. Также [ править ]

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

Ссылки [ править ]

^ а б в г Гутоски, G; Уотрус Дж (2007). К общей теории квантовых игр . Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений . п. 565. arXiv : Quant-ph / 0611234 . Bibcode : 2006quant.ph.11234G . DOI : 10.1145 / 1250790.1250873 . ISBN 9781595936318. S2CID 2329605 .
^ «Пусть начнутся квантовые игры» . Мир физики . 2002-10-02 . Проверено 11 ноября 2020 .
^ Клив, R; Хойер П .; Тонер B .; Уотроус Дж. (2004). «Последствия и пределы нелокальных стратегий». Труды 19-й ежегодной конференции IEEE по вычислительной сложности : 236–249. arXiv : квант-ph / 0404076 . Bibcode : 2004quant.ph..4076C .
^ Брассард, Г .; Бродбент А .; Тэпп А. (2005). «Квантовая псевдотелепатия». Основы физики . 35 (11): 1877–1907. arXiv : квант-ph / 0407221 . Bibcode : 2005FoPh ... 35.1877B . DOI : 10.1007 / s10701-005-7353-4 . S2CID 7395322 .
^ a b c d e Гутоски, Гас; Уотроус, Джон (2005). «Квантовые интерактивные доказательства с конкурирующими доказательствами». Стакс 2005 . Конспект лекций по информатике. 3404 . С. 605–616. arXiv : cs / 0412102 . DOI : 10.1007 / 978-3-540-31856-9_50 . ISBN 978-3-540-24998-6. S2CID 15662983 .
^ Гош, Soumik (2020). «Исследование однооборотных квантовых рецензируемых игр» (PDF) . У Ватерлоо . Проверено 11 октября 2020 .
^ Б с д е е г ч Web.Stanford.Edu , 2020, http://web.stanford.edu/~oas/SI/QM/notes/SIQMWeek3.pdf.
^ Китаев, А; Уотрус Дж (2000). «Распараллеливание, усиление и экспоненциальное временное моделирование квантовой интерактивной системы доказательства». Труды 32-го симпозиума AMC по теории вычислений : 608–617.
^ Watrous, J (2003). «У PSPACE есть квантовые интерактивные системы доказательства постоянного раунда». Теоретическая информатика . 292 (3): 575–588. DOI : 10.1016 / s0304-3975 (01) 00375-9 .
^ Коллер, D; Мегиддо Н. (1992). «Сложность игры с нулевой суммой для двоих в развернутой форме». Игры и экономическое поведение . 4 (4): 528–552. CiteSeerX 10.1.1.30.7625 . DOI : 10.1016 / 0899-8256 (92) 90035-ц .
^ Feige, U; Килиан Дж. (1997). Делаем игры короткими . Труды Двадцать девятого ежегодного симвозиума ACM по теории вычислений . С. 506–516. CiteSeerX 10.1.1.5.1990 . DOI : 10.1145 / 258533.258644 . ISBN 978-0897918886. S2CID 15664449 .
^ ХАЧИЯН, L (1979). «Алгоритм с полиномиальным временем в линейном программировании». Советская математика - Доклады . 20 : 191–194.
^ Grötschel, M ; Lovász L .; Шрайвер А. (1988). Геометрические алгоритмы и комбинаторная оптимизация . Алгоритмы и комбинаторика. Springer. ISBN 978-3-642-97883-8.
^ Нестеров, Юрий; Немировский, Аркадий (1994). Полиномиальные алгоритмы внутренней точки в выпуклом программировании (PDF) . SIAM Исследования в области прикладной математики. 13 . DOI : 10.1137 / 1.9781611970791 . ISBN 978-0-89871-319-0.

[general_qg-1] а б в г Гутоски, G; Уотрус Дж (2007). К общей теории квантовых игр . Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений . п. 565. arXiv : Quant-ph / 0611234 . Bibcode : 2006quant.ph.11234G . DOI : 10.1145 / 1250790.1250873 . ISBN 9781595936318. S2CID 2329605 .

[2] «Пусть начнутся квантовые игры» . Мир физики . 2002-10-02 . Проверено 11 ноября 2020 .

[3] Клив, R; Хойер П .; Тонер B .; Уотроус Дж. (2004). «Последствия и пределы нелокальных стратегий». Труды 19-й ежегодной конференции IEEE по вычислительной сложности : 236–249. arXiv : квант-ph / 0404076 . Bibcode : 2004quant.ph..4076C .

[4] Брассард, Г .; Бродбент А .; Тэпп А. (2005). «Квантовая псевдотелепатия». Основы физики . 35 (11): 1877–1907. arXiv : квант-ph / 0407221 . Bibcode : 2005FoPh ... 35.1877B . DOI : 10.1007 / s10701-005-7353-4 . S2CID 7395322 .

[:0-5] Гутоски, Гас; Уотроус, Джон (2005). «Квантовые интерактивные доказательства с конкурирующими доказательствами». Стакс 2005 . Конспект лекций по информатике. 3404 . С. 605–616. arXiv : cs / 0412102 . DOI : 10.1007 / 978-3-540-31856-9_50 . ISBN 978-3-540-24998-6. S2CID 15662983 .

[6] Гош, Soumik (2020). «Исследование однооборотных квантовых рецензируемых игр» (PDF) . У Ватерлоо . Проверено 11 октября 2020 .

[:1-7] Б с д е е г ч Web.Stanford.Edu , 2020, http://web.stanford.edu/~oas/SI/QM/notes/SIQMWeek3.pdf.

[8] Китаев, А; Уотрус Дж (2000). «Распараллеливание, усиление и экспоненциальное временное моделирование квантовой интерактивной системы доказательства». Труды 32-го симпозиума AMC по теории вычислений : 608–617.

[9] Watrous, J (2003). «У PSPACE есть квантовые интерактивные системы доказательства постоянного раунда». Теоретическая информатика . 292 (3): 575–588. DOI : 10.1016 / s0304-3975 (01) 00375-9 .

[10] Коллер, D; Мегиддо Н. (1992). «Сложность игры с нулевой суммой для двоих в развернутой форме». Игры и экономическое поведение . 4 (4): 528–552. CiteSeerX 10.1.1.30.7625 . DOI : 10.1016 / 0899-8256 (92) 90035-ц .

[11] Feige, U; Килиан Дж. (1997). Делаем игры короткими . Труды Двадцать девятого ежегодного симвозиума ACM по теории вычислений . С. 506–516. CiteSeerX 10.1.1.5.1990 . DOI : 10.1145 / 258533.258644 . ISBN 978-0897918886. S2CID 15664449 .

[12] ХАЧИЯН, L (1979). «Алгоритм с полиномиальным временем в линейном программировании». Советская математика - Доклады . 20 : 191–194.

[13] Grötschel, M ; Lovász L .; Шрайвер А. (1988). Геометрические алгоритмы и комбинаторная оптимизация . Алгоритмы и комбинаторика. Springer. ISBN 978-3-642-97883-8.

[14] Нестеров, Юрий; Немировский, Аркадий (1994). Полиномиальные алгоритмы внутренней точки в выпуклом программировании (PDF) . SIAM Исследования в области прикладной математики. 13 . DOI : 10.1137 / 1.9781611970791 . ISBN 978-0-89871-319-0.

[1]