論文の概要: Separating QMA from QCMA with a classical oracle

• arxiv url: http://arxiv.org/abs/2511.09551v1
• Date: Thu, 13 Nov 2025 02:01:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-13 22:34:54.619556
• Title: Separating QMA from QCMA with a classical oracle
• Title（参考訳）: 古典的オラクルを用いたQCMAとQMAの分離
• Authors: John Bostanci, Jonas Haferkamp, Chinmay Nirkhe, Mark Zhandry,
• Abstract要約: 量子証人(QMA)を持つ効率的な量子検証器によって決定可能な言語群は、古典的証人(QCMA)にのみアクセス可能な言語群よりも厳密に大きいことを証明した古典的オラクルを構築した。 我々は、ボソンの観点で問題を表現することによって、オラクルへの量子アクセスを圧縮できることを観察する。
• 参考スコア（独自算出の注目度）: 8.15122567803892
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries. Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.
• Abstract（参考訳）: 我々は、量子証人(QMA)を持つ効率的な量子検証器によって決定可能な言語の集合が、古典的証人(QCMA)にのみアクセス可能な言語よりも厳密に大きいことを証明した古典的オラクルを構築した。 我々が構成する古典的オラクルの分離は、スペクトルForrelation(英語版)という決定問題のためのものである -- オラクルはブールハイパーキューブの2つのサブセットを記述し、計算タスクは、標準基底測定分布が1つのサブセットで十分にサポートされている量子状態が存在するかどうかを判断することである。これは、そのフーリエ基底測定分布が他のサブセットで十分にサポートされている一方で、そのフーリエ基底測定分布が他のサブセットでサポートされている。これは、メンバーシップクエリを通してアクセス可能な2つのセットの間の「Forrelation」行列のスペクトルノルムを推定することと等価である。我々の下限境界は、古典的な目撃者によるクエリアルゴリズムが、分布から多くのサンプルを複数回生成できるという単純な観察から導かれる。一方、量子目撃者は「1回」のオブジェクトである。この観察により、QCMAが同時に厳しいサンプリングを下限に抑えることを証明することができる。 サンプリング問題に対するこの圧縮された視点を用いて、サンプリング硬度の結果を証明し、その証明を完成させる。

関連論文リスト

• Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity [0.0]
  1つの量子サンプル(サブセットの要素上の一様重ね合わせの1つのコピー)のみを使用する単純な量子アルゴリズムを提供する。 サンプル対サンプルの設定では、量子計算は古典的な計算よりも最も大きな分離を達成できる。
  論文  参考訳（メタデータ） (2025-02-12T19:00:10Z)
• Toward Separating QMA from QCMA with a Classical Oracle [10.699704508276174]
  QMAは効率的な量子検証器によって決定できる言語のクラスであり、QCMAは効率的な量子検証器が古典的な証人しか与えられない言語のクラスである。 量子クエリ複雑性における挑戦的な基本的なゴールは、これらのクラスに対する古典的なオラクル分離を見つけることである。
  論文  参考訳（メタデータ） (2024-11-04T00:18:06Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• Learning unitaries with quantum statistical queries [0.0]
  量子統計的クエリからユニタリ演算子を学習するためのアルゴリズムをいくつか提案する。 量子統計的クエリを利用して、パウリ弦の部分集合上のユニタリのフーリエ質量を推定する。 量子統計クエリーは、様々なユニタリ学習タスクに統一的なフレームワークを提供することを示す。
  論文  参考訳（メタデータ） (2023-10-03T17:56:07Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• 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)
• Quantum Oracle Separations from Complex but Easily Specified States [1.52292571922932]
  量子オラクル (quantum oracle) は、量子計算中に呼び出し可能なブラックボックスである。 私たちは、タスクの複雑さの分離を維持しながら、古典的に簡単に指定できるようにマークされた状態を制約します。 古典的に定義されたオラクルは、量子アルゴリズムがステップ内の他のハードな状態を準備できるという事実を利用して、重出力サンプリングにおいて量子古典的なオラクル分離を観察する。
  論文  参考訳（メタデータ） (2021-04-15T05:40:38Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  パウリの誤差は、多数の現実的な量子チャネルの中で最も低いサンプリングオーバーヘッドをもたらすことを示す。 我々はQEMと量子チャネル符号化を併用する手法を考案し、純粋なQEMと比較してサンプリングオーバーヘッドの低減を解析する。
  論文  参考訳（メタデータ） (2020-12-15T15:51:27Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  本稿では、量子誤り訂正符号の品質と、論理ゲートの普遍的な集合を達成する能力とを結びつける、近似したイージン・クニル定理の証明を示す。 我々の導出は、一般的な量子気象プロトコルにおける量子フィッシャー情報に強力な境界を用いる。
  論文  参考訳（メタデータ） (2020-04-24T17:58:10Z)

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

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