Ground State Connectivity of Local Hamiltonians

The study of ground state energies of local Hamiltonians is a natural generalization of the study of classical constraint satisfaction problems, and has thus played a fundamental role in quantum complexity theory. In this talk, we take a new direction by introducing the physically well-motivated notion of "ground state connectivity" of local Hamiltonians, which can be thought of as a quantum generalization of classical reconfiguration problems. In particular, ground state connectivity 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 NEXP-complete (where QCMA stands for Quantum-Classical Merlin Arthur, a quantum generalization of NP). 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, and which may be of independent interest. (Joint work with Jamie Sikora. No background in quantum computing is assumed.)