The Complexity of Stoquastic Sparse Hamiltonians

• URL: http://arxiv.org/abs/2605.02845v1
• Date: Mon, 04 May 2026 17:22:02 GMT
• Title: The Complexity of Stoquastic Sparse Hamiltonians
• Abstract summary: We show that the Stoquastic Sparse Hamiltonians problem ($mathsfStoqSH$) is in $mathsfStoqMA$.<n>Since Stoquastic Local Hamiltonians are $mathsfStoqMA$-hard, this implies that $mathsfStoqSH$ is $mathsfStoqMA$-complete.<n>We also show that the separable version of $mathsfStoqMA(2)$ is $mathsfStoqMA
• Score: 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.

Related papers

• Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs [0.0]
  We study gap amplification of the class $mathsfQMA+(2)$ characterized by unentangled quantum proofs.<n>Our proof combines symmetric-subspace projections with the relation $mathsfQMA+(1)=mathsfNEXP$ of Bassirian, Fefferman, and Marwaha.
  arXiv  Detail & Related papers  (2026-08-08T07:45:56Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape [0.2864713389096699]
  We show that $mathsfCorrBQP$ is exactly equal to $mathsfBPPmathsfPP$.<n>We also show that $mathsfCorrBQP$ is self-low with respect to classical queries.
  arXiv  Detail & Related papers  (2025-07-04T16:21:45Z)
• On the Complexity of Pure-State Consistency of Local Density Matrices [0.0]
  We define a pure state analogue of the complexity class QMA+ of Aharanov and Regev [FOCS 2003], which we call PureSuperQMA.<n>We prove hardness for 2-qubit reduced density matrices and showing that mixed N-Representability is QMA-complete.<n>We view this as evidence for a negative answer to the longstanding open question whether PureCLDM is QMA(2)-complete.
  arXiv  Detail & Related papers  (2024-11-05T13:43:21Z)
• Towards a universal gateset for $\mathsf{QMA}_1$ [0.0]
  We prove that for all gatesets in the cyclotomic field $mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$, $G_2k$ is universal for all gatesets in $mathbbQ(zeta_2k),zeta_2k=e2pi i/2k$.<n>We also prove that the Gapped Clique Homology problem defined by King
  arXiv  Detail & Related papers  (2024-11-04T23:39:27Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  We show $mathsfQ(f_mathsfsab)$, the quantum query complexity of $f_mathsfsab$. We show that when $f$ is the Indexing function, $mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$, ruling out the possibility that $mathsfQ(f_mathsfsab)=Theta(sqrtmathsf
  arXiv  Detail & Related papers  (2024-08-22T17:57:58Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  We focus on learning mixtures of separated Gaussians on $mathbbRd$ of the form $P= sum_i=1k w_i mathcalN(boldsymbol mu_i,mathbf Sigma_i)$. We prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least $dOmega (1/epsilon)$.
  arXiv  Detail & Related papers  (2023-06-22T17:23:36Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• StoqMA meets distribution testing [0.0]
  We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits. We show that both variants of $mathsfStoqMA$ that without any ancillary random bit and with perfect soundness are contained in $mathsfNP$. Our results make a step towards collapsing the hierarchy $mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06], in which all classes are contained in $
  arXiv  Detail & Related papers  (2020-11-11T12:30:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.