論文の概要: On the complexity of zero gap MIP*
- arxiv url: http://arxiv.org/abs/2002.10490v2
- Date: Wed, 29 Apr 2020 00:08:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 05:07:50.936254
- Title: On the complexity of zero gap MIP*
- Title（参考訳）: 零ギャップ MIP* の複雑性について
- Authors: Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen
- Abstract要約: クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
- 参考スコア（独自算出の注目度）: 0.11470070927586014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The class $\mathsf{MIP}^*$ is the set of languages decidable by multiprover
interactive proofs with quantum entangled provers. It was recently shown by Ji,
Natarajan, Vidick, Wright and Yuen that $\mathsf{MIP}^*$ is equal to
$\mathsf{RE}$, the set of recursively enumerable languages. In particular this
shows that the complexity of approximating the quantum value of a non-local
game $G$ is equivalent to the complexity of the Halting problem.
In this paper we investigate the complexity of deciding whether the quantum
value of a non-local game $G$ is exactly $1$. This problem corresponds to a
complexity class that we call zero gap $\mathsf{MIP}^*$, denoted by
$\mathsf{MIP}^*_0$, where there is no promise gap between the verifier's
acceptance probabilities in the YES and NO cases. We prove that
$\mathsf{MIP}^*_0$ extends beyond the first level of the arithmetical hierarchy
(which includes $\mathsf{RE}$ and its complement $\mathsf{coRE}$), and in fact
is equal to $\Pi_2^0$, the class of languages that can be decided by quantified
formulas of the form $\forall y \, \exists z \, R(x,y,z)$.
Combined with the previously known result that $\mathsf{MIP}^{co}_0$ (the
commuting operator variant of $\mathsf{MIP}^*_0$) is equal to $\mathsf{coRE}$,
our result further highlights the fascinating connection between various models
of quantum multiprover interactive proofs and different classes in
computability theory.
- Abstract（参考訳）: クラス $\mathsf{mip}^*$ は、量子絡み合ったプロバーを持つ多元証明によって決定可能な言語の集合である。
Ji, Natarajan, Vidick, Wright and Yuen が最近示したところによると、$\mathsf{MIP}^*$ は再帰可算言語の集合である $\mathsf{RE}$ に等しい。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
本稿では,非ローカルゲームである$g$の量子値が正確に1ドルであるかどうかを判断する複雑さについて検討する。
この問題は、 0 のギャップ $\mathsf{MIP}^*$ を $\mathsf{MIP}^*_0$ と表現する複雑性クラスに対応しており、YES と NO のケースでは、検証者の受容確率の間に約束のギャップはない。
我々は、$\mathsf{MIP}^*_0$ が算術階層の最初のレベルを越えて拡張されることを証明し($\mathsf{RE}$ とその補集合 $\mathsf{coRE}$ を含む)、実際に $\Pi_2^0$ と同値であり、$\forall y \, \exists z \, R(x,y,z)$ という形の量式で決定できる言語クラスである。
これまで知られていた結果と、$\mathsf{MIP}^{co}_0$($\mathsf{MIP}^*_0$の可換作用素変種)が$\mathsf{coRE}$に等しいことと合わせて、この結果は、量子マルチプロペラインタラクティブ証明の様々なモデルと計算可能性理論の異なるクラスの間の魅力的な関係をさらに強調する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth [8.66267734067296]
制限しきい値関数を演算する境界を持つ定数深さ回路のクラスについて検討する。
十分大きな$mathsfbPTFC0[k]$の場合、$mathsfbPTFC0[k]は$mathsfTC0[k]を含む。
論文 参考訳（メタデータ） (2024-08-29T09:40:55Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳（メタデータ） (2024-01-02T22:25:56Z) - Parity vs. AC0 with simple quantum preprocessing [0.0]
我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。
私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
論文 参考訳（メタデータ） (2023-11-22T20:27:05Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Monogamy of entanglement between cones [68.8204255655161]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。
我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文 参考訳（メタデータ） (2022-06-23T16:23:59Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy [0.12891210250935145]
非局所ゲームと算術的階層の関係について検討する。
量子値を正確に計算することは、それを近似するよりも厳密に、また通勤演算子値を計算するより厳密に難しいことを示す。
論文 参考訳（メタデータ） (2021-10-09T21:53:02Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。