Skip to content



Undecidability of the spectral gap problem

Cubitt, TS (University of Cambridge)
Monday 02 September 2013, 16:30-17:30

Seminar Room 1, Newton Institute


Co-authors: David Perez-Garcia (Universidad Complutense de Madrid), Michael Wolf (Technische Universität München)

The spectral gap of a quantum many-body Hamiltonian plays a crucial role in determining its physical properties. In particular, it determines the phase diagram of the system, with quantum phase transitions occurring where the spectral gap vanishes.

A number of longstanding open problems in mathematical physics, such as the Haldane conjecture or the 2D AKLT gap conjecture, concern spectral gaps of particular many-body models. In the related setting of quantum field theories, determining if Yang-Mills theory is gapped is one of the Millennium Prize Problems. Numerous important results about many-body Hamiltonians only apply to gapped systems. Determining when a model is gapped or gapless is therefore one of the primary goals of theoretical condensed matter physics.

I will show that the spectral gap problem is unsolvable in general. Specifically, we prove that there exist translationally-invariant Hamiltonians on a 2D square lattice of finite-dimensional spins, with two-body nearest-neighbour interactions, for which the spectral gap problem is undecidable. This means that there exist Hamiltonians for which the presence or absence of a spectral gap cannot be proven in any consistent framework of mathematics.

The proof is (of course!) by reduction from the Halting Problem. But the construction is complex, and draws on a wide variety of techniques: from quantum algorithms and quantum computing, to classical tiling problems, to recent Hamiltonian complexity results, to even more recent PEPS constructions. I will explain the result, sketch the techniques involved in the proof, and discuss what implications this might have for physics (which after all happens in the laboratory, not in Hilbert space!).


This talk has not been recorded because the speaker withheld their permission

Back to top ∧