論文の概要: The Complexity of Stoquastic Sparse Hamiltonians
- arxiv url: http://arxiv.org/abs/2605.02845v1
- Date: Mon, 04 May 2026 17:22:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-05 20:33:50.43
- Title: The Complexity of Stoquastic Sparse Hamiltonians
- Title（参考訳）: 確率スパースハミルトニアンの複素性
- Authors: Alex B. Grilo, Marios Rozos,
- Abstract要約: 確率スパースハミルトン問題(mathsfStoqSH$)が$mathsfStoqMA$であることを示す。
Stoquastic Local Hamiltonian は $mathsfStoqMA$-hard であるため、$mathsfStoqSH$ は $mathsfStoqMA$-complete となる。
また、$mathsfStoqMA(2)$の分離可能なバージョンが$mathsfStoqMAであることも示します。
- 参考スコア（独自算出の注目度）: 0.30079490585515334
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Despite having an unnatural definition, $\mathsf{StoqMA}$ plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of $\mathsf{NP}$, $\mathsf{MA}$ and $\mathsf{AM}$. Therefore, understanding the exact power of $\mathsf{StoqMA}$ (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem ($\mathsf{StoqSH}$) is in $\mathsf{StoqMA}$. Since Stoquastic Local Hamiltonians are $\mathsf{StoqMA}$-hard, this implies that $\mathsf{StoqSH}$ is $\mathsf{StoqMA}$-complete. We complement this result by showing that the separable version of $\mathsf{StoqSH}$ is $\mathsf{StoqMA}(2)$-complete, where $\mathsf{StoqMA}(2)$ is the version of $\mathsf{StoqMA}$ that receives two unentangled proofs.
- Abstract（参考訳）: 不自然な定義があるにもかかわらず、$\mathsf{StoqMA}$は、カヴィットとモンタナロによるハミルトンの複雑性の分類定理(SICOMP 2016)において、ハミルトンの複雑性において中心的な役割を果たす。
さらに、これは、$\mathsf{NP}$, $\mathsf{MA}$と$\mathsf{AM}$の2つのランダム化された拡張の間にある。
したがって、$\mathsf{StoqMA}$の正確なパワーを理解する(そしてより自然な複雑性クラスと折り畳むことを願う)ことは、異なる理由から非常に興味深い。
本研究では、StoqSH}$(StoqSH}$)が$\mathsf{StoqMA}$(StoqSH}$)であることを示すことによって、この複雑性クラスを理解するための一歩を踏み出した。
確率的局所ハミルトニアンは$\mathsf{StoqMA}$-hardであるため、$\mathsf{StoqSH}$は$\mathsf{StoqMA}$-completeである。
この結果を補完するために、$\mathsf{StoqSH}$の分離版が$\mathsf{StoqMA}(2)$-completeであることを示す。
関連論文リスト
- Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape [0.2864713389096699]
私たちは$mathsfCorrBQP$が$mathsfBPPmathsfPP$と全く同じであることを示す。
また、$mathsfCorrBQP$は古典的なクエリに関して自己低であることを示す。
論文 参考訳（メタデータ） (2025-07-04T16:21:45Z) - On the Complexity of Pure-State Consistency of Local Density Matrices [0.0]
我々は、Aharanov と Regev [FOCS 2003] の複雑性クラス QMA+ の純粋状態類似体を定義し、PureSuperQMA と呼ぶ。
2-qubit還元密度行列の硬さを証明し、混合N-表現性はQMA完全であることを示す。
我々はこれを、PureCLDMがQMA(2)完全かどうかという長年の未解決問題に対する否定的な答えの証拠とみなす。
論文 参考訳（メタデータ） (2024-11-05T13:43:21Z) - Quantum Sabotage Complexity [0.7812210699650152]
ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
論文 参考訳（メタデータ） (2024-08-22T17:57:58Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。
この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
論文 参考訳（メタデータ） (2023-06-22T17:23:36Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。