Stoquastic Sparse Hamiltonians is StoqMA-complete and its separable version is StoqMA(2)-complete.
Complexity Classification of Local Hamiltonian Problems
3 Pith papers cite this work, alongside 46 external citations. Polarity classification is still indexing.
3
Pith papers citing it
46
external citations · Crossref
years
2026 3verdicts
UNVERDICTED 3representative citing papers
Many r-local Hamiltonians, including Pauli strings, random high-rank operators, and high-rank operators, admit sparsifications with o(n^r) terms that (1±ε)-approximate the original Hamiltonian on all states.
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.
citing papers explorer
-
The Complexity of Stoquastic Sparse Hamiltonians
Stoquastic Sparse Hamiltonians is StoqMA-complete and its separable version is StoqMA(2)-complete.
-
Many Hamiltonians Are Sparsifiable
Many r-local Hamiltonians, including Pauli strings, random high-rank operators, and high-rank operators, admit sparsifications with o(n^r) terms that (1±ε)-approximate the original Hamiltonian on all states.
-
Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.