Sevag Gharibian, University of California, Berkeley
The study of ground spaces of local Hamiltonians is a fundamental task
in condensed matter physics. In terms of computational complexity
theory, a common focus in this area has been to estimate a given
Hamiltonian’s ground state energy. However, from a physics
perspective, it is often more relevant to understand the structure of
the ground space itself. In this paper, we pursue the latter direction
by introducing the notion of “ground state connectivity” of local
Hamiltonians. In particular, we show that determining how “connected”
the ground space of a local Hamiltonian is can range from
QCMA-complete to PSPACE-complete. (Here, QCMA is the well-known
variant of Quantum Merlin Arthur (QMA) in which the proof is
classical.) As a result, we obtain a natural QCMA-complete problem, a
task which has generally proven difficult since the conception of QCMA
over a decade ago.
This talk is based on joint work with Jamie Sikora.