pith. machine review for the scientific record. sign in

arxiv: 2605.02845 · v1 · submitted 2026-05-04 · 💻 cs.CC · quant-ph

Recognition: unknown

The Complexity of Stoquastic Sparse Hamiltonians

Alex B. Grilo , Marios Rozos
Authors on Pith no claims yet

Pith reviewed 2026-05-08 01:40 UTC · model grok-4.3

classification 💻 cs.CC quant-ph
keywords stoquastic HamiltoniansStoqMAHamiltonian complexitysparse Hamiltoniansquantum Merlin-ArthurStoqMA(2)ground-state energypromise problems
0
0 comments X

The pith

The Stoquastic Sparse Hamiltonians problem is StoqMA-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that deciding the ground-state energy of a stoquastic sparse Hamiltonian belongs to StoqMA, the quantum Merlin-Arthur class for stoquastic systems. Because the local version of the problem is already StoqMA-hard, the sparse version is therefore StoqMA-complete. This places sparse and local stoquastic Hamiltonians at the same level of complexity. The work also proves that the version restricted to separable proofs is complete for the two-unentangled-proof class StoqMA(2).

Core claim

We show that the Stoquastic Sparse Hamiltonians problem (StoqSH) is in StoqMA. Since Stoquastic Local Hamiltonians are StoqMA-hard, this implies that StoqSH is StoqMA-complete. We complement this result by showing that the separable version of StoqSH is StoqMA(2)-complete.

What carries the argument

The StoqSH decision problem together with a StoqMA verification protocol whose reduction from the local case preserves the stoquastic sign structure and the promise gap.

If this is right

  • Local and sparse stoquastic Hamiltonians have identical complexity status under StoqMA.
  • StoqMA is the exact class capturing the verification power of stoquastic Hamiltonian problems.
  • The separable variant requires exactly two unentangled proofs to achieve completeness in StoqMA(2).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If StoqMA collapses to MA, then both sparse and local stoquastic Hamiltonian problems would lie in MA.
  • Sparsity alone does not weaken the proof-verification requirements for stoquastic Hamiltonians.
  • Similar completeness results may extend to other restricted interaction graphs that still admit a stoquastic-preserving reduction.

Load-bearing premise

Any reduction or protocol that places StoqSH inside StoqMA must preserve both the stoquastic property of the Hamiltonian and the energy-gap promise without adding extra entanglement.

What would settle it

An explicit family of stoquastic sparse Hamiltonians whose ground-state energy decision cannot be verified by any StoqMA protocol with polynomial-size proofs and polynomial-time verification would refute the membership claim.

Figures

Figures reproduced from arXiv: 2605.02845 by Alex B. Grilo, Marios Rozos.

Figure 1
Figure 1. Figure 1: Complexity classification of Hamiltonian problems under locality, sparsity, view at source ↗
Figure 2
Figure 2. Figure 2: Complexity classification of Hamiltonian problems with separable witness view at source ↗
Figure 3
Figure 3. Figure 3: Region in the (c, s)-plane where Theorem 1.4 holds. 4 view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that the Stoquastic Sparse Hamiltonians problem (StoqSH) is StoqMA-complete. It establishes membership of StoqSH in StoqMA and notes that Stoquastic Local Hamiltonians are StoqMA-hard; since local stoquastic Hamiltonians are a subclass of sparse ones, hardness transfers directly. It further shows that the separable version of StoqSH is StoqMA(2)-complete.

Significance. If the membership proof holds, the result clarifies the complexity landscape for stoquastic Hamiltonians, which is central to the Cubitt-Montanaro classification theorem. The direct inheritance of hardness via the identity map (no non-trivial reduction needed) means the claim rests on the new upper bound; the stress-test concern about reduction preservation does not land, as the subclass relation automatically preserves stoquasticity and the promise gap.

minor comments (1)
  1. [Abstract] Abstract: the phrasing 'since Stoquastic Local Hamiltonians are StoqMA-hard, this implies...' could briefly note that the implication follows from the subclass relation rather than a constructed reduction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, accurate summary of our results, and recommendation for minor revision. We appreciate the recognition that the hardness of StoqSH follows directly from the subclass relation with Stoquastic Local Hamiltonians, with no additional reduction required, and that stoquasticity and the promise gap are automatically preserved.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper proves StoqSH membership in StoqMA directly and inherits StoqMA-hardness from the established StoqMA-hardness of Stoquastic Local Hamiltonians (Cubitt-Montanaro 2016, external citation). Hardness transfers via the identity map on the subclass, preserving stoquasticity and promise gap with no additional reduction steps. The separable StoqSH result uses standard unentangled-proof techniques. No equations, self-definitions, fitted parameters, or load-bearing self-citations reduce any claim to its own inputs by construction. The argument is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard definitions of StoqMA, stoquastic Hamiltonians, and promise-gap reductions; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Stoquastic Local Hamiltonians is StoqMA-hard (Cubitt-Montanaro)
    Cited as the hardness source for the completeness result.
  • standard math Standard definitions of StoqMA and StoqMA(2)
    Used to define the target classes.

pith-pipeline@v0.9.0 · 5513 in / 1196 out tokens · 55514 ms · 2026-05-08T01:40:13.024935+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    and Childs, Andrew M

    Berry, Dominic W. and Childs, Andrew M. and Cleve, Richard and Kothari, Robin and Somma, Rolando D. , title =. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , pages =. 2014 , isbn =. doi:10.1145/2591796.2591854 , abstract =

    work page doi:10.1145/2591796.2591854 2014

  2. [2]

    and Oliveira, Roberto and Terhal, Barbara M

    Bravyi, Sergey and Divincenzo, David P. and Oliveira, Roberto and Terhal, Barbara M. , title =. Quantum Info. Comput. , month = may, pages =. 2008 , issue_date =

    2008

  3. [3]

    Merlin--Arthur games and stoquastic complexity

    Sergey Bravyi and Arvid J. Bessen and Barbara M. Terhal , year=. Merlin-. quant-ph/0611021 , archivePrefix=

    work page arXiv

  4. [4]

    Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing , pages =

    Aharonov, Dorit and Ta-Shma, Amnon , title =. Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing , pages =. 2003 , isbn =. doi:10.1145/780542.780546 , abstract =

    work page doi:10.1145/780542.780546 2003

  5. [5]

    and Chuang, Isaac L

    Nielsen, Michael A. and Chuang, Isaac L. , year=. Quantum Computation and Quantum Information: 10th Anniversary Edition , publisher=

  6. [6]

    Termwise versus globally stoquastic local hamiltonians: questions of complexity and sign-curing,

    Ioannou, Marios and Piddock, Stephen and Marvian, Milad and Klassen, Joel and Terhal, Barbara M. Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing. 2020. arXiv:2007.11964

    work page arXiv 2020

  7. [7]

    The Complexity of the Separable Hamiltonian Problem , year=

    Chailloux, André and Sattath, Or , booktitle=. The Complexity of the Separable Hamiltonian Problem , year=

  8. [8]

    Kitaev, A. Yu. and Shen, A. H. and Vyalyi, M. N. , title =. 2002 , isbn =

    2002

  9. [9]

    Testing matrix product states

    Mehdi Soleimanifar and John Wright , title =. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2022 , pages =. doi:10.1137/1.9781611977073.68 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.68 , abstract =

    work page doi:10.1137/1.9781611977073.68 2022

  10. [10]

    and Montanaro, Ashley , title =

    Harrow, Aram W. and Montanaro, Ashley , title =. J. ACM , month = feb, articleno =. 2013 , issue_date =. doi:10.1145/2432622.2432625 , abstract =

    work page doi:10.1145/2432622.2432625 2013

  11. [11]

    Liu, Yi-Kai , title =. Proceedings of the 9th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation , pages =. 2006 , isbn =. doi:10.1007/11830924_40 , abstract =

    work page doi:10.1007/11830924_40 2006

  12. [12]

    2007 , eprint=

    The Local Consistency Problem for Stoquastic and 1-D Quantum Systems , author=. 2007 , eprint=

    2007

  13. [13]

    Proceedings of the 2014 IEEE 29th Conference on Computational Complexity , pages =

    Aaronson, Scott and Impagliazzo, Russell and Moshkovitz, Dana , title =. Proceedings of the 2014 IEEE 29th Conference on Computational Complexity , pages =. 2014 , isbn =. doi:10.1109/CCC.2014.13 , abstract =

    work page doi:10.1109/ccc.2014.13 2014

  14. [14]

    The Power of Adiabatic Quantum Computation with No Sign Problem

    Hastings, Matthew B. , journal =. The. doi:10.22331/q-2021-12-06-597 , url =

    work page doi:10.22331/q-2021-12-06-597 2021

  15. [15]

    Hastings, and Umesh V

    Gily\'. (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem , year =. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =. doi:10.1145/3406325.3451060 , abstract =

    work page doi:10.1145/3406325.3451060

  16. [16]

    Proof for an upper bound in fixed-node Monte Carlo for lattice fermions , author =. Phys. Rev. B , volume =. 1995 , month =. doi:10.1103/PhysRevB.51.13039 , url =

    work page doi:10.1103/physrevb.51.13039 1995

  17. [17]

    A rapidly mixing

    Bravyi, Sergey and Carleo, Giuseppe and Gosset, David and Liu, Yinchen , journal =. A rapidly mixing. doi:10.22331/q-2023-11-07-1173 , url =

    work page doi:10.22331/q-2023-11-07-1173 2023

  18. [18]

    Local Hamiltonian Problem with Succinct Ground State is MA-Complete

    Local Hamiltonian Problem with Succinct Ground State is MA-Complete , author =. PRX Quantum , volume =. 2025 , month =. doi:10.1103/PRXQuantum.6.020312 , url =

    work page doi:10.1103/prxquantum.6.020312 2025

  19. [19]

    Complexity Classification of Local Hamiltonian Problems

    Cubitt, Toby and Montanaro, Ashley , title =. SIAM Journal on Computing , volume =. 2016 , doi =. https://doi.org/10.1137/140998287 , abstract =

    work page doi:10.1137/140998287 2016

  20. [20]

    Schaefer

    Schaefer, Thomas J. , title =. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , pages =. 1978 , isbn =. doi:10.1145/800133.804350 , abstract =

    work page doi:10.1145/800133.804350 1978

  21. [21]

    2010 , journal =

    Bravyi, Sergey and Terhal, Barbara , title =. SIAM Journal on Computing , volume =. 2010 , doi =. https://doi.org/10.1137/08072689X , abstract =

    work page doi:10.1137/08072689x 2010

  22. [22]

    Randomness , author=

    Stoquastic PCP vs. Randomness , author=. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2019 , organization=

    2019

  23. [23]

    2025 , eprint=

    Complexity of geometrically local stoquastic Hamiltonians , author=. 2025 , eprint=

    2025

  24. [24]

    2025 , eprint=

    The Complexity of Local Stoquastic Hamiltonians on 2D Lattices , author=. 2025 , eprint=

    2025

  25. [25]

    StoqMA vs. MA: the power of error reduction

    Aharonov, Dorit and Grilo, Alex B. and Liu, Yupan , journal =. Stoq. doi:10.22331/q-2025-09-11-1853 , url =

    work page doi:10.22331/q-2025-09-11-1853 2025

  26. [26]

    StoqMA Meets Distribution Testing

    Liu, Yupan , title =. 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) , pages =. 2021 , volume =. doi:10.4230/LIPIcs.TQC.2021.4 , annote =

    work page doi:10.4230/lipics.tqc.2021.4 2021

  27. [27]

    Communications in Mathematical Physics , volume=

    On complexity of the quantum Ising model , author=. Communications in Mathematical Physics , volume=. 2017 , publisher=

    2017

  28. [28]

    Kitaev, Alexei , journal=. Quantum

  29. [29]

    Quantum Info

    Piddock, Stephen and Montanaro, Ashley , title =. Quantum Info. Comput. , month = jun, pages =. 2017 , issue_date =

    2017

  30. [30]

    Quantum Fingerprinting , author =. Phys. Rev. Lett. , volume =. 2001 , month =. doi:10.1103/PhysRevLett.87.167902 , url =

    work page doi:10.1103/physrevlett.87.167902 2001

  31. [31]

    The Complexity of the Local Hamiltonian Problem

    Kempe, Julia and Kitaev, Alexei and Regev, Oded , title =. SIAM Journal on Computing , volume =. 2006 , doi =. https://doi.org/10.1137/S0097539704445226 , abstract =

    work page doi:10.1137/s0097539704445226 2006

  32. [32]

    and Gosset, David and Webb, Zak

    Childs, Andrew M. and Gosset, David and Webb, Zak. The Bose-Hubbard Model is QMA-complete. Automata, Languages, and Programming. 2014

    2014

  33. [33]

    The Power of Quantum Systems on a Line , year=

    Aharonov, Dorit and Gottesman, Daniel and Irani, Sandy and Kempe, Julia , booktitle=. The Power of Quantum Systems on a Line , year=

  34. [34]

    Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference

    Liu, Yupan and Wu, Pei , year = 2026, month = apr, number =. Unentangled Stoquastic. doi:10.48550/arXiv.2604.27886 , urldate =. arXiv , keywords =:2604.27886 , primaryclass =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2604.27886 2026