The Complexity of Stoquastic Sparse Hamiltonians
2026-05-04 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a complexity class called StoqMA, which is important in understanding certain quantum problems but is defined in an unusual way. They show that a problem involving stoquastic sparse Hamiltonians (StoqSH) fits exactly within this class, meaning StoqSH is as hard as the hardest problems in StoqMA. Additionally, they investigate a version of this problem where the input consists of two separate pieces of information and find it complete for StoqMA(2), a related class involving two unentangled proofs. These results help clarify the power and boundaries of StoqMA and its variants.
StoqMAHamiltonian complexityStoquastic HamiltoniansStoqSHStoqMA(2)quantum complexity classesunentangled proofscomplexity completenessMAAM
Authors
Alex B. Grilo, Marios Rozos
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.