論文の概要: Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
- arxiv url: http://arxiv.org/abs/2110.04651v2
- Date: Tue, 12 Oct 2021 02:28:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 23:09:19.714553
- Title: Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
- Title（参考訳）: 非局所ゲーム、圧縮理論、および算術的階層
- Authors: Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen
- Abstract要約: 非局所ゲームと算術的階層の関係について検討する。
量子値を正確に計算することは、それを近似するよりも厳密に、また通勤演算子値を計算するより厳密に難しいことを示す。
- 参考スコア（独自算出の注目度）: 0.12891210250935145
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the connection between the complexity of nonlocal games and
the arithmetical hierarchy, a classification of languages according to the
complexity of arithmetical formulas defining them. It was recently shown by Ji,
Natarajan, Vidick, Wright and Yuen that deciding whether the
(finite-dimensional) quantum value of a nonlocal game is $1$ or at most
$\frac{1}{2}$ is complete for the class $\Sigma_1$ (i.e., $\mathsf{RE}$). A
result of Slofstra implies that deciding whether the commuting operator value
of a nonlocal game is equal to $1$ is complete for the class $\Pi_1$ (i.e.,
$\mathsf{coRE}$). We prove that deciding whether the quantum value of a
two-player nonlocal game is exactly equal to $1$ is complete for $\Pi_2$; this
class is in the second level of the arithmetical hierarchy and corresponds to
formulas of the form "$\forall x \, \exists y \, \phi(x,y)$". This shows that
exactly computing the quantum value is strictly harder than approximating it,
and also strictly harder than computing the commuting operator value (either
exactly or approximately). We explain how results about the complexity of
nonlocal games all follow in a unified manner from a technique known as
compression. At the core of our $\Pi_2$-completeness result is a new "gapless"
compression theorem that holds for both quantum and commuting operator
strategies. Our compression theorem yields as a byproduct an alternative proof
of Slofstra's result that the set of quantum correlations is not closed. We
also show how a "gap-preserving" compression theorem for commuting operator
strategies would imply that approximating the commuting operator value is
complete for $\Pi_1$.
- Abstract（参考訳）: 本研究では,非局所ゲームの複雑性と,それらを定義する算術公式の複雑さに応じて言語を分類する算術階層との関係について検討する。
最近ではji, natarajan, vidick, wright, yuenによって、非ローカルゲームの(有限次元)量子値が1ドルか、または少なくとも$\frac{1}{2}$が$\sigma_1$(すなわち$\mathsf{re}$)のクラスで完結しているかを決定することが示されている。
Slofstraの結果は、非局所ゲームの可換演算子値が$1$と等しいかどうかを決定することは、クラス$\Pi_1$(つまり$\mathsf{coRE}$)に対して完備であることを意味する。
このクラスは算術階層の第二レベルにあり、「$\forall x \, \exists y \, \phi(x,y)$」という形の式に対応する。
これは、量子値の正確な計算は、それを近似するよりも厳密に、また通勤演算子値の計算よりも厳密に難しいことを示している。
我々は,非ローカルゲームの複雑性に関する結果が,圧縮と呼ばれる手法から統一的に従う方法を説明する。
われわれの$\Pi_2$-completenessの結果の中核は、量子的および可換作用素戦略の両方に当てはまる新しい「ギャップレス」圧縮定理である。
我々の圧縮定理は、量子相関の集合が閉でないというSlofstraの結果の代替証明を副産物として得る。
また、可換作用素戦略のための「gap保存」圧縮定理は、可換作用素値の近似が$\pi_1$で完備であることを示す。
関連論文リスト
- The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
スムースブースターは任意の例にあまり重みを付けない分布を生成する。
もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
論文 参考訳（メタデータ） (2024-09-17T23:09:25Z) - Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳（メタデータ） (2023-11-28T21:15:30Z) - Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文 参考訳（メタデータ） (2023-11-22T20:27:05Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳（メタデータ） (2023-03-03T16:53:30Z) - Quantum free games [2.298932494750101]
我々は、$n$変数上の3SATのベルQMA(2)プロトコルを示し、通信総量は$tildeO(sqrtn)である。
論文 参考訳（メタデータ） (2023-02-08T20:32:24Z) - 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) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。