skip to content

Undecidability of the spectral gap problem

Presented by: 
TS Cubitt University of Cambridge
Monday 2nd September 2013 - 16:30 to 17:30
INI Seminar Room 1
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!).

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons