QCMA hardness of ground space connectivity for commuting Hamiltonians

David Gosset1,2, Jenish C. Mehta1, and Thomas Vidick1

1California Institute of Technology
2IBM T.J Watson Research Center

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


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

► References

[1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. 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.

[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.

[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.

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

[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.

[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.

[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.

[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.

[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.

[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=

[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.

[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] Sevag Gharibian and Justin Yirka, "The complexity of simulating local measurements on quantum systems", Quantum 3, 189 (2019).

[3] 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).

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-19 08:24:32) and SAO/NASA ADS (last updated successfully 2024-04-19 08:24:33). The list may be incomplete as not all publishers provide suitable and complete citation data.