Undecidability of the Spectral Gap (full version)

Understand

We show that the spectral gap problem is undecidable.

• Specifically, we construct families of translationally-invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem.
• This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant in the thermodynamic limit.
• Moreover, this constant can be taken equal to the local interaction strength of the Hamiltonian.