Abstract
Determining spectral gaps in the thermodynamic limit is a central challenge in quantum many-body physics. When a fixed boundary condition is imposed, this problem is undecidable: no algorithm, even with unlimited resources, can decide for every Hamiltonian whether it is gapped. Yet the thermodynamic limit is meant to capture the intrinsic properties of very large systems, which should not depend on how their boundaries are chosen. Here, we therefore consider the bulk spectral gap problem, which concerns only the intrinsic excitations of the infinite system, independently of any boundary. We first give a general algorithm, based on a hierarchy of semidefinite programs, that produces certified upper bounds on the bulk gap of any finite-range system, arbitrarily tight at the cost of more computation. Second, we prove that no algorithm can decide whether the bulk gap is positive, already for translationally invariant nearest-neighbour chains of fixed local dimension. The bulk spectral gap is thus certifiable from above but uncomputable from below: deciding whether it vanishes, under the promise that it is either zero or at least a constant, is RE-complete. Consequently, no general algorithm producing convergent upper bounds, ours included, admits a computable convergence rate. The same construction also shows that deciding whether an explicitly given product state is a ground state of the infinite system is undecidable, and that convergent bounds on ground-state expectation values admit no computable convergence rate in general. Finally, we obtain the first nontrivial certified upper bounds on the bulk gap of the spin-1/2 kagome Heisenberg antiferromagnet.
