[{"publisher":"Springer Berlin Heidelberg","date_created":"2019-03-01T11:37:54Z","title":"Ground State Connectivity of Local Hamiltonians","year":"2015","external_id":{"arxiv":["1409.3182"]},"language":[{"iso":"eng"}],"publication":"International Colloquium on Automata, Languages, and Programming (ICALP 2015)","abstract":[{"text":"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.","lang":"eng"}],"oa":"1","date_updated":"2023-02-28T11:02:07Z","author":[{"first_name":"Sevag","full_name":"Gharibian, Sevag","id":"71541","orcid":"0000-0002-9992-3379","last_name":"Gharibian"},{"last_name":"Sikora","full_name":"Sikora, Jamie","first_name":"Jamie"}],"conference":{"location":"Kyoto, Japan","name":"International Colloquium on Automata, Languages, and Programming (ICALP)"},"doi":"10.1007/978-3-662-47672-7_50","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1409.3182"}],"publication_identifier":{"isbn":["978-3-662-47672-7"]},"publication_status":"published","place":"Berlin, Heidelberg","page":"617-628","citation":{"ieee":"S. Gharibian and J. Sikora, “Ground State Connectivity of Local Hamiltonians,” in <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>, Kyoto, Japan, 2015, pp. 617–628, doi: <a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>.","chicago":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” In <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>, edited by Magn{\\’u}s M. Halld{\\’o}rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, 617–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">https://doi.org/10.1007/978-3-662-47672-7_50</a>.","ama":"Gharibian S, Sikora J. Ground State Connectivity of Local Hamiltonians. In: Halld{\\’o}rsson MM, Iwama K, Kobayashi N, Speckmann B, eds. <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>. Springer Berlin Heidelberg; 2015:617-628. doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>","apa":"Gharibian, S., &#38; Sikora, J. (2015). Ground State Connectivity of Local Hamiltonians. In M. M. Halld{\\’o}rsson, K. Iwama, N. Kobayashi, &#38; B. Speckmann (Eds.), <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i> (pp. 617–628). Springer Berlin Heidelberg. <a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">https://doi.org/10.1007/978-3-662-47672-7_50</a>","bibtex":"@inproceedings{Gharibian_Sikora_2015, place={Berlin, Heidelberg}, title={Ground State Connectivity of Local Hamiltonians}, DOI={<a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>}, 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, Bettina}, year={2015}, pages={617–628} }","mla":"Gharibian, Sevag, and Jamie Sikora. “Ground State Connectivity of Local Hamiltonians.” <i>International Colloquium on Automata, Languages, and Programming (ICALP 2015)</i>, edited by Magn{\\’u}s M. Halld{\\’o}rsson et al., Springer Berlin Heidelberg, 2015, pp. 617–28, doi:<a href=\"https://doi.org/10.1007/978-3-662-47672-7_50\">10.1007/978-3-662-47672-7_50</a>.","short":"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."},"_id":"8164","department":[{"_id":"623"},{"_id":"7"}],"user_id":"71541","type":"conference","editor":[{"first_name":"Magn{\\'u}s M.","last_name":"Halld{\\'o}rsson","full_name":"Halld{\\'o}rsson, Magn{\\'u}s M."},{"last_name":"Iwama","full_name":"Iwama, Kazuo","first_name":"Kazuo"},{"last_name":"Kobayashi","full_name":"Kobayashi, Naoki","first_name":"Naoki"},{"last_name":"Speckmann","full_name":"Speckmann, Bettina","first_name":"Bettina"}],"status":"public"}]