Undecidability of the Spectral Gap (full version)

Abstract

We show that the spectral gap problem is undecidable. Specifically, we construct families of translationally-invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant in the thermodynamic limit. Moreover, this constant can be taken equal to the local interaction strength of the Hamiltonian.

v1: 146 pages, 56 theorems etc, 15 figs. See shorter companion paper arXiv:1502.04135 for version omitting technical details. v2: Small fix to abstract wording. v3: Simplified and shortened parts of proof. 127p, 55 thms, 10 figs. v4: Minor intro edits. v5: Published version. Adds explanatory pseudo-code for all Turing Machines, and other presentational improvements. 150 pages, 55 thms, 13 figs

References in corpus (22)

• Lieb-Robinson Bounds and the Exponential Clustering Theorem
• Undecidability of the Spectral Gap (short version)
• The power of quantum systems on a line
• Entropy and Entanglement in Quantum Ground States
• Stochastic Error Cancellation in Analog Quantum Simulation
• Matrix product operators and states: NP-hardness and undecidability
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Tsirelson's problem and an embedding theorem for groups arising from non-local games
• Persistence of exponential decay and spectral gaps for interacting fermions
• Fundamental limitations in the purifications of tensor networks
• Demonstrating the AKLT spectral gap on 2D degree-3 lattices
• Existence of a Spectral Gap in the Affleck-Kennedy-Lieb-Tasaki Model on the Hexagonal Lattice
• Undecidability of the Spectral Gap in One Dimension
• Size-Driven Quantum Phase Transitions
• Memory effects can make the transmission capability of a communication channel uncomputable
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Non-signaling deterministic models for non-local correlations have to be uncomputable
• Uncomputability of Phase Diagrams
• Measurement-based quantum computation and undecidable logic
• The Stability of Free Fermi Hamiltonians
• Open problems in mathematical physics
• On the uncomputability of the spectral gap

Cited by in corpus (7)

• Some Problems in Density Functional Theory
• Uncomputably Complex Renormalisation Group Flows
• Undecidability in Physics: a Review
• Duality-preserving deformation of 3+1d lattice ${\mathbb{Z}}_2$ gauge theory with exact gapped ground states
• Stability of the spectral gap and ground state indistinguishability for a decorated AKLT model
• On the set of reduced states of translation invariant, infinite quantum systems
• A Hierarchy of Spectral Gap Certificates for Frustration-Free Spin Systems