論文の概要: En Route to a Standard QMA1 vs. QCMA Oracle Separation
- arxiv url: http://arxiv.org/abs/2604.26921v1
- Date: Wed, 29 Apr 2026 17:38:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-30 15:59:36.522527
- Title: En Route to a Standard QMA1 vs. QCMA Oracle Separation
- Title（参考訳）: 標準QMA1 vs. QCMA Oracle分離への道
- Authors: David Miloschewsky, Supartha Podder, Dorian Rudolph,
- Abstract要約: 我々は完全性の下で量子証人の力を研究する。
言語が$mathsfQMA$にあるが$mathsfQCMA$ではない古典的なオラクルを構築する。
- 参考スコア（独自算出の注目度）: 0.25489046505746704
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in $\mathsf{QMA}_1$ but not in $\mathsf{QCMA}$ when the $\mathsf{QCMA}$ verifier is only allowed polynomially many adaptive rounds and exponentially many parallel queries per round. Additionally, we derandomize the permutation-oracle separation of Fefferman and Kimmel, obtaining an in-place oracle separation between $\mathsf{QMA}_1$ and $\mathsf{QCMA}$. Furthermore, we focus on $\mathsf{QCMA}$ and $\mathsf{QMA}$ with an exponentially small gap, where we show a separation assuming the gap is fixed, but not when it may be arbitrarily small. Finally, we derive consequences for approximate ground-state preparation from sparse Hamiltonian oracle access, including a bounded-adaptivity frustration-free variant.
- Abstract（参考訳）: 我々は完全性の下で量子証人の力を研究する。
我々は、言語が$\mathsf{QMA}_1$にあるが、$\mathsf{QCMA}$でない古典的なオラクルを構築する。
さらに、Fefferman と Kimmel の置換オークル分離をデランドマイズし、$\mathsf{QMA}_1$ と $\mathsf{QCMA}$ の配置のオラクル分離を得る。
さらに、指数的に小さなギャップを持つ $\mathsf{QCMA}$ と $\mathsf{QMA}$ にフォーカスする。
最後に, 境界適応型フラストレーションフリーな変種を含む, スパースハミルトニアンのオラクルアクセスから, 近似基底状態生成の結果を導出する。
関連論文リスト
- Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning [51.820005667020354]
有限状態と作用空間を持つ平均回帰型MDPに対して、弱い通信仮定の下で、単純だが効果的なQ-ラーニングアルゴリズムについて検討する。
We proof that the collaborations the per-agent sample complexitys to $widetildeOleft(frac|mathcalA||hstar|_mathsfsp3Mvarepsilon3right)$, with only $widetildeOleft(frac|hstar|_mathsfsp3Mvareps)。
論文 参考訳（メタデータ） (2026-01-20T06:21:54Z) - Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。
効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。
また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文 参考訳（メタデータ） (2025-02-25T19:08:26Z) - QMA vs. QCMA and Pseudorandomness [5.483786291093505]
そのようなオラクルは、ある量子擬ランダム性予想が成立するときに存在することを示す。
私たちの結果は、"Win-win"シナリオの確立と見なすことができます。
論文 参考訳（メタデータ） (2024-11-21T18:50:12Z) - Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - A distribution testing oracle separation between QMA and QCMA [0.6144680854063939]
量子複雑性理論において、$textitnon-deterministic$ 量子計算の定義が量子証人を必要とするかどうかという長い議論である。
本稿では,各計算複雑性クラスを分離したランダム化された古典オラクルを構築することにより,この問題を進展させる。
論文 参考訳（メタデータ） (2022-10-27T12:43:56Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。