Complexity of geometrically local stoquastic Hamiltonians
Summarize this article with:
AbstractThe QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.Popular summaryStoquastic Hamiltonians avoid the sign problem in Monte Carlo simulations, so they are often viewed as the easy corner of many-body physics. We show that this intuition fails. Even under strict physical structure, estimating the ground-state energy remains computationally intractable. Earlier work proved MA-hardness for general stoquastic Hamiltonians but did not enforce geometric locality. Our results close that gap by establishing MA-hardness for nearest-neighbour, geometrically local models in two dimensions and on a line (one dimension), all with constant local dimension of qudits. We give two explicit constructions that encode a randomized classical verifier while preserving stoquasticity and geometric locality. Our results imply that in the worst case, sign-free geometrically local interactions between qudits still do not yield a tractable ground-state energy problem.► BibTeX data@article{Raza2026complexityof, doi = {10.22331/q-2026-02-11-2004}, url = {https://doi.org/10.22331/q-2026-02-11-2004}, title = {Complexity of geometrically local stoquastic {H}amiltonians}, author = {Raza, Asad and Eisert, Jens and Grilo, Alex B.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2004}, month = feb, year = {2026} }► References [1] A.Y. Kitaev, A.H. Shen, and M.N. Vyalyi. ``Classical and quantum computation''. AMS. Providence, RI (2002). https://doi.org/10.1090/gsm/047 [2] Julia Kempe, Alexei Kitaev, and Oded Regev. ``The complexity of the local Hamiltonian problem''. In Proceedings of the 24th International Conference on Foundations of Software Technology and Theoretical Computer Science. Page 372–383. FSTTCS'04Berlin, Heidelberg (2004). Springer-Verlag. https://doi.org/10.1007/978-3-540-30538-5_31 [3] Julia Kempe and Oded Regev. ``3-local Hamitonian is QMA-complete''. Quant. Inf. Comp. 3, 258–264 (2003). https://doi.org/10.26421/QIC3.3-7 [4] D. Nagaj and S. Mozes. ``New construction for a QMA complete three-local Hamiltonian''. J. Math. Phys. 48 (2007). https://doi.org/10.1063/1.2748377 [5] A. Kay. ``Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems''. Phys. Rev. A 76, 030307 (2007). https://doi.org/10.1103/PhysRevA.76.030307 [6] Roberto Oliveira and Barbara M. Terhal. ``The complexity of quantum spin systems on a two-dimensional square lattice''. Quant. Inf. Comp. 8, 900–924 (2008). https://doi.org/10.26421/QIC8.10-2 [7] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. ``The power of quantum systems on a line''. Commun. Math. Phys. 287, 41–65 (2009). https://doi.org/10.1007/s00220-008-0710-3 [8] D. Hangleiter and J. Eisert. ``Computational advantage of quantum random sampling''. Rev. Mod. Phys. 95, 035001 (2023). https://doi.org/10.1103/RevModPhys.95.035001 [9] S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin. ``Quantum Hamiltonian complexity''. Found. Trends Theo. Comp. Sc. 10, 159–282 (2015). https://doi.org/10.1561/0400000066 [10] T. J. Osborne. ``Hamiltonian complexity''. Rep. Prog. Phys. 75, 022001 (2012). https://doi.org/10.1088/0034-4885/75/2/022001 [11] J. E. Hirsch, R. L. Sugar, D. J. Scalapino, and R. Blankenbecler. ``Monte Carlo simulations of one-dimensional fermion systems''. Phys. Rev. B 26, 5033–5055 (1982). https://doi.org/10.1103/PhysRevB.26.5033 [12] M. Troyer, F. Alet, S. Trebst, and S. Wessel. ``Non‐local updates for quantum Monte Carlo simulations''. AIP Conf. Proc. 690, 156–169 (2003). https://doi.org/10.1063/1.1632126 [13] L. Pollet. ``Recent developments in quantum Monte Carlo simulations with applications for cold gases''. Rep. Prog. Phys. 75, 094501 (2012). https://doi.org/10.1088/0034-4885/75/9/094501 [14] Matthias Troyer and Uwe-Jens Wiese. ``Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations''. Phys. Rev. Lett. 94, 170201 (2005). https://doi.org/10.1103/PhysRevLett.94.170201 [15] D. Hangleiter, I. Roth, D. Nagaj, and J. Eisert. ``Easing the Monte Carlo sign problem''. Science Adv. 6, eabb8341 (2020). https://doi.org/10.48550/arXiv.1906.02309 [16] Sergey Bravyi and Barbara Terhal. ``Complexity of stoquastic frustration-free Hamiltonians''. SIAM J. Comp. 39, 1462–1485 (2010). https://doi.org/10.1137/08072689X [17] L. Babai. ``Trading group theory for randomness''. Proc. Seventeenth Ann. ACM Symp. Th. Comp. STOC ’85Page 421–429 (1985). https://doi.org/10.1145/22145.22192 [18] A. Gilyén, M. B Hastings, and U. Vazirani. ``(Sub) exponential advantage of adiabatic quantum computation with no sign problem''. In Proc. 53rd Ann. ACM SIGACT Symp. Th. Comp. Pages 1357–1369. (2021). https://doi.org/10.48550/arXiv.2011.09495 [19] Dorit Aharonov and Alex Bredariol Grilo. ``Stoquastic PCP vs. randomness''.
In David Zuckerman, editor, 60th IEEE Ann. Symp. Found. Comp. Sc. FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019. Pages 1000–1023. IEEE Computer Society (2019). https://doi.org/10.1109/FOCS.2019.00065 [20] Dorit Aharonov and Alex B. Grilo. ``Two combinatorial ma-complete problems''. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference. Volume 185 of LIPIcs, pages 36:1–36:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPICS.ITCS.2021.36 [21] Jiaqing Jiang. ``Local Hamiltonian problem with succinct ground state is MA-complete''. PRX Quantum 6, 020312 (2025). https://doi.org/10.1103/PRXQuantum.6.020312 [22] S. Bravyi. ``Monte Carlo simulation of stoquastic Hamiltonians''. Quant. Inf. Comp. 15, 1122–1140 (2015). [23] Sergey Bravyi, David P. DiVincenzo, Roberto Oliveira, and Barbara M. Terhal. ``The complexity of stoquastic local hamiltonian problems''. Quantum Inf. Comput. 8, 361–385 (2008). https://doi.org/10.26421/QIC8.5-1 [24] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal. ``Merlin-Arthur games and stoquastic complexity'' (2006). arXiv:quant-ph/0611021. arXiv:quant-ph/0611021 [25] J. Klassen, M. Marvian, S. Piddock, M. Ioannou, I. Hen, and B. M. Terhal. ``Hardness and ease of curing the sign problem for two local qubit Hamiltonians''. SIAM J. Comp. 49, 1332–1362 (2020). https://doi.org/10.1137/19M1287511 [26] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. ``Adiabatic quantum computation is equivalent to standard quantum computation''. SIAM Rev. 50, 755–787 (2008). https://doi.org/10.1109/FOCS.2004.8 [27] Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami. ``The local Hamiltonian problem on a line with eight states is QMA-complete''. Quant. Inf. Comp. 13, 721–750 (2013). https://doi.org/10.26421/QIC13.9-10-1 [28] Stathis Zachos and Martin Furer. ``Probabilistic quantifiers vs. distrustful adversaries''. In Kesav V. Nori, editor, Foundations of Software Technology and Theoretical Computer Science. Pages 443–455. Berlin, Heidelberg (1987).
Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-18625-5_67 [29] Oded Goldreich and David Zuckerman. ``Another Proof that BPP $⊆$ PH (and more)''. In Studies in complexity and cryptography. Miscellanea on the Interplay between randomness and computation. Volume 6650 of Lecture Notes in Computer Science. Berlin, Heidelberg (2011). Springer. https://doi.org/10.1007/978-3-642-22670-0_6 [30] Dorit Aharonov, Alex B. Grilo, and Yupan Liu. ``StoqMA vs. MA: the power of error reduction''. Quantum 9, 1853 (2025). https://doi.org/10.22331/q-2025-09-11-1853 [31] Dorit Aharonov and Tomer Naveh. ``Quantum NP - A survey'' (2002). arXiv:quant-ph/0210077. arXiv:quant-ph/0210077 [32] T. Cubitt and A. Montanaro. ``Complexity classification of local Hamiltonian problems''. SIAM J. Comp. 45, 268–316 (2016). https://doi.org/10.1137/140998287 [33] D. Nagaj, D. Hangleiter, J. Eisert, and M. Schwarz. ``Pinned quantum Merlin-Arthur: The power of fixing a few qubits in proofs''. Phys. Rev. A 103, 012604 (2021). https://doi.org/10.1103/PhysRevA.103.012604Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-11 10:41:40: Could not fetch cited-by data for 10.22331/q-2026-02-11-2004 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-11 10:41:40: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractThe QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity that studies the computational complexity of problems in quantum many-body physics. Since its proposal, substantial effort has been invested in better understanding the problem for physically motivated important families of Hamiltonians. In particular, the QMA-completeness of approximating the ground state energy of local Hamiltonians has been extended to the case where the Hamiltonians are geometrically local in one and two spatial dimensions. Among those physically motivated Hamiltonians, stoquastic Hamiltonians play a particularly crucial role, as they constitute the manifestly sign-free Hamiltonians in Monte Carlo approaches. Interestingly, for such Hamiltonians, the problem at hand becomes more ''classical'', being hard for the class MA (the randomized version of NP) and its complexity has tight connections with derandomization. In this work, we prove that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension. Moreover, we show that related problems are StoqMA-complete.Popular summaryStoquastic Hamiltonians avoid the sign problem in Monte Carlo simulations, so they are often viewed as the easy corner of many-body physics. We show that this intuition fails. Even under strict physical structure, estimating the ground-state energy remains computationally intractable. Earlier work proved MA-hardness for general stoquastic Hamiltonians but did not enforce geometric locality. Our results close that gap by establishing MA-hardness for nearest-neighbour, geometrically local models in two dimensions and on a line (one dimension), all with constant local dimension of qudits. We give two explicit constructions that encode a randomized classical verifier while preserving stoquasticity and geometric locality. Our results imply that in the worst case, sign-free geometrically local interactions between qudits still do not yield a tractable ground-state energy problem.► BibTeX data@article{Raza2026complexityof, doi = {10.22331/q-2026-02-11-2004}, url = {https://doi.org/10.22331/q-2026-02-11-2004}, title = {Complexity of geometrically local stoquastic {H}amiltonians}, author = {Raza, Asad and Eisert, Jens and Grilo, Alex B.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2004}, month = feb, year = {2026} }► References [1] A.Y. Kitaev, A.H. Shen, and M.N. Vyalyi. ``Classical and quantum computation''. AMS. Providence, RI (2002). https://doi.org/10.1090/gsm/047 [2] Julia Kempe, Alexei Kitaev, and Oded Regev. ``The complexity of the local Hamiltonian problem''. In Proceedings of the 24th International Conference on Foundations of Software Technology and Theoretical Computer Science. Page 372–383. FSTTCS'04Berlin, Heidelberg (2004). Springer-Verlag. https://doi.org/10.1007/978-3-540-30538-5_31 [3] Julia Kempe and Oded Regev. ``3-local Hamitonian is QMA-complete''. Quant. Inf. Comp. 3, 258–264 (2003). https://doi.org/10.26421/QIC3.3-7 [4] D. Nagaj and S. Mozes. ``New construction for a QMA complete three-local Hamiltonian''. J. Math. Phys. 48 (2007). https://doi.org/10.1063/1.2748377 [5] A. Kay. ``Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems''. Phys. Rev. A 76, 030307 (2007). https://doi.org/10.1103/PhysRevA.76.030307 [6] Roberto Oliveira and Barbara M. Terhal. ``The complexity of quantum spin systems on a two-dimensional square lattice''. Quant. Inf. Comp. 8, 900–924 (2008). https://doi.org/10.26421/QIC8.10-2 [7] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. ``The power of quantum systems on a line''. Commun. Math. Phys. 287, 41–65 (2009). https://doi.org/10.1007/s00220-008-0710-3 [8] D. Hangleiter and J. Eisert. ``Computational advantage of quantum random sampling''. Rev. Mod. Phys. 95, 035001 (2023). https://doi.org/10.1103/RevModPhys.95.035001 [9] S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin. ``Quantum Hamiltonian complexity''. Found. Trends Theo. Comp. Sc. 10, 159–282 (2015). https://doi.org/10.1561/0400000066 [10] T. J. Osborne. ``Hamiltonian complexity''. Rep. Prog. Phys. 75, 022001 (2012). https://doi.org/10.1088/0034-4885/75/2/022001 [11] J. E. Hirsch, R. L. Sugar, D. J. Scalapino, and R. Blankenbecler. ``Monte Carlo simulations of one-dimensional fermion systems''. Phys. Rev. B 26, 5033–5055 (1982). https://doi.org/10.1103/PhysRevB.26.5033 [12] M. Troyer, F. Alet, S. Trebst, and S. Wessel. ``Non‐local updates for quantum Monte Carlo simulations''. AIP Conf. Proc. 690, 156–169 (2003). https://doi.org/10.1063/1.1632126 [13] L. Pollet. ``Recent developments in quantum Monte Carlo simulations with applications for cold gases''. Rep. Prog. Phys. 75, 094501 (2012). https://doi.org/10.1088/0034-4885/75/9/094501 [14] Matthias Troyer and Uwe-Jens Wiese. ``Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations''. Phys. Rev. Lett. 94, 170201 (2005). https://doi.org/10.1103/PhysRevLett.94.170201 [15] D. Hangleiter, I. Roth, D. Nagaj, and J. Eisert. ``Easing the Monte Carlo sign problem''. Science Adv. 6, eabb8341 (2020). https://doi.org/10.48550/arXiv.1906.02309 [16] Sergey Bravyi and Barbara Terhal. ``Complexity of stoquastic frustration-free Hamiltonians''. SIAM J. Comp. 39, 1462–1485 (2010). https://doi.org/10.1137/08072689X [17] L. Babai. ``Trading group theory for randomness''. Proc. Seventeenth Ann. ACM Symp. Th. Comp. STOC ’85Page 421–429 (1985). https://doi.org/10.1145/22145.22192 [18] A. Gilyén, M. B Hastings, and U. Vazirani. ``(Sub) exponential advantage of adiabatic quantum computation with no sign problem''. In Proc. 53rd Ann. ACM SIGACT Symp. Th. Comp. Pages 1357–1369. (2021). https://doi.org/10.48550/arXiv.2011.09495 [19] Dorit Aharonov and Alex Bredariol Grilo. ``Stoquastic PCP vs. randomness''.
In David Zuckerman, editor, 60th IEEE Ann. Symp. Found. Comp. Sc. FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019. Pages 1000–1023. IEEE Computer Society (2019). https://doi.org/10.1109/FOCS.2019.00065 [20] Dorit Aharonov and Alex B. Grilo. ``Two combinatorial ma-complete problems''. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference. Volume 185 of LIPIcs, pages 36:1–36:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPICS.ITCS.2021.36 [21] Jiaqing Jiang. ``Local Hamiltonian problem with succinct ground state is MA-complete''. PRX Quantum 6, 020312 (2025). https://doi.org/10.1103/PRXQuantum.6.020312 [22] S. Bravyi. ``Monte Carlo simulation of stoquastic Hamiltonians''. Quant. Inf. Comp. 15, 1122–1140 (2015). [23] Sergey Bravyi, David P. DiVincenzo, Roberto Oliveira, and Barbara M. Terhal. ``The complexity of stoquastic local hamiltonian problems''. Quantum Inf. Comput. 8, 361–385 (2008). https://doi.org/10.26421/QIC8.5-1 [24] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal. ``Merlin-Arthur games and stoquastic complexity'' (2006). arXiv:quant-ph/0611021. arXiv:quant-ph/0611021 [25] J. Klassen, M. Marvian, S. Piddock, M. Ioannou, I. Hen, and B. M. Terhal. ``Hardness and ease of curing the sign problem for two local qubit Hamiltonians''. SIAM J. Comp. 49, 1332–1362 (2020). https://doi.org/10.1137/19M1287511 [26] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. ``Adiabatic quantum computation is equivalent to standard quantum computation''. SIAM Rev. 50, 755–787 (2008). https://doi.org/10.1109/FOCS.2004.8 [27] Sean Hallgren, Daniel Nagaj, and Sandeep Narayanaswami. ``The local Hamiltonian problem on a line with eight states is QMA-complete''. Quant. Inf. Comp. 13, 721–750 (2013). https://doi.org/10.26421/QIC13.9-10-1 [28] Stathis Zachos and Martin Furer. ``Probabilistic quantifiers vs. distrustful adversaries''. In Kesav V. Nori, editor, Foundations of Software Technology and Theoretical Computer Science. Pages 443–455. Berlin, Heidelberg (1987).
Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-18625-5_67 [29] Oded Goldreich and David Zuckerman. ``Another Proof that BPP $⊆$ PH (and more)''. In Studies in complexity and cryptography. Miscellanea on the Interplay between randomness and computation. Volume 6650 of Lecture Notes in Computer Science. Berlin, Heidelberg (2011). Springer. https://doi.org/10.1007/978-3-642-22670-0_6 [30] Dorit Aharonov, Alex B. Grilo, and Yupan Liu. ``StoqMA vs. MA: the power of error reduction''. Quantum 9, 1853 (2025). https://doi.org/10.22331/q-2025-09-11-1853 [31] Dorit Aharonov and Tomer Naveh. ``Quantum NP - A survey'' (2002). arXiv:quant-ph/0210077. arXiv:quant-ph/0210077 [32] T. Cubitt and A. Montanaro. ``Complexity classification of local Hamiltonian problems''. SIAM J. Comp. 45, 268–316 (2016). https://doi.org/10.1137/140998287 [33] D. Nagaj, D. Hangleiter, J. Eisert, and M. Schwarz. ``Pinned quantum Merlin-Arthur: The power of fixing a few qubits in proofs''. Phys. Rev. A 103, 012604 (2021). https://doi.org/10.1103/PhysRevA.103.012604Cited byCould not fetch Crossref cited-by data during last attempt 2026-02-11 10:41:40: Could not fetch cited-by data for 10.22331/q-2026-02-11-2004 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-02-11 10:41:40: No response from ADS or unable to decode the received json data when getting the list of citing works.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.