Undecidability of the spectral gap

Add to your list(s) Download to your calendar using vCal

• Toby Cubitt (University College London)
• Thursday 16 February 2017, 15:00-16:00
• MR 14, CMS.

If you have a question about this talk, please contact Dr Hansen.

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]

This talk is part of the Applied and Computational Analysis series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• Applied and Computational Analysis
• CMS Events
• DAMTP info aggregator
• Featured lists
• Interested Talks
• MR 14, CMS
• My seminars
• Type the title of a new list here
• bld31

Note that ex-directory lists are not shown.