Undecidability of the spectral gap problem
Seminar author:Toby Cubitt
Event date and time:07/16/2013 03:15:pm
Event location:Sala de Graus II (C5 building, Ciències UAB)
Event contact:
The spectral gap of a quantum many-body Hamiltonian — the difference between the ground state energy and lowest excited state in the thermodynamic limit — plays a crucial role in determining the physical properties of a many-body system. In particular, it determines the phase diagram of the system, with quantum phase transitions occurring at critical points, where the spectral gap vanishes.
A number of famous longstanding open problems in mathematical physics concern spectral gaps of particular many-body models, such as the “Haldane conjecture” for the 1D Heisenberg chain, or the gap conjecture for the 2D AKLT model. In the related setting of quantum field theories, determining if Yang-Mills theory is gapped is one of the Millennium Prize Problems, with a $1 million prize attached. Many algorithmic, complexity theoretic, information theoretic, and condensed matter physics results for 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 nearest-neighbour interactions, for which the spectral gap problem is undecidable. Thus 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 quite 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 results. I will explain the result, sketch the techniques involved in the proof, and discuss what implications this might have for real physics (which after all happens in the laboratory, not in Hilbert space!)
[Based on ongoing work with David Perez-Garcia and Michael Wolf.]
