[QIP-Sem] QIP seminar, Fri 4/26, 2:00 PM, 6C-442, Toby Cubitt

[Peter Shor]

MIT Quantum Information Processing seminar
Friday 4/26 at 2:00 PM in 6C-442
-------------------------------------------------

 Toby Cubitt (University of Cambridge)

Undecidability of the spectral gap question

Abstract:

The spectral gap of a quantum many-body Hamiltonian -- the difference between the ground state energy (lowest eigenvalue) and lowest excited state (next-lowest eigenvalue, ignoring degeneracies) in the thermodynamic limit (limit of arbitrarily large system size) -- plays an important 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 open problems in mathematical physics concern whether or not particular many-body models are gapped. For example, the "Haldane conjecture" states that Heisenberg spin chains are gapped for integer spin, and gapless for half-integer spin. The seminal result by Lieb-Schultz-Mattis proves the half-integer case. But, whilst there exists strong numerical evidence, the integer case remains unproven. In 2-dimensions, there is a longstanding conjecture that the 2D AKLT model is gapped. 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.

I will show that the general spectral gap problem is unsolvable. Specifically, 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 gapless Hamiltonians for which the absence of a gap cannot be proven in any consistent framework of mathematics.

The proof is (of course!) by reduction from the Halting Problem. But the argument is quite complex, and draws on a wide variety of techniques, ranging from quantum algorithms and quantum computing, to classical tiling problems, to recent Hamiltonian complexity results, to an even more recent construction of gapless PEPS parent Hamiltonians. I will explain the result, sketch the techniques involved in the proof, and discuss what implications this might have for physics.

Based on ongoing work with David Perez-Garcia and Michael Wolf.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem