The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
Summarize this article with:
AbstractWe show the 2-Local Stoquastic Hamiltonian problem on a 2D square qubit lattice is StoqMA-complete. We achieve this by extending the spatially sparse circuit construction of Oliveira and Terhal, as well as the perturbative gadgets of Bravyi, DiVincenzo, Oliveira, and Terhal. Our main contributions demonstrate StoqMA circuits can be made spatially sparse and that geometrical, stoquastic-preserving, perturbative gadgets can be constructed, without an increase to particle dimension.Featured image: An illustration of a local stoquastic Hamiltonian constrained to a two-dimensional square lattice of qubits. Estimating the ground-state energy of such systems, in general, is StoqMA-complete.Popular summaryLocal stoquastic Hamiltonians represent a class of interacting quantum systems that avoid the sign problem of Monte Carlo simulations, making them amenable to classical algorithmic techniques. It has previously been shown that estimating the ground-state energy of such systems is intractable in general, specifically, StoqMA-complete, even for 2-local interactions. We improve this result by showing that the problem remains StoqMA-complete even when the interactions are restricted to a two-dimensional square or triangular lattice of qubits. This is achieved by extending the spatially sparse circuit construction of Oliveira and Terhal, and the perturbative gadgets of Bravyi, DiVincenzo, Oliveira and Terhal, to develop new stoquastic-preserving gadgets (Cross, Fork, Triangle) that reduce locality and planarise interaction graphs without inflating particle dimension. By working directly with qubits and not higher-dimensional particles, our results are more natural and directly relevant to real spin systems.► BibTeX data@article{Waite2026complexityoflocal, doi = {10.22331/q-2026-05-06-2097}, url = {https://doi.org/10.22331/q-2026-05-06-2097}, title = {The {C}omplexity of {L}ocal {S}toquastic {H}amiltonians on 2{D} {L}attices}, author = {Waite, Gabriel and Bremner, Michael J.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2097}, month = may, year = {2026} }► References [1] A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. ``Classical and Quantum Computation''.
American Mathematical Society. USA (2002). https://doi.org/10.1090/gsm/047 [2] Roberto Oliveira and Barbara M. Terhal. ``The complexity of quantum spin systems on a two-dimensional square lattice''. Quantum Info. Comput. 8, 900–924 (2008). arXiv:quant-ph/0504050. https://doi.org/10.26421/QIC8.10-2 arXiv:quant-ph/0504050 [3] Norbert Schuch and Frank Verstraete. ``Computational complexity of interacting electrons and fundamental limitations of density functional theory''. Nature Physics 5, 732–735 (2009). arXiv:0712.0483. https://doi.org/10.1038/nphys1370 arXiv:0712.0483 [4] Stephen Piddock and Ashley Montanaro. ``The complexity of antiferromagnetic interactions and 2D lattices''. Quantum Info. Comput. 17, 636–672 (2017). arXiv:1506.04014. https://doi.org/10.26421/QIC17.7-8-6 arXiv:1506.04014 [5] Toby S. Cubitt and Ashley Montanaro. ``Complexity Classification of Local Hamiltonian Problems''. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. Pages 120–129. FOCS '14USA (2014). IEEE Computer Society. arXiv:1311.3161. https://doi.org/10.1109/FOCS.2014.21 arXiv:1311.3161 [6] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal. ``Merlin-Arthur Games and Stoquastic Complexity'' (2006). arXiv:quant-ph/0611021. arXiv:quant-ph/0611021 [7] Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. Terhal. ``The Complexity of Stoquastic Local Hamiltonian Problems''. Quantum Inf. Comput. 8, 361–385 (2008). arXiv:quant-ph/0606140. https://doi.org/10.26421/QIC8.5-1 arXiv:quant-ph/0606140 [8] Jacob D. Biamonte and Peter J. Love. ``Realizable Hamiltonians for universal adiabatic quantum computers''. Physical Review A 78 (2008). arXiv:0704.1287. https://doi.org/10.1103/physreva.78.012352 arXiv:0704.1287 [9] Sergey Bravyi and Mikhail Vyalyi. ``Commutative version of the k-local Hamiltonian problem and common eigenspace problem''. Quantum Info. Comput. 5, 187–215 (2005). arXiv:quant-ph/0308021. https://doi.org/10.26421/QIC5.3-2 arXiv:quant-ph/0308021 [10] Norbert Schuch. ``Complexity of commuting Hamiltonians on a square lattice of qubits''. Quantum Info. Comput. 11, 901–912 (2011). arXiv:1105.2843. https://doi.org/10.26421/QIC11.11-12-1 arXiv:1105.2843 [11] Dorit Aharonov and Lior Eldar. ``On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems''. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Pages 334–343. FOCS '11USA (2011). IEEE Computer Society. arXiv:1102.0770. https://doi.org/10.1109/FOCS.2011.58 arXiv:1102.0770 [12] Dorit Aharonov and Lior Eldar. ``The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP''.
Quantum Information Processing 14, 83–101 (2014). arXiv:1311.7378. https://doi.org/10.1007/s11128-014-0877-9 arXiv:1311.7378 [13] Dorit Aharonov, Oded Kenneth, and Itamar Vigdorovich. ``On the Complexity of Two Dimensional Commuting Local Hamiltonians''. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Volume 111, pages 2:1–2:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018). arXiv:1803.02213. https://doi.org/10.4230/LIPIcs.TQC.2018.2 arXiv:1803.02213 [14] Sandy Irani and Jiaqing Jiang. ``Commuting local Hamiltonian problem on 2D beyond qubits''. Communications in Mathematical Physics 406, 273 (2025). arXiv:2309.04910. https://doi.org/10.1007/s00220-025-05462-8 arXiv:2309.04910 [15] E. Y. Loh, J. E. Gubernatis, R. T. Scalettar, S. R. White, D. J. Scalapino, and R. L. Sugar. ``Sign problem in the numerical simulation of many-electron systems''. Phys. Rev. B 41, 9301–9307 (1990). https://doi.org/10.1103/PhysRevB.41.9301 [16] Zi-Xiang Li and Hong Yao. ``Sign-Problem-Free Fermionic Quantum Monte Carlo: Developments and Applications''. Annual Review of Condensed Matter Physics 10, 337–356 (2019). arXiv:1805.08219. https://doi.org/10.1146/annurev-conmatphys-033117-054307 arXiv:1805.08219 [17] Dominik Hangleiter, Ingo Roth, Daniel Nagaj, and Jens Eisert. ``Easing the Monte Carlo sign problem''. Science Advances 6 (2020). arXiv:1906.02309. https://doi.org/10.1126/sciadv.abb8341 arXiv:1906.02309 [18] W. M. C. Foulkes, L. Mitas, R. J. Needs, and G. Rajagopal. ``Quantum Monte Carlo simulations of solids''. Rev. Mod. Phys. 73, 33–83 (2001). https://doi.org/10.1103/RevModPhys.73.33 [19] Anders W. Sandvik, Adolfo Avella, and Ferdinando Mancini. ``Computational studies of quantum spin systems''. In AIP Conference Proceedings. AIP (2010). arXiv:1101.3281. https://doi.org/10.1063/1.3518900 arXiv:1101.3281 [20] Masayuki Ohzeki. ``Quantum Monte Carlo simulation of a particular class of non-stoquastic Hamiltonians in quantum annealing''. Scientific Reports 7 (2017). arXiv:1612.04785. https://doi.org/10.1038/srep41186 arXiv:1612.04785 [21] Sergey Bravyi, Giuseppe Carleo, David Gosset, and Yinchen Liu. ``A rapidly mixing Markov chain from any gapped quantum many-body system''. Quantum 7, 1173 (2023). arXiv:2207.07044. https://doi.org/10.22331/q-2023-11-07-1173 arXiv:2207.07044 [22] Lev Barash, Arman Babakhani, and Itay Hen. ``Quantum Monte Carlo algorithm for arbitrary spin-1/2 Hamiltonians''. Phys. Rev. Res. 6, 013281 (2024). arXiv:2307.06503. https://doi.org/10.1103/PhysRevResearch.6.013281 arXiv:2307.06503 [23] D. F. B. ten Haaf, H. J. M. van Bemmel, J. M. J. van Leeuwen, W. van Saarloos, and D. M. Ceperley. ``Proof for an upper bound in fixed-node Monte Carlo for lattice fermions''. Phys. Rev. B 51, 13039–13045 (1995). https://doi.org/10.1103/PhysRevB.51.13039 [24] Dorit Aharonov, Alex B Grilo, and Yupan Liu. ``StoqMA vs. MA: the power of error reduction''. Quantum 9, 1853 (2025). arXiv:2010.02835. https://doi.org/10.22331/q-2025-09-11-1853 arXiv:2010.02835 [25] Yupan Liu. ``StoqMA Meets Distribution Testing''. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Volume 197, pages 4:1–4:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021). arXiv:2011.05733. https://doi.org/10.4230/LIPIcs.TQC.2021.4 arXiv:2011.05733 [26] Chris Marriott and John Watrous. ``Quantum Arthur-Merlin games''. Computational Complexity 14, 122–152 (2005). arXiv:cs/0506068. https://doi.org/10.1007/s00037-005-0194-x arXiv:cs/0506068 [27] Sergey Bravyi and Barbara Terhal. ``Complexity of Stoquastic Frustration-Free Hamiltonians''. SIAM J. Comput. 39, 1462–1485 (2009). arXiv:0806.1746. https://doi.org/10.1137/08072689X arXiv:0806.1746 [28] Sergey Bravyi and Matthew Hastings. ``On Complexity of the Quantum Ising Model''. Communications in Mathematical Physics 349, 1–45 (2016). arXiv:1410.0703. https://doi.org/10.1007/s00220-016-2787-4 arXiv:1410.0703 [29] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. ``Improved Hardness Results for the Guided Local Hamiltonian Problem''. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261, pages 32:1–32:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). arXiv:2207.10250. https://doi.org/10.4230/LIPIcs.ICALP.2023.32 arXiv:2207.10250 [30] Asad Raza, Jens Eisert, and Alex B Grilo. ``Complexity of geometrically local stoquastic Hamiltonians''. Quantum 10, 2004 (2026). arXiv:2407.15499. https://doi.org/10.22331/q-2026-02-11-2004 arXiv:2407.15499 [31] Sevag Gharibian. ``Guest Column: The 7 faces of quantum NP''. SIGACT News 54, 54–91 (2024). arXiv:2310.18010. https://doi.org/10.1145/3639528.3639535 arXiv:2310.18010 [32] Stathis Zachos and Martin Furer. ``Probabilistic quantifiers vs. distrustful adversaries''. In Proc. of the Seventh Conference on Foundations of Software Technology and Theoretical Computer Science. Pages 443–455. Berlin, Heidelberg (1987). Springer-Verlag. https://doi.org/10.1007/3-540-18625-5_67 [33] Julia Kempe, Alexei Kitaev, and Oded Regev. ``The Complexity of the Local Hamiltonian Problem''. SIAM Journal on Computing 35, 1070–1097 (2006). arXiv:quant-ph/0406180. https://doi.org/10.1137/S0097539704445226 arXiv:quant-ph/0406180 [34] Sergey Bravyi, David P. DiVincenzo, and Daniel Loss. ``Schrieffer-Wolff transformation for quantum many-body systems''. Annals of Physics 326, 2793–2826 (2011). arXiv:1105.0675. https://doi.org/10.1016/j.aop.2011.06.004 arXiv:1105.0675 [35] Sergey Bravyi, David P. DiVincenzo, Daniel Loss, and Barbara M. Terhal. ``Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions''. Phys. Rev. Lett. 101, 070503 (2008). arXiv:0803.2686. https://doi.org/10.1103/PhysRevLett.101.070503 arXiv:0803.2686 [36] Gabriel Waite, Ryan L Mann, and Samuel J Elman. ``The Hamiltonian Jungle'' (2023). [37] A.L. Fetter and J.D. Walecka. ``Quantum Theory of Many-Particle Systems''. Dover Books on Physics. Dover Publications. (2012). url: https://books.google.com.au/books?id=t5_DAgAAQBAJ. https://books.google.com.au/books?id=t5_DAgAAQBAJ [38] Marios Ioannou, Stephen Piddock, Milad Marvian, Joel Klassen, and Barbara M. Terhal. ``Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing'' (2022). arXiv:2007.11964. arXiv:2007.11964 [39] Sergey Bravyi and David Gosset. ``Polynomial-Time Classical Simulation of Quantum Ferromagnets''. Phys. Rev. Lett. 119, 100503 (2017). arXiv:1612.05602. https://doi.org/10.1103/PhysRevLett.119.100503 arXiv:1612.05602 [40] Stephen Piddock. ``Complexity and Simulation of Many-Body Quantum Systems''. Phd thesis. University of Bristol. (2019). url: https://research-information.bris.ac.uk/en/studentTheses/complexity-and-simulation-of-many-body-quantum-systems/. https://research-information.bris.ac.uk/en/studentTheses/complexity-and-simulation-of-many-body-quantum-systems/ [41] Sergey Bravyi. ``Monte Carlo simulation of stoquastic Hamiltonians''. Quantum Info. Comput. 15, 1122–1140 (2015). arXiv:1402.2295. https://doi.org/10.26421/QIC15.13-14-3 arXiv:1402.2295 [42] Alex Bredariol Grilo, Iordanis Kerenidis, and Jamie Sikora. ``QMA with Subset State Witnesses''. Pages 163–174.
Springer Berlin Heidelberg. (2015). arXiv:1410.2882. https://doi.org/10.1007/978-3-662-48054-0_14 arXiv:1410.2882 [43] Sevag Gharibian and François Le Gall. ``Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture''. SIAM Journal on Computing 52, 1009–1038 (2023). arXiv:2111.09079. https://doi.org/10.1137/22M1513721 arXiv:2111.09079Cited by[1] Gabriel Waite, "The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians", arXiv:2509.25829, (2025). [2] Gabriel Waite and Karl Lin, "On the Complexity of the Succinct State Local Hamiltonian Problem", arXiv:2509.25821, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-05-06 09:11:09). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-05-06 09:11:08: Could not fetch cited-by data for 10.22331/q-2026-05-06-2097 from Crossref. This is normal if the DOI was registered recently.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. AbstractWe show the 2-Local Stoquastic Hamiltonian problem on a 2D square qubit lattice is StoqMA-complete. We achieve this by extending the spatially sparse circuit construction of Oliveira and Terhal, as well as the perturbative gadgets of Bravyi, DiVincenzo, Oliveira, and Terhal. Our main contributions demonstrate StoqMA circuits can be made spatially sparse and that geometrical, stoquastic-preserving, perturbative gadgets can be constructed, without an increase to particle dimension.Featured image: An illustration of a local stoquastic Hamiltonian constrained to a two-dimensional square lattice of qubits. Estimating the ground-state energy of such systems, in general, is StoqMA-complete.Popular summaryLocal stoquastic Hamiltonians represent a class of interacting quantum systems that avoid the sign problem of Monte Carlo simulations, making them amenable to classical algorithmic techniques. It has previously been shown that estimating the ground-state energy of such systems is intractable in general, specifically, StoqMA-complete, even for 2-local interactions. We improve this result by showing that the problem remains StoqMA-complete even when the interactions are restricted to a two-dimensional square or triangular lattice of qubits. This is achieved by extending the spatially sparse circuit construction of Oliveira and Terhal, and the perturbative gadgets of Bravyi, DiVincenzo, Oliveira and Terhal, to develop new stoquastic-preserving gadgets (Cross, Fork, Triangle) that reduce locality and planarise interaction graphs without inflating particle dimension. By working directly with qubits and not higher-dimensional particles, our results are more natural and directly relevant to real spin systems.► BibTeX data@article{Waite2026complexityoflocal, doi = {10.22331/q-2026-05-06-2097}, url = {https://doi.org/10.22331/q-2026-05-06-2097}, title = {The {C}omplexity of {L}ocal {S}toquastic {H}amiltonians on 2{D} {L}attices}, author = {Waite, Gabriel and Bremner, Michael J.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2097}, month = may, year = {2026} }► References [1] A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. ``Classical and Quantum Computation''.
American Mathematical Society. USA (2002). https://doi.org/10.1090/gsm/047 [2] Roberto Oliveira and Barbara M. Terhal. ``The complexity of quantum spin systems on a two-dimensional square lattice''. Quantum Info. Comput. 8, 900–924 (2008). arXiv:quant-ph/0504050. https://doi.org/10.26421/QIC8.10-2 arXiv:quant-ph/0504050 [3] Norbert Schuch and Frank Verstraete. ``Computational complexity of interacting electrons and fundamental limitations of density functional theory''. Nature Physics 5, 732–735 (2009). arXiv:0712.0483. https://doi.org/10.1038/nphys1370 arXiv:0712.0483 [4] Stephen Piddock and Ashley Montanaro. ``The complexity of antiferromagnetic interactions and 2D lattices''. Quantum Info. Comput. 17, 636–672 (2017). arXiv:1506.04014. https://doi.org/10.26421/QIC17.7-8-6 arXiv:1506.04014 [5] Toby S. Cubitt and Ashley Montanaro. ``Complexity Classification of Local Hamiltonian Problems''. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. Pages 120–129. FOCS '14USA (2014). IEEE Computer Society. arXiv:1311.3161. https://doi.org/10.1109/FOCS.2014.21 arXiv:1311.3161 [6] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal. ``Merlin-Arthur Games and Stoquastic Complexity'' (2006). arXiv:quant-ph/0611021. arXiv:quant-ph/0611021 [7] Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. Terhal. ``The Complexity of Stoquastic Local Hamiltonian Problems''. Quantum Inf. Comput. 8, 361–385 (2008). arXiv:quant-ph/0606140. https://doi.org/10.26421/QIC8.5-1 arXiv:quant-ph/0606140 [8] Jacob D. Biamonte and Peter J. Love. ``Realizable Hamiltonians for universal adiabatic quantum computers''. Physical Review A 78 (2008). arXiv:0704.1287. https://doi.org/10.1103/physreva.78.012352 arXiv:0704.1287 [9] Sergey Bravyi and Mikhail Vyalyi. ``Commutative version of the k-local Hamiltonian problem and common eigenspace problem''. Quantum Info. Comput. 5, 187–215 (2005). arXiv:quant-ph/0308021. https://doi.org/10.26421/QIC5.3-2 arXiv:quant-ph/0308021 [10] Norbert Schuch. ``Complexity of commuting Hamiltonians on a square lattice of qubits''. Quantum Info. Comput. 11, 901–912 (2011). arXiv:1105.2843. https://doi.org/10.26421/QIC11.11-12-1 arXiv:1105.2843 [11] Dorit Aharonov and Lior Eldar. ``On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems''. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Pages 334–343. FOCS '11USA (2011). IEEE Computer Society. arXiv:1102.0770. https://doi.org/10.1109/FOCS.2011.58 arXiv:1102.0770 [12] Dorit Aharonov and Lior Eldar. ``The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP''.
Quantum Information Processing 14, 83–101 (2014). arXiv:1311.7378. https://doi.org/10.1007/s11128-014-0877-9 arXiv:1311.7378 [13] Dorit Aharonov, Oded Kenneth, and Itamar Vigdorovich. ``On the Complexity of Two Dimensional Commuting Local Hamiltonians''. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Volume 111, pages 2:1–2:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018). arXiv:1803.02213. https://doi.org/10.4230/LIPIcs.TQC.2018.2 arXiv:1803.02213 [14] Sandy Irani and Jiaqing Jiang. ``Commuting local Hamiltonian problem on 2D beyond qubits''. Communications in Mathematical Physics 406, 273 (2025). arXiv:2309.04910. https://doi.org/10.1007/s00220-025-05462-8 arXiv:2309.04910 [15] E. Y. Loh, J. E. Gubernatis, R. T. Scalettar, S. R. White, D. J. Scalapino, and R. L. Sugar. ``Sign problem in the numerical simulation of many-electron systems''. Phys. Rev. B 41, 9301–9307 (1990). https://doi.org/10.1103/PhysRevB.41.9301 [16] Zi-Xiang Li and Hong Yao. ``Sign-Problem-Free Fermionic Quantum Monte Carlo: Developments and Applications''. Annual Review of Condensed Matter Physics 10, 337–356 (2019). arXiv:1805.08219. https://doi.org/10.1146/annurev-conmatphys-033117-054307 arXiv:1805.08219 [17] Dominik Hangleiter, Ingo Roth, Daniel Nagaj, and Jens Eisert. ``Easing the Monte Carlo sign problem''. Science Advances 6 (2020). arXiv:1906.02309. https://doi.org/10.1126/sciadv.abb8341 arXiv:1906.02309 [18] W. M. C. Foulkes, L. Mitas, R. J. Needs, and G. Rajagopal. ``Quantum Monte Carlo simulations of solids''. Rev. Mod. Phys. 73, 33–83 (2001). https://doi.org/10.1103/RevModPhys.73.33 [19] Anders W. Sandvik, Adolfo Avella, and Ferdinando Mancini. ``Computational studies of quantum spin systems''. In AIP Conference Proceedings. AIP (2010). arXiv:1101.3281. https://doi.org/10.1063/1.3518900 arXiv:1101.3281 [20] Masayuki Ohzeki. ``Quantum Monte Carlo simulation of a particular class of non-stoquastic Hamiltonians in quantum annealing''. Scientific Reports 7 (2017). arXiv:1612.04785. https://doi.org/10.1038/srep41186 arXiv:1612.04785 [21] Sergey Bravyi, Giuseppe Carleo, David Gosset, and Yinchen Liu. ``A rapidly mixing Markov chain from any gapped quantum many-body system''. Quantum 7, 1173 (2023). arXiv:2207.07044. https://doi.org/10.22331/q-2023-11-07-1173 arXiv:2207.07044 [22] Lev Barash, Arman Babakhani, and Itay Hen. ``Quantum Monte Carlo algorithm for arbitrary spin-1/2 Hamiltonians''. Phys. Rev. Res. 6, 013281 (2024). arXiv:2307.06503. https://doi.org/10.1103/PhysRevResearch.6.013281 arXiv:2307.06503 [23] D. F. B. ten Haaf, H. J. M. van Bemmel, J. M. J. van Leeuwen, W. van Saarloos, and D. M. Ceperley. ``Proof for an upper bound in fixed-node Monte Carlo for lattice fermions''. Phys. Rev. B 51, 13039–13045 (1995). https://doi.org/10.1103/PhysRevB.51.13039 [24] Dorit Aharonov, Alex B Grilo, and Yupan Liu. ``StoqMA vs. MA: the power of error reduction''. Quantum 9, 1853 (2025). arXiv:2010.02835. https://doi.org/10.22331/q-2025-09-11-1853 arXiv:2010.02835 [25] Yupan Liu. ``StoqMA Meets Distribution Testing''. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Volume 197, pages 4:1–4:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021). arXiv:2011.05733. https://doi.org/10.4230/LIPIcs.TQC.2021.4 arXiv:2011.05733 [26] Chris Marriott and John Watrous. ``Quantum Arthur-Merlin games''. Computational Complexity 14, 122–152 (2005). arXiv:cs/0506068. https://doi.org/10.1007/s00037-005-0194-x arXiv:cs/0506068 [27] Sergey Bravyi and Barbara Terhal. ``Complexity of Stoquastic Frustration-Free Hamiltonians''. SIAM J. Comput. 39, 1462–1485 (2009). arXiv:0806.1746. https://doi.org/10.1137/08072689X arXiv:0806.1746 [28] Sergey Bravyi and Matthew Hastings. ``On Complexity of the Quantum Ising Model''. Communications in Mathematical Physics 349, 1–45 (2016). arXiv:1410.0703. https://doi.org/10.1007/s00220-016-2787-4 arXiv:1410.0703 [29] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans. ``Improved Hardness Results for the Guided Local Hamiltonian Problem''. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Volume 261, pages 32:1–32:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). arXiv:2207.10250. https://doi.org/10.4230/LIPIcs.ICALP.2023.32 arXiv:2207.10250 [30] Asad Raza, Jens Eisert, and Alex B Grilo. ``Complexity of geometrically local stoquastic Hamiltonians''. Quantum 10, 2004 (2026). arXiv:2407.15499. https://doi.org/10.22331/q-2026-02-11-2004 arXiv:2407.15499 [31] Sevag Gharibian. ``Guest Column: The 7 faces of quantum NP''. SIGACT News 54, 54–91 (2024). arXiv:2310.18010. https://doi.org/10.1145/3639528.3639535 arXiv:2310.18010 [32] Stathis Zachos and Martin Furer. ``Probabilistic quantifiers vs. distrustful adversaries''. In Proc. of the Seventh Conference on Foundations of Software Technology and Theoretical Computer Science. Pages 443–455. Berlin, Heidelberg (1987). Springer-Verlag. https://doi.org/10.1007/3-540-18625-5_67 [33] Julia Kempe, Alexei Kitaev, and Oded Regev. ``The Complexity of the Local Hamiltonian Problem''. SIAM Journal on Computing 35, 1070–1097 (2006). arXiv:quant-ph/0406180. https://doi.org/10.1137/S0097539704445226 arXiv:quant-ph/0406180 [34] Sergey Bravyi, David P. DiVincenzo, and Daniel Loss. ``Schrieffer-Wolff transformation for quantum many-body systems''. Annals of Physics 326, 2793–2826 (2011). arXiv:1105.0675. https://doi.org/10.1016/j.aop.2011.06.004 arXiv:1105.0675 [35] Sergey Bravyi, David P. DiVincenzo, Daniel Loss, and Barbara M. Terhal. ``Quantum Simulation of Many-Body Hamiltonians Using Perturbation Theory with Bounded-Strength Interactions''. Phys. Rev. Lett. 101, 070503 (2008). arXiv:0803.2686. https://doi.org/10.1103/PhysRevLett.101.070503 arXiv:0803.2686 [36] Gabriel Waite, Ryan L Mann, and Samuel J Elman. ``The Hamiltonian Jungle'' (2023). [37] A.L. Fetter and J.D. Walecka. ``Quantum Theory of Many-Particle Systems''. Dover Books on Physics. Dover Publications. (2012). url: https://books.google.com.au/books?id=t5_DAgAAQBAJ. https://books.google.com.au/books?id=t5_DAgAAQBAJ [38] Marios Ioannou, Stephen Piddock, Milad Marvian, Joel Klassen, and Barbara M. Terhal. ``Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing'' (2022). arXiv:2007.11964. arXiv:2007.11964 [39] Sergey Bravyi and David Gosset. ``Polynomial-Time Classical Simulation of Quantum Ferromagnets''. Phys. Rev. Lett. 119, 100503 (2017). arXiv:1612.05602. https://doi.org/10.1103/PhysRevLett.119.100503 arXiv:1612.05602 [40] Stephen Piddock. ``Complexity and Simulation of Many-Body Quantum Systems''. Phd thesis. University of Bristol. (2019). url: https://research-information.bris.ac.uk/en/studentTheses/complexity-and-simulation-of-many-body-quantum-systems/. https://research-information.bris.ac.uk/en/studentTheses/complexity-and-simulation-of-many-body-quantum-systems/ [41] Sergey Bravyi. ``Monte Carlo simulation of stoquastic Hamiltonians''. Quantum Info. Comput. 15, 1122–1140 (2015). arXiv:1402.2295. https://doi.org/10.26421/QIC15.13-14-3 arXiv:1402.2295 [42] Alex Bredariol Grilo, Iordanis Kerenidis, and Jamie Sikora. ``QMA with Subset State Witnesses''. Pages 163–174.
Springer Berlin Heidelberg. (2015). arXiv:1410.2882. https://doi.org/10.1007/978-3-662-48054-0_14 arXiv:1410.2882 [43] Sevag Gharibian and François Le Gall. ``Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture''. SIAM Journal on Computing 52, 1009–1038 (2023). arXiv:2111.09079. https://doi.org/10.1137/22M1513721 arXiv:2111.09079Cited by[1] Gabriel Waite, "The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians", arXiv:2509.25829, (2025). [2] Gabriel Waite and Karl Lin, "On the Complexity of the Succinct State Local Hamiltonian Problem", arXiv:2509.25821, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-05-06 09:11:09). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-05-06 09:11:08: Could not fetch cited-by data for 10.22331/q-2026-05-06-2097 from Crossref. This is normal if the DOI was registered recently.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.