StoqMA vs. MA: the power of error reduction

Dorit Aharonov; Alex B. Grilo; Yupan Liu

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

StoqMA vs. MA: the power of error reduction

Dorit Aharonov^1,2, Alex B. Grilo³, and Yupan Liu⁴

¹School of Computer Science and Engineering, The Hebrew University of Jerusalem
²Qedma Quantum Computing Ltd.
³Sorbonne Université, CNRS, LIP6
⁴Graduate School of Mathematics, Nagoya University

Published:	2025-09-11, volume 9, page 1853
Editor:	Srinivasan Arunachalam
Eprint:	arXiv:2010.02835v4
Doi:	https://doi.org/10.22331/q-2025-09-11-1853
Citation:	Quantum 9, 1853 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

$\sf{StoqMA}$ characterizes the computational hardness of stoquastic local Hamiltonians, which is a family of Hamiltonians that does not suffer from the sign problem. Although error reduction is commonplace for many complexity classes, such as $\sf{BPP, BQP, MA, QMA}$, etc.,this property remains open for $\sf{StoqMA}$ since Bravyi, Bessen and Terhal defined this class in 2006. In this note, we show that error reduction for $\sf{StoqMA}$ will imply that $\sf{StoqMA = MA}$.

► BibTeX data

@article{Aharonov2025stoqmavsmapowerof,
  doi = {10.22331/q-2025-09-11-1853},
  url = {https://doi.org/10.22331/q-2025-09-11-1853},
  title = {Stoq{MA} vs. {MA}: the power of error reduction},
  author = {Aharonov, Dorit and Grilo, Alex B. and Liu, Yupan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1853},
  month = sep,
  year = {2025}
}

► References

[1] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. ``Classical and quantum computation''. American Mathematical Soc. (2002).
https://doi.org/10.5555/863284

[2] Julia Kempe and Oded Regev. ``3-local hamiltonian is QMA-complete''. Quantum Information and Computation 3, 258–264 (2003).
https://doi.org/10.5555/2011534.2011541

[3] Julia Kempe, Alexei Kitaev, and Oded Regev. ``The complexity of the local hamiltonian problem''. SIAM Journal on Computing 35, 1070–1097 (2006).
https://doi.org/10.1137/S0097539704445226

[4] Roberto Oliveira and Barbara M Terhal. ``The complexity of quantum spin systems on a two-dimensional square lattice''. Quantum Information & Computation 8, 900–924 (2008).
https://doi.org/10.5555/2016985.2016987

[5] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. ``The power of quantum systems on a line''. Communications in Mathematical Physics 287, 41–65 (2009).
https://doi.org/10.1007/s00220-008-0710-3

[6] Andrew M. Childs, David Gosset, and Zak Webb. ``The bose-hubbard model is $\mathsf{QMA}$-complete''. In International Colloquium on Automata, Languages, and Programming. Pages 308–319. Springer (2014).
https://doi.org/10.1007/978-3-662-43948-7_26

[7] Toby Cubitt and Ashley Montanaro. ``Complexity classification of local hamiltonian problems''. SIAM Journal on Computing 45, 268–316 (2016).
https://doi.org/10.1137/140998287

[8] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. ``A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem''. Science 292, 472–475 (2001).
https://doi.org/10.1126/science.1057726

[9] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. ``Quantum annealing with manufactured spins''. Nature 473, 194–198 (2011).
https://doi.org/10.1038/nature10012

[10] Tameem Albash and Daniel A Lidar. ``Adiabatic quantum computation''. Reviews of Modern Physics 90, 015002 (2018).
https://doi.org/10.1103/RevModPhys.90.015002

[11] Sergey Bravyi, David P. Divincenzo, Roberto Oliveira, and Barbara M. Terhal. ``The complexity of stoquastic local hamiltonian problems''. Quantum Info. Comput. 8, 361–385 (2008).
https://doi.org/10.5555/2011772.2011773

[12] Sergey Bravyi, Arvid J Bessen, and Barbara M Terhal. ``Merlin-arthur games and stoquastic complexity'' (2006).

[13] Sergey Bravyi and Barbara Terhal. ``Complexity of stoquastic frustration-free hamiltonians''. SIAM Journal on Computing 39, 1462–1485 (2010).
https://doi.org/10.1137/08072689X

[14] Sergey Bravyi and Matthew Hastings. ``On complexity of the quantum ising model''. Communications in Mathematical Physics 349, 1–45 (2017).
https://doi.org/10.1007/s00220-016-2787-4

[15] Thomas J. Schaefer. ``The complexity of satisfiability problems''. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC 78. (1978).

[16] László Babai. ``Trading group theory for randomness''. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing. Pages 421–429. (1985).
https://doi.org/10.1145/22145.22192

[17] Ran Raz and Avishay Tal. ``Oracle separation of BQP and PH''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019. Pages 13–23. ACM (2019).
https://doi.org/10.1145/3313276.3316315

[18] Adam R Klivans and Dieter van Melkebeek. ``Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses''. SIAM Journal on Computing 31, 1501–1526 (2002).
https://doi.org/10.1137/S0097539700389652

[19] Peter Bro Miltersen and N Variyam Vinodchandran. ``Derandomizing arthur–merlin games using hitting sets''. Computational Complexity 14, 256–279 (2005).
https://doi.org/10.1007/s00037-005-0197-7

[20] Martin Furer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos. ``On completeness and soundness in interactive proof systems''. Advances in Computing Research: A Research Annual, 5, 429–442 (1989).

[21] Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. ``Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems''. Quantum Information & Computation 12, 461–471 (2012).
https://doi.org/10.5555/2230996.2231003

[22] Dorit Aharonov and Alex Bredariol Grilo. ``Stoquastic pcp vs. randomness''. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1000–1023. IEEE (2019).
https://doi.org/10.1109/FOCS.2019.00065

[23] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. ``Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?''. Chic. J. Theor. Comput. Sci. 2009 (2009).
https://doi.org/10.1007/978-3-540-24587-2_21

[24] Aram W Harrow and Ashley Montanaro. ``Testing product states, quantum merlin-arthur games and tensor optimization''. Journal of the ACM (JACM) 60, 1–43 (2013).
https://doi.org/10.1145/2432622.2432625

[25] Shayan Oveis Gharan and Luca Trevisan. ``Approximating the expansion profile and almost optimal local graph clustering''. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. Pages 187–196. (2012).
https://doi.org/10.1109/FOCS.2012.85

[26] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. ``Markov chains and mixing times''. American Mathematical Society. (2006).
https://doi.org/10.1007/s00283-018-9839-x

[27] Michael A Nielsen and Isaac Chuang. ``Quantum computation and quantum information'' (2002).

[28] John Watrous. ``Succinct quantum proofs for properties of finite groups''. In Proceedings 41st Annual Symposium on Foundations of Computer Science. Pages 537–546. IEEE (2000).
https://doi.org/10.5555/795666.796590

[29] Joel Klassen and Barbara M Terhal. ``Two-local qubit hamiltonians: when are they stoquastic?''. Quantum 3, 139 (2019).
https://doi.org/10.22331/q-2019-05-06-139

[30] Dorit Aharonov and Alex B. Grilo. ``Two combinatorial MA-complete problems''. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Pages 36:1–36:20. (2021).
https://doi.org/10.4230/LIPIcs.ITCS.2021.36

Cited by

[1] Asad Raza, Jens Eisert, and Alex B. Grilo, "Complexity of geometrically local stoquastic Hamiltonians", Quantum 10, 2004 (2026).

[2] Gabriel Waite and Michael J. Bremner, "The Complexity of Local Stoquastic Hamiltonians on 2D Lattices", Quantum 10, 2097 (2026).

[3] Jordi Weggemans, Marten Folkertsma, and Chris Cade, "Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture", arXiv:2302.11578, (2023).

[4] Gabriel Waite, "The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians", arXiv:2509.25829, (2025).

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

[6] Yupan Liu, "Quantum state testing beyond the polarizing regime and quantum triangular discrimination", arXiv:2303.01952, (2023).

[7] Sevag Gharibian, "The 7 faces of quantum NP", arXiv:2310.18010, (2023).

[8] Yupan Liu, "StoqMA meets distribution testing", arXiv:2011.05733, (2020).

[9] Gabriel Waite and Michael J. Bremner, "The Complexity of Local Stoquastic Hamiltonians on 2D Lattices", arXiv:2502.14244, (2025).

[10] William Gay and Fernando Granha Jeronimo, "The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems", arXiv:2605.16249, (2026).

[11] Sevag Gharibian and Dorian Rudolph, "On polynomially many queries to NP or QMA oracles", arXiv:2111.02296, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 16:03:39) and SAO/NASA ADS (last updated successfully 2026-07-15 16:03:40). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.