Ground State Connectivity of Local Hamiltonians

S. Gharibian, J. Sikora, in: M.M. Halld{\’o}rsson, K. Iwama, N. Kobayashi, B. Speckmann (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2015), Springer Berlin Heidelberg, Berlin, Heidelberg, 2015, pp. 617–628.

Conference Paper | Published | English
Author
;
Editor
; ; ;
Department
Abstract
The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this paper, we take a new direction by introducing the physically motivated notion of ``ground state connectivity'' of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. We show that determining how ``connected'' the ground space of a local Hamiltonian is can range from QCMA-complete to PSPACE-complete, as well as NEXP-complete for an appropriately defined ``succinct'' version of the problem. As a result, we obtain a natural QCMA-complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is essentially tight with respect to the length of the unitary evolution in question.
Publishing Year
Proceedings Title
International Colloquium on Automata, Languages, and Programming (ICALP 2015)
Page
617-628
Conference
International Colloquium on Automata, Languages, and Programming (ICALP)
Conference Location
Kyoto, Japan
LibreCat-ID

Cite this

Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. In: Halld{\’o}rsson MM, Iwama K, Kobayashi N, Speckmann B, eds. International Colloquium on Automata, Languages, and Programming (ICALP 2015). Berlin, Heidelberg: Springer Berlin Heidelberg; 2015:617-628. doi:10.1007/978-3-662-47672-7_50
Gharibian, S., & Sikora, J. (2015). Ground State Connectivity of Local Hamiltonians. In M. M. Halld{\’o}rsson, K. Iwama, N. Kobayashi, & B. Speckmann (Eds.), International Colloquium on Automata, Languages, and Programming (ICALP 2015) (pp. 617–628). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_50
@inproceedings{Gharibian_Sikora_2015, place={Berlin, Heidelberg}, title={Ground State Connectivity of Local Hamiltonians}, DOI={10.1007/978-3-662-47672-7_50}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP 2015)}, publisher={Springer Berlin Heidelberg}, author={Gharibian, Sevag and Sikora, Jamie}, editor={Halld{\’o}rsson, Magn{\’u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, BettinaEditors}, year={2015}, pages={617–628} }
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” In International Colloquium on Automata, Languages, and Programming (ICALP 2015), edited by Magn{\’u}s M. Halld{\’o}rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, 617–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. https://doi.org/10.1007/978-3-662-47672-7_50.
S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” in International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 2015, pp. 617–628.
Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” International Colloquium on Automata, Languages, and Programming (ICALP 2015), edited by Magn{\’u}s M. Halld{\’o}rsson et al., Springer Berlin Heidelberg, 2015, pp. 617–28, doi:10.1007/978-3-662-47672-7_50.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1409.3182

Search this title in

Google Scholar
ISBN Search