論文の概要: Quantum free games
- arxiv url: http://arxiv.org/abs/2302.04322v1
- Date: Wed, 8 Feb 2023 20:32:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 17:33:48.355748
- Title: Quantum free games
- Title（参考訳）: 量子自由ゲーム
- Authors: Anand Natarajan, Tina Zhang
- Abstract要約: 我々は、$n$変数上の3SATのベルQMA(2)プロトコルを示し、通信総量は$tildeO(sqrtn)である。
- 参考スコア（独自算出の注目度）: 2.298932494750101
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The complexity of free games with two or more classical players was
essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC'14). There
are two complexity classes that can be considered quantum analogues of
classical free games: (1) AM*, the multiprover interactive proof class
corresponding to free games with entangled players, and, somewhat less
obviously, (2) BellQMA(2), the class of quantum Merlin-Arthur proof systems
with two unentangled Merlins, whose proof states are separately measured by
Arthur. In this work, we make significant progress towards a tight
characterization of both of these classes. 1. We show a BellQMA(2) protocol for
3SAT on $n$ variables, where the total amount of communication is
$\tilde{O}(\sqrt{n})$. This answers an open question of Chen and Drucker (2010)
and also shows, conditional on ETH, that the algorithm of Brand\~{a}o,
Christandl and Yard (STOC'11) is tight up to logarithmic factors. 2. We show
that $\mathsf{AM}^*[n_{\text{provers}} = 2, q = O(1), a =\mathrm{poly}\log(n)]
= \mathsf{RE}$, i.e. that free entangled games with constant-sized questions
are as powerful as general entangled games. Our result is a significant
improvement over the headline result of Ji et al. (2020), whose MIP* protocol
for the halting problem has $\mathrm{poly}(n)$-sized questions and answers. 3.
We obtain a zero-gap AM* protocol for a $\Pi_2$ complete language with
constant-size questions and almost logarithmically large answers, improving on
the headline result of Mousavi, Nezhadi and Yuen (STOC'22). 4. Using a
connection to the nonuniform complexity of the halting problem we show that any
MIP* protocol for RE requires $\Omega(\log n)$ bits of communication. It
follows that our results in item 3 are optimal up to an $O(\log^* n)$ factor,
and that the gapless compression theorems of MNY'22 are asymptotically optimal.
- Abstract（参考訳）: アーロンソン、インパグリアッツォ、モシュコビッツ(ccc'14)によって2人以上のクラシック選手によるフリーゲームの複雑さは本質的に解決された。
古典自由ゲームの量子アナログと見なすことができる2つの複雑性クラスが存在する: (1) am*, マルチプロファー対話型証明クラス, (2) bellqma(2), 量子メルリン-アーサー証明系の2つの非絡みのないマーリンはアーサーによって別々に測定される。
本研究では,これら2つのクラスを厳密に評価する上で,大きな進歩を遂げる。
1.$n$変数上の3SATのベルQMA(2)プロトコルを示し、通信の総量は$\tilde{O}(\sqrt{n})$である。
これは Chen and Drucker (2010) のオープンな疑問に答え、ETH の条件として、Brand\~{a}o, Christandl and Yard (STOC'11) のアルゴリズムは対数因子に強く依存していることを示す。
2) $\mathsf{AM}^*[n_{\text{provers}} = 2, q = O(1), a =\mathrm{poly}\log(n)] = \mathsf{RE}$, すなわち、一定の大きさの質問を持つ自由絡み合いゲームは一般的な絡み合いゲームと同じくらい強力であることを示す。
我々の結果は、停止問題に対するMIP*プロトコルが$\mathrm{poly}(n)$-sized question and answer である Ji et al. (2020) の見出し結果よりも大幅に改善されている。
3. 一定の大きさの質問とほぼ対数的に大きな回答を持つ$\pi_2$完全言語に対するゼロギャップam*プロトコルを求め、mousavi, nezhadi, yuen (stoc'22) の見出し結果を改善した。
4. 停止問題の非一様複雑性への接続を用いて、reに対するmip*プロトコルは$\omega(\log n)$ の通信を必要とすることを示す。
第3項目の結果は、最大で$o(\log^* n)$ factor まで最適であり、mny'22 のギャップのない圧縮定理は漸近的に最適である。
関連論文リスト
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - The Complexity of NISQ [15.842125145638693]
NISQデバイスは、その計算能力を理解するために必須である。
本稿では、複雑性クラス $textsfNISQ $ を定義し、研究する。
3つのよく研究された問題に対して$textsfNISQ$のパワーを考慮する。
論文 参考訳（メタデータ） (2022-10-13T17:58:32Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Connes implies Tsirelson: a simple proof [91.3755431537592]
コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。
また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
論文 参考訳（メタデータ） (2022-09-16T13:59:42Z) - Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。
これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文 参考訳（メタデータ） (2022-02-03T18:18:28Z) - Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy [0.12891210250935145]
非局所ゲームと算術的階層の関係について検討する。
量子値を正確に計算することは、それを近似するよりも厳密に、また通勤演算子値を計算するより厳密に難しいことを示す。
論文 参考訳（メタデータ） (2021-10-09T21:53:02Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Quasi-polynomial time algorithms for free quantum games in bounded
dimension [11.56707165033]
2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。
量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
論文 参考訳（メタデータ） (2020-05-18T16:55:08Z) - On the complexity of zero gap MIP* [0.11470070927586014]
クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
論文 参考訳（メタデータ） (2020-02-24T19:11:01Z) - Complexity limitations on one-turn quantum refereed games [0.6091702876917281]
本論文は,量子参照ゲームの理論的側面を研究する。
抽象ゲームは、審判に量子状態を送信する2人のプレーヤーの間のものである。
審判は、2つの状態に対して効率よく実施可能な共同測定を行い、どのプレイヤーが勝つかを判定する。
論文 参考訳（メタデータ） (2020-02-04T19:28:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。