論文の概要: The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
- arxiv url: http://arxiv.org/abs/2402.18790v1
- Date: Thu, 29 Feb 2024 01:35:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-01 16:22:17.338416
- Title: The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
- Title（参考訳）: 非負振幅をもつ無絡量子証明のパワー
- Authors: Fernando Granha Jeronimo and Pei Wu
- Abstract要約: 非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
- 参考スコア（独自算出の注目度）: 55.90795112399611
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum entanglement is a fundamental property of quantum mechanics and plays
a crucial role in quantum computation and information. We study entanglement
via the lens of computational complexity by considering quantum generalizations
of the class NP with multiple unentangled quantum proofs, the so-called QMA(2)
and its variants. The complexity of QMA(2) is a longstanding open problem, and
only the trivial bounds QMA $\subseteq$ QMA(2) $\subseteq$ NEXP are known.
In this work, we study the power of unentangled quantum proofs with
non-negative amplitudes, a class which we denote $\text{QMA}^+(2)$. In this
setting, we are able to design proof verification protocols for problems both
using logarithmic size quantum proofs and having a constant probability gap in
distinguishing yes from no instances. In particular, we design global protocols
for small set expansion, unique games, and PCP verification. As a consequence,
we obtain NP $\subseteq \text{QMA}^+_{\log}(2)$ with a constant gap. By virtue
of the new constant gap, we are able to ``scale up'' this result to
$\text{QMA}^+(2)$, obtaining the full characterization $\text{QMA}^+(2)$=NEXP
by establishing stronger explicitness properties of the PCP for NEXP.
One key novelty of these protocols is the manipulation of quantum proofs in a
global and coherent way yielding constant gaps. Previous protocols (only
available for general amplitudes) are either local having vanishingly small
gaps or treat the quantum proofs as classical probability distributions
requiring polynomially many proofs thereby not implying non-trivial bounds on
QMA(2).
Finally, we show that QMA(2) is equal to $\text{QMA}^+(2)$ provided the gap
of the latter is a sufficiently large constant. In particular, if
$\text{QMA}^+(2)$ admits gap amplification, then QMA(2)=NEXP.
- Abstract（参考訳）: 量子絡み合いは量子力学の基本的な性質であり、量子計算と情報において重要な役割を果たす。
計算複雑性のレンズによる絡み合いを、複数の非絡み合い量子証明を持つクラスNPの量子一般化、いわゆるQMA(2)とその変種を考慮して検討する。
QMA(2) の複雑さは長年の開問題であり、自明な境界 QMA $\subseteq$ QMA(2) $\subseteq$ NEXP のみが知られている。
本研究では、非負の振幅を持つ非絡み合った量子証明のパワー、すなわち $\text{QMA}^+(2)$ を表わすクラスについて研究する。
この設定では、対数サイズの量子証明と、yesとnoインスタンスの区別において一定の確率ギャップを持つ問題に対する証明検証プロトコルを設計することができる。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
その結果、定数ギャップを持つNP $\subseteq \text{QMA}^+_{\log}(2)$を得る。
新しい定数ギャップにより、この結果が $\text{QMA}^+(2)$ となり、 NEXP の PCP のより強い明示性特性を確立することにより、フル特徴づけ $\text{QMA}^+(2)$=NEXP が得られる。
これらのプロトコルの重要な新しさの1つは、一定ギャップを与える大域的かつコヒーレントな方法での量子証明の操作である。
以前のプロトコル(一般的な振幅でのみ使用可能)は局所的に小さなギャップを持つか、量子証明を多項式的に多くの証明を必要とする古典的確率分布として扱うかのいずれかであり、qma(2) 上の非自明な境界を含まない。
最後に、qma(2) が$\text{qma}^+(2)$ に等しいことを示す。
特に、$\text{qma}^+(2)$ がギャップ増幅を許すなら、qma(2)=nexp である。
関連論文リスト
- Complexity Theory for Quantum Promise Problems [5.049812996253858]
本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。
複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。
我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
論文 参考訳（メタデータ） (2024-11-06T07:29:52Z) - Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local
Hamiltonians [0.0]
非適応型量子PCPは、証明クエリ数が一定である場合に適応型量子PCPをシミュレートできることを示す。
また、ある量子PCPステートメントが偽であるような(量子)オラクルが存在することも示している。
論文 参考訳（メタデータ） (2024-03-07T19:00:06Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳（メタデータ） (2022-06-29T22:19:12Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Quantum Proofs of Proximity [6.160793572747927]
近接検定のQMA証明は古典的近接検定や量子検定よりも指数関数的に強いことを示す。
この結果には、表現力のある特性のクラスをテストするための量子スピードアップを可能にするアルゴリズムフレームワークが含まれている。
また、このファミリーの外部にある特性であるグラフ双分極性をテストするためのQMAアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-08T13:15:30Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。