論文の概要: The status of the quantum PCP conjecture (games version)

• arxiv url: http://arxiv.org/abs/2403.13084v1
• Date: Tue, 19 Mar 2024 18:30:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-21 18:56:56.757303
• Title: The status of the quantum PCP conjecture (games version)
• Title（参考訳）: 量子PCP予想(ゲーム版)の現状
• Authors: Anand Natarajan, Chinmay Nirkhe,
• Abstract要約: 多重対数的に長いメッセージを持つ多目的対話型証明システムはREにおける任意の決定問題を解くことができることを示す。 本稿では,(1)標準AM完全問題に対する効率的なプロバーを用いた簡潔なMIP*プロトコルを新たに構築し,(2)ナタラジャンとヴィディックのエネルギー増幅手順における誤差を説明する。
• 参考スコア（独自算出の注目度）: 0.6144680854063939
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In classical complexity theory, the two definitions of probabilistically checkable proofs -- the constraint satisfaction and the nonlocal games version -- are computationally equal in power. In the quantum setting, the situation is far less clear. The result MIP* = RE of Ji et. al. (arXiv:2001.04383) and refinements by Natarajan and Zhang (arXiv:2302.04322) show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE, including undecidable problems like the halting problem. These results show that any connection between the "constraint satisfaction" or "Hamiltonian" quantum PCP conjecture and nonlocal games must involve restricting the players in the game to be computationally efficient. This note contains two main results: (1) we give a "quantum games PCP for AM" in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick (arXiv:1710.03062) which invalidates their claim to have constructed a quantum games PCP for a QMA-complete problem. In surveying the obstacles remaining towards a quantum games PCP for QMA, we highlight the importance and challenge of understanding gap amplification for Hamiltonians even when locality is replaced by much weaker constraints, such as bounds on the "Pauli spectrum" of the Hamiltonian. We hope these questions will motivate progress towards new "baby versions" of Hamiltonian quantum PCP conjecture.
• Abstract（参考訳）: 古典的複雑性理論において、確率論的に検証可能な証明(制約満足度と非局所ゲームバージョン)の2つの定義は計算量的に同じである。 量子環境では、状況ははるかに明確ではない。 MIP* = RE of Ji et al (arXiv:2001.04383) と、Natarajan と Zhang (arXiv:2302.04322) による改良により、多対数長のメッセージを持つ多目的対話型証明システムは、停止問題のような決定不能な問題を含むREのあらゆる問題を解決することができることを示した。 これらの結果は、「制約満足度」あるいは「ハミルトニアン」量子PCP予想と非局所ゲームとの間の関係は、ゲーム内のプレイヤーを計算的に効率よく制限する必要があることを示している。 本稿では,(1)標準AM完全問題に対する効率的なプロバーを備えた簡潔なMIP*プロトコルを新たに構築し,(2)ナタラジャンとヴィディックのエネルギー増幅手順における誤りを説明する(arXiv:1710.03062)。 量子ゲームPCP for QMA の障害を調査する際には、局所性がハミルトンの「パウリスペクトル」上の境界のようなより弱い制約に置き換わる場合でも、ハミルトニアンにとってギャップ増幅を理解することの重要性と課題を強調した。 これらの疑問がハミルトン量子PCP予想の新しい「ベイビーバージョン」への進展を動機づけることを願っている。

関連論文リスト

• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
  非適応型量子PCPは、証明クエリ数が一定である場合に適応型量子PCPをシミュレートできることを示す。 また、ある量子PCPステートメントが偽であるような(量子)オラクルが存在することも示している。
  論文  参考訳（メタデータ） (2024-03-07T19:00:06Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture [0.0]
  我々は最近定義されたガイドド局所ハミルトン問題における「マーリン化」バージョンについて検討する。 これらの問題には、入力の一部として提供される指針状態はなく、単に存在するという約束が伴うだけである。 誘導状態の両クラスに対する誘導可能な局所ハミルトン問題は、逆多項式の精度設定において$mathsfQCMA$-completeであることを示す。
  論文  参考訳（メタデータ） (2023-02-22T19:00:00Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Commitments to Quantum States [11.217084610985674]
  コミットフェーズの後、コミットした状態が送信者の視点から隠されている場合、量子メッセージへのコミットが結合される。 量子状態コミットメント(QSC)の隠蔽は、古典的なメッセージに対するコミットメントスキームによってもたらされることを示す。 量子状態へのコミットは多くの新しい暗号可能性への扉を開く。
  論文  参考訳（メタデータ） (2022-10-11T04:34:36Z)
• Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [0.0]
  サビッチの定理は、NPSPACE計算はPSPACEでシミュレートできると述べている。 SQCMASPACE=NEXP のように、サビッチの定理の量子アナログが成り立たないことを示す。 SQCMASPACE を[Chailloux, Sattath, 2012] のスパース分離ハミルトン問題に組み込む方法を示す (QMA(2)-complete for 1/poly promise gap)。
  論文  参考訳（メタデータ） (2022-06-10T17:35:10Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  パラメータ化量子回路で完了した2プレーヤゼロサムゲームとして,両部絡み検出を再構成する。 このプロトコルを線形光ネットワーク上で実験的に実装し、5量子量子純状態と2量子量子混合状態の両部絡み検出に有効であることを示す。
  論文  参考訳（メタデータ） (2022-03-15T09:46:45Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。