## Undecidability of the spectral gap

### With Toby Cubitt (University College London)

# 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.