論文の概要: Separating ClonableQMA and QCMA Relative to a Classical Oracle

• arxiv url: http://arxiv.org/abs/2610.06740v1
• Date: Mon, 05 Oct 2026 17:21:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 23:16:53.34238
• Title: Separating ClonableQMA and QCMA Relative to a Classical Oracle
• Title（参考訳）: ClonableQMAとQCMAを分離する - 古典的なOracle
• Abstract要約: クローン可能な量子証明でさえ、古典的なオラクルと比較して、古典的な証明よりも強力であることを示す。 また、BQP/clonableqpolyとBQP/polyを古典的に分離し、量子暗号への結果の適用について述べる。
• 参考スコア（独自算出の注目度）: 2.7182326722409376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Since the introduction of the complexity class QMA as a quantum-verifier analogue of NP (Kitaev, 1997), many have wondered whether quantum proofs are necessary or classical proofs suffice - that is, whether QMA = QCMA or QCMA != QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07). This longstanding question was recently answered by works of Bostanci, Haferkamp, Nirkhe, and Zhandry (STOC '26) and Bostanci, Huang, and Vaikuntanathan (FOCS '26), which showed that quantum proofs are more powerful than classical ones in the classical-oracle setting. However, it remains unclear what exactly makes quantum proofs more powerful than classical ones. In the information-theoretic setting, a family of quantum states is not classicalizable if and only if it is unclonable. Indeed, these recent works also explicitly highlight the unclonability of their quantum proofs as a key mechanism behind their separations, and their arguments crucially rely on this property. This raises the question of whether unclonability is necessary for quantum proofs to be more powerful than classical ones. In this work, we show that even clonable quantum proofs can be more powerful than classical ones relative to a classical oracle by constructing a classical oracle O such that QCMA^O != ClonableQMA^O. This resolves the open question of Nehoran and Zhandry (ITCS '24), who established the analogous separation relative to a quantum oracle. We also show a classical-oracle separation between BQP/clonableqpoly and BQP/poly, and give applications of our results to quantum cryptography.
• Abstract（参考訳）: 複雑性クラス QMA が NP (Kitaev, 1997) の量子検証類似体として導入されて以来、多くの人は量子証明が必要か古典的証明が十分か、つまり QMA = QCMA か QCMA かを疑問視してきた。 QMA (Aharonov and Naveh, 2002; Aaronson and Kuperberg, CCC '07)。 この長年にわたる疑問は、ボスタンチ、ハファーカンプ、ニールケ、ザンドリー(STOC '26)、ボスタンチ、フアン、ヴァイクンタナサン(FOCS '26)の研究によって、古典的なオーラクル設定の量子証明よりも強力であることが示されている。 しかし、なぜ量子証明が古典的証明よりも強力になるのかは定かではない。 情報理論的な設定では、量子状態の族が古典化不可能であることと、それが制限不能であることは同値である。 実際、これらの最近の研究は、それらの分離の背後にある重要なメカニズムとして量子証明の不連続性を強調しており、それらの議論はこの性質に決定的に依存している。 このことは、量子証明が古典的証明よりも強力であるためには非閉性が必要であるかどうかという問題を提起する。 本研究では、古典的なオラクル O を QCMA^O のような古典的なオラクル O を構成することにより、クローン可能な量子証明でさえ、古典的なオラクルと比較してより強力であることを示す。 = ClonableQMA^O。 これにより、ネホランとザンドリー(ITCS '24)の開問題が解決され、量子オラクルに対する類似の分離が確立された。 また、BQP/clonableqpolyとBQP/polyを古典的に分離し、量子暗号への結果の適用について述べる。

関連論文リスト

• A Cautionary Note on Quantum Oracles [0.0]
  量子オラクル問題はQMAクラスに含まれるが、ポリQCPHクラスには含まれないことを示す。 また、同じ分離が、ナタラジャンとニクヘ(2024年)によって導入されたモデルである分布オラクルに対して成り立つことを示す。
  論文  参考訳（メタデータ） (2025-04-28T04:20:39Z)
• Kochen-Specker for many qubits and the classical limit [55.2480439325792]
  量子および古典予測は、量子ビットの数がマクロスケールに増加するにつれて収束することが示されている。 古典的極限を説明するこの方法は、以前にGHZ状態に対して報告された結果と一致し、改善する。
  論文  参考訳（メタデータ） (2024-11-26T22:30:58Z)
• Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle [10.063768056247591]
  BQP/qpoly $neq$BQP/poly および QMA $neq$QCMA の古典的アクセス可能な古典的オラクルを構築する。 ここでは、古典的アクセス可能な古典的オラクルは、量子アルゴリズムでさえも古典的にのみアクセス可能なオラクルである。
  論文  参考訳（メタデータ） (2023-03-08T00:30:07Z)
• 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)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)

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

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