論文の概要: Quantum soundness of the classical low individual degree test
- arxiv url: http://arxiv.org/abs/2009.12982v1
- Date: Sun, 27 Sep 2020 23:45:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-30 20:42:04.393146
- Title: Quantum soundness of the classical low individual degree test
- Title（参考訳）: 古典的低次個別度テストの量子健全性
- Authors: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
- Abstract要約: 低次検定と呼ばれる低次検定の変種を解析する。
私たちの主な結果は、このテストの2人プレイヤバージョンが、量子プローバーに対するサウンドであることです。
- 参考スコア（独自算出の注目度）: 9.42581332803306
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Low degree tests play an important role in classical complexity theory,
serving as basic ingredients in foundational results such as $\mathsf{MIP} =
\mathsf{NEXP}$ [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten
years, versions of these tests which are sound against quantum provers have
found increasing applications to the study of nonlocal games and the complexity
class~$\mathsf{MIP}^*$. The culmination of this line of work is the result
$\mathsf{MIP}^* = \mathsf{RE}$ [arXiv:2001.04383]. One of the key ingredients
in the first reported proof of $\mathsf{MIP}^* = \mathsf{RE}$ is a two-prover
variant of the low degree test, initially shown to be sound against multiple
quantum provers in [arXiv:1302.1242]. Unfortunately a mistake was recently
discovered in the latter result, invalidating the main result of
[arXiv:1302.1242] as well as its use in subsequent works, including
[arXiv:2001.04383]. We analyze a variant of the low degree test called the low
individual degree test. Our main result is that the two-player version of this
test is sound against quantum provers. This soundness result is sufficient to
re-derive several bounds on~$\mathsf{MIP}^*$ that relied on [arXiv:1302.1242],
including $\mathsf{MIP}^* = \mathsf{RE}$.
- Abstract（参考訳）: 低次テストは古典的複雑性理論において重要な役割を果たし、$\mathsf{MIP} = \mathsf{NEXP}$ [BFL91] や PCP の定理 [AS98,ALM+98] のような基礎的な結果の基本的な材料として機能する。
この10年間で、量子プローバーに対して健全なこれらのテストのバージョンは、非局所ゲームや複雑性クラス—$\mathsf{MIP}^*$の研究への応用が増加している。
この一連の研究の成果は、$\mathsf{mip}^* = \mathsf{re}$ [arxiv:2001.04383] である。
最初に報告された「$\mathsf{MIP}^* = \mathsf{RE}$」の証明の鍵となる要素の1つは、[arXiv:1302.1242] における複数の量子プローバーに対して音であることを示す低次検定の2つの証明である。
残念ながら、後者の結果に誤りが発見され、 [arxiv:1302.1242] の主な結果と [arxiv:2001.04383] を含むその後の作品での使用を無効にした。
低次テスト(low individual degree test)と呼ばれる低次テストの変種を分析した。
私たちの主な結果は、このテストの2つのプレイヤーバージョンが量子プローバーに対する音であることです。
この健全性の結果は [arXiv:1302.1242] に依存する~$\mathsf{MIP}^*$ 上のいくつかの境界を導出するのに十分であり、$\mathsf{MIP}^* = \mathsf{RE}$ を含む。
関連論文リスト
- Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
本稿では,一元性検定における量子クエリの下位境界を証明するための新しい手法を提案する。
すべての得られる下限は$mathsfC$-testerで$mathsfC subseteq mathsfQMA(2)/mathsfqpoly$である。
我々は、$mathsfQMA(2) notsupset mathsfSBQP$と$mathsfQMA/mathsfqpolyの量子オラクルが存在することを示した。
論文 参考訳（メタデータ） (2024-01-15T19:00:36Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳（メタデータ） (2024-01-03T09:12:25Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳（メタデータ） (2024-01-02T22:25:56Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - On the complexity of zero gap MIP* [0.11470070927586014]
クラス $mathsfMIP*$ が $mathsfRE$ に等しいことを示す。
特にこのことは、非局所ゲーム$G$の量子値の近似の複雑さがハルティング問題の複雑性と同値であることを示している。
論文 参考訳（メタデータ） (2020-02-24T19:11:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。