---
_id: '8164'
abstract:
- lang: eng
  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.
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Jamie
  full_name: Sikora, Jamie
  last_name: Sikora
citation:
  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} }'
  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>.'
  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>.'
  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.'
conference:
  location: Kyoto, Japan
  name: International Colloquium on Automata, Languages, and Programming (ICALP)
date_created: 2019-03-01T11:37:54Z
date_updated: 2023-02-28T11:02:07Z
department:
- _id: '623'
- _id: '7'
doi: 10.1007/978-3-662-47672-7_50
editor:
- first_name: Magn{\'u}s M.
  full_name: Halld{\'o}rsson, Magn{\'u}s M.
  last_name: Halld{\'o}rsson
- first_name: Kazuo
  full_name: Iwama, Kazuo
  last_name: Iwama
- first_name: Naoki
  full_name: Kobayashi, Naoki
  last_name: Kobayashi
- first_name: Bettina
  full_name: Speckmann, Bettina
  last_name: Speckmann
external_id:
  arxiv:
  - '1409.3182'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1409.3182
oa: '1'
page: 617-628
place: Berlin, Heidelberg
publication: International Colloquium on Automata, Languages, and Programming (ICALP
  2015)
publication_identifier:
  isbn:
  - 978-3-662-47672-7
publication_status: published
publisher: Springer Berlin Heidelberg
status: public
title: Ground State Connectivity of Local Hamiltonians
type: conference
user_id: '71541'
year: '2015'
...