QCMA hardness of ground space connectivity for commuting Hamiltonians

David Gosset; Jenish C. Mehta; Thomas Vidick

doi:10.22331/q-2017-07-14-16

QCMA hardness of ground space connectivity for commuting Hamiltonians

David Gosset^1,2, Jenish C. Mehta¹, and Thomas Vidick¹

¹California Institute of Technology
²IBM T.J Watson Research Center

Published:	2017-07-14, volume 1, page 16
Eprint:	arXiv:1610.03582v2
Doi:	https://doi.org/10.22331/q-2017-07-14-16
Citation:	Quantum 1, 16 (2017).

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

Abstract

In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian $H$. It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.

► BibTeX data

@article{Gosset2017qcmahardnessof,
  doi = {10.22331/q-2017-07-14-16},
  url = {https://doi.org/10.22331/q-2017-07-14-16},
  title = {{QCMA} hardness of ground space connectivity for commuting {H}amiltonians},
  author = {Gosset, David and Mehta, Jenish C. and Vidick, Thomas},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {1},
  pages = {16},
  month = jul,
  year = {2017}
}

► References

[1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. https://doi.org/10.1017/CBO9780511804090.
https://doi.org/10.1017/CBO9780511804090

[2] Dorit Aharonov and Lior Eldar. On the complexity of commuting local Hamiltonians, and tight conditions for topological order in such systems. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 334–343. IEEE, 2011. https://doi.org/10.1109/FOCS.2011.58.
https://doi.org/10.1109/FOCS.2011.58

[3] Dorit Aharonov, Daniel Gottesman, Sandy Irani, and Julia Kempe. The power of quantum systems on a line. Communications in Mathematical Physics, 287(1):41–65, 2009. https://doi.org/10.1109/FOCS.2007.46.
https://doi.org/10.1109/FOCS.2007.46

[4] Benjamin J Brown, Daniel Loss, Jiannis K Pachos, Chris N Self, and James R Wootton. Quantum memories at finite temperature. Reviews of Modern Physics, 88(4):045005, 2016. http://dx.doi.org/10.1103/RevModPhys.88.045005.
https://doi.org/10.1103/RevModPhys.88.045005

[5] Sergey Bravyi and Mikhail Vyalyi. Commutative version of the k-local Hamiltonian problem and common eigenspace problem. arXiv preprint quant-ph/0308021, 2003.
arXiv:quant-ph/0308021

[6] Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, pages 151–158. ACM, 1971. https://doi.org/10.1145/800157.805047.
https://doi.org/10.1145/800157.805047

[7] Parikshit Gopalan, Phokion G Kolaitis, Elitza Maneva, and Christos H Papadimitriou. The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM Journal on Computing, 38(6):2330–2355, 2009. https://doi.org/10.1137/07070440X.
https://doi.org/10.1137/07070440X

[8] Sevag Gharibian and Jamie Sikora. Ground state connectivity of local Hamiltonians. In Automata, Languages, and Programming, pages 617–628. Springer, 2015. https://link.springer.com/chapter/10.1007/978-3-662-47672-7_50.
https://link.springer.com/chapter/10.1007/978-3-662-47672-7_50

[9] A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2–30, 2003. https://doi.org/10.1016/S0003-4916(02)00018-0.
https://doi.org/10.1016/S0003-4916(02)00018-0

[10] Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local Hamiltonian problem. SIAM Journal on Computing, 35(5):1070–1097, 2006. http://dx.doi.org/10.1137/S0097539704445226.
https://doi.org/10.1137/S0097539704445226

[11] Julia Kempe and Oded Regev. 3-local Hamiltonian is QMA-complete. arXiv preprint quant-ph/0302079, 2003. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.252.4841.
arXiv:quant-ph/0302079
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.252.4841

[12] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation, volume 47. American Mathematical Society Providence, 2002. http://dx.doi.org/10.1090/gsm/047.
https://doi.org/10.1090/gsm/047

[13] Roberto Oliveira and Barbara M Terhal. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Information & Computation, 8(10):900–924, 2008.

[14] Norbert Schuch. Complexity of commuting Hamiltonians on a square lattice of qubits. Quantum Information & Computation, 11(11-12):901–912, 2011.

[15] John Watrous. Theory of quantum information. University of Waterloo Fall, 128, 2011.

Cited by

[1] Daniel Nagaj, Dominik Hangleiter, Jens Eisert, and Martin Schwarz, "Pinned quantum Merlin-Arthur: The power of fixing a few qubits in proofs", Physical Review A 103 1, 012604 (2021).

[2] Sandy Irani and Jiaqing Jiang, "Commuting Local Hamiltonian Problem on 2D Beyond Qubits", Communications in Mathematical Physics 406 11, 273 (2025).

[3] "Simulation of atomic nuclei and their constituents with quantum computers", université Paris-Saclay (2023).

[4] Sevag Gharibian and Justin Yirka, "The complexity of simulating local measurements on quantum systems", Quantum 3, 189 (2019).

[5] S. C. Morampudi, B. Hsu, S. L. Sondhi, R. Moessner, and C. R. Laumann, "Clustering in Hilbert space of a quantum optimization problem", Physical Review A 96 4, 042303 (2017).

[6] Sevag Gharibian, "Guest Column: The 7 faces of quantum NP", ACM SIGACT News 54 4, 54 (2023).

[7] Mahmoud Naderi, Muhammad Naveed Zafar, Marko Pezer, and Manuel Mazzara, Lecture Notes on Data Engineering and Communications Technologies 300, 253 (2026) ISBN:978-3-032-23340-0.

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

[9] Andres Ruiz, "Symmetry breaking and restoration for many-body problems treated on quantum computers", arXiv:2310.17996, (2023).

[10] John Bostanci and Yeongwoo Hwang, "Commuting Local Hamiltonians Beyond 2D", arXiv:2410.10495, (2024).

[11] Sevag Gharibian and Jonas Kamminga, "On the complexity of estimating ground state entanglement and free energy", arXiv:2510.06796, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-11-02 19:28:35) and SAO/NASA ADS (last updated successfully 2026-11-02 19:28:36). 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.