  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. Roughly, "ground state
connectivity" corresponds to the natural question: Given two ground states
|{\psi}> and |{\phi}> of a local Hamiltonian H, is there an "energy barrier"
(with respect to H) along any sequence of local operations mapping |{\psi}> to
|{\phi}>? We show that the complexity of this question 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.
