{"id":"arxiv/2605.02845","url":"https://arxiv.org/abs/2605.02845","tags":["cs.CC","quant-ph"],"score":0,"title":"The Complexity of Stoquastic Sparse Hamiltonians","domain":"cs.CC","source":"arxiv","authors":["Alex B. Grilo","Marios Rozos"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-04","reactions":{}}