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] 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, "The 7 faces of quantum NP", arXiv:2310.18010, (2023).

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 18:03:05) and SAO/NASA ADS (last updated successfully 2023-11-29 18:03:06). 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.