Undecidability of the spectral gap

The spectral gap – the difference between the smallest and
second-smallest eigenvalue of a quantum many-body Hamiltonian – is of
central importance to quantum many-body physics. It determines the phase
diagram at low temperature, with quantum phase transitions occurring when
the gap vanishes. Some of the most challenging and long-standing open
problems in theoretical physics concern the spectral gap, such as the
famous Haldane conjecture, or the infamous Yang-Mills gap conjecture (one
of the Millennium Prize problems). These problems – and many others – are
all particular cases of the general spectral gap problem: Given a quantum
many-body Hamiltonian, is the system it describes gapped or gapless?

We prove that this problem is undecidable (in the Goedel and Turing
sense). Our results also extend to many other important zero-temperature
properties of quantum many-body systems, such as correlation functions.

The proof is by reduction from the Halting problem. But the construction
is complex and draws on a wide variety of techniques, ranging from
spectral theory, Hamiltonian complexity theory, quantum algorithms, and
new results on aperiodic tilings.

I will explain the result, sketch the techniques involved in the proof at
an accessible level, discuss the striking implications this may have for
physics, and outline some interesting computability questions related to
this problem that remain open.

Based on the following papers:

Undecidability of the Spectral Gap
Toby Cubitt, David Perez-Garcia and Michael Wolf
Nature, 528, p207-211, (2015)
arXiv:1502.04135[quant-ph]

Undecidability of the Spectral Gap (full version, 143 pages)
Toby Cubitt, David Perez-Garcia and Michael Wolf
arXiv:1502.04573[quant-ph]

• Speaker: Toby Cubitt (University College London)
• Thursday 16 February 2017, 15:00–16:00
• Venue: MR 14, CMS.
• Series: Applied and Computational Analysis; organiser: Dr Hansen.