The Complexity of Stoquastic Sparse Hamiltonians
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.02845
curl -X POST /api/v1/records/arxiv/2605.02845/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.02845/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'