  The field of quantum Hamiltonian complexity lies at the intersection of
quantum many-body physics and computational complexity theory, with deep
implications to both fields. The main object of study is the LocalHamiltonian
problem, which is concerned with estimating the ground-state energy of a local
Hamiltonian and is complete for the class QMA, a quantum generalization of the
class NP. A major challenge in the field is to understand the complexity of the
LocalHamiltonian problem in more physically natural parameter regimes. One
crucial parameter in understanding the ground space of any Hamiltonian in
many-body physics is the spectral gap, which is the difference between the
smallest two eigenvalues. Despite its importance in quantum many-body physics,
the role played by the spectral gap in the complexity of the LocalHamiltonian
is less well-understood. In this work, we make progress on this question by
considering the precise regime, in which one estimates the ground-state energy
to within inverse exponential precision. Computing ground-state energies
precisely is a task that is important for quantum chemistry and quantum
many-body physics.
  In the setting of inverse-exponential precision, there is a surprising result
that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the
class of problems solvable in polynomial space. We clarify the reason behind
this boost in complexity. Specifically, we show that the full complexity of the
high precision case only comes about when the spectral gap is exponentially
small. As a consequence of the proof techniques developed to show our results,
we uncover important implications for the representability and circuit
complexity of ground states of local Hamiltonians, the theory of uniqueness of
quantum witnesses, and techniques for the amplification of quantum witnesses in
the presence of postselection.
