Time: Friday, Apr 26, 2-3pm
Location: 6C-442
Speaker: Toby Cubitt (U. Cambridge)
Title: 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.
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip