論文の概要: The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
- arxiv url: http://arxiv.org/abs/2609.38957v1
- Date: Wed, 30 Sep 2026 04:23:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:27.183374
- Title: The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
- Title（参考訳）: 地域ハミルトニアン問題:BQP-ハードネスに対する相対的証拠
- Abstract要約: 可換な局所ハミルト問題(英語版)は局所ハミルト問題(英語版)の制限である。
一般の CLH 問題の可能性に対する公式な証拠は、$mathsfQMA$-complete ではない。
- 参考スコア（独自算出の注目度）: 8.438148845727445
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The commuting local-Hamiltonian (CLH) problem is a restriction of the local-Hamiltonian problem, in which the terms of the Hamiltonian are required to pairwise commute. A long line of work has shown that the problem lies in $\mathsf{NP}$ for certain families of commuting local Hamiltonians. Nevertheless, there has been no formal evidence against the possibility that the general CLH problem is $\mathsf{QMA}$-complete. CLH is complete for the complexity class $\mathsf{QIMA}$, defined through quantum verifiers whose local gates commute. Therefore, CLH is $\mathsf{QMA}$-complete if and only if $\mathsf{QIMA}=\mathsf{QMA}$. In this work, we introduce a classical-oracle analogue $\mathsf{QIMA}^{\mathcal{O}}$ and construct a classical oracle $\mathcal{O}$ such that $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$. Since $\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this implies $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle. Thus, our result provides relativized evidence against the possibility that the general commuting local-Hamiltonian problem is $\mathsf{BQP}$-hard, and hence also against the possibility that it is $\mathsf{QMA}$-complete.
- Abstract（参考訳）: 通勤局所ハミルトニアン問題(英: commuting local-Hamiltonian problem、CLH)は、ハミルトニアンの項が相互に通勤するために必要となる局所ハミルトニアン問題の制限である。
長い研究の行は、局所ハミルトニアンを通勤するある種の族に対して、問題は$\mathsf{NP}$にあることを示した。
それでも、一般の CLH 問題は $\mathsf{QMA}$-complete である可能性に対する公式な証拠は存在しない。
CLH は、局所ゲートが可換である量子検証器によって定義される複雑性クラス $\mathsf{QIMA}$ に対して完備である。
したがって、CLH が $\mathsf{QMA}$-完全であることと $\mathsf{QIMA}=\mathsf{QMA}$ であることは同値である。
本研究では、古典的オラクル類似体 $\mathsf{QIMA}^{\mathcal{O}}$ を導入し、古典的オラクル $\mathcal{O}$ を $\mathsf{BQP}^{\mathcal{O}}\not\subseteq\mathsf{QIMA}^{\mathcal{O}}$ とする。
$\mathsf{BQP}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$ for any classical oracle $\mathcal{O}$, this suggests $\mathsf{QIMA}^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ for our constructed oracle.
したがって、この結果は局所-ハミルトン問題の一般可換化が$\mathsf{BQP}$-hardである可能性、従って$\mathsf{QMA}$-completeである可能性に対する相対的な証拠を提供する。
関連論文リスト
- The Complexity of Stoquastic Sparse Hamiltonians [0.30079490585515334]
確率スパースハミルトン問題(mathsfStoqSH$)が$mathsfStoqMA$であることを示す。
Stoquastic Local Hamiltonian は $mathsfStoqMA$-hard であるため、$mathsfStoqSH$ は $mathsfStoqMA$-complete となる。
また、$mathsfStoqMA(2)$の分離可能なバージョンが$mathsfStoqMAであることも示します。
論文 参考訳（メタデータ） (2026-05-04T17:22:02Z) - On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。
以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
論文 参考訳（メタデータ） (2026-01-06T18:34:07Z) - Towards verifications of Krylov complexity [0.0]
私は16の量子力学系のモーメントの完全かつ明示的な表現をSchr"odinger と Heisenberg の両方で正確に解けるように提示する。
論文 参考訳（メタデータ） (2024-03-11T02:57:08Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳（メタデータ） (2021-12-14T16:29:53Z) - The Acrobatics of BQP [1.7136832159667206]
量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
論文 参考訳（メタデータ） (2021-11-19T19:40:05Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - StoqMA meets distribution testing [0.0]
We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。
いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。
我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
論文 参考訳（メタデータ） (2020-11-11T12:30:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。