@inproceedings{8164,
  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.}},
  author       = {{Gharibian, Sevag and Sikora, Jamie}},
  booktitle    = {{International Colloquium on Automata, Languages, and Programming (ICALP 2015)}},
  editor       = {{Halld{\'o}rsson, Magn{\'u}s M. and Iwama, Kazuo and Kobayashi, Naoki and Speckmann, Bettina}},
  isbn         = {{978-3-662-47672-7}},
  location     = {{Kyoto, Japan}},
  pages        = {{617--628}},
  publisher    = {{Springer Berlin Heidelberg}},
  title        = {{{Ground State Connectivity of Local Hamiltonians}}},
  doi          = {{10.1007/978-3-662-47672-7_50}},
  year         = {{2015}},
}