Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Undecidability of the Spectral Gap

J.B. Houben

Published Jan 1, 2016• 0 citations
OpenAlex

Abstract

We treat the results of the 2015 paper by Cubitt et al. entitled “Undecidability of the Spectral Gap”, and the constructions required to arrive at these results. This paper showed that a specific quantum mechanical problem (the “spectral gap problem”) is algorithmically undecidable, using techniques from computer science. We also treat the theory from quantum mechanics and computer science that is required to understand these results and constructions.

Related papers

Why Some Physicists Are Excited About the Undecidability of the Spectral Gap Problem and Why Should We

Владик Крейнович

Since Turing's time, many problems have been proven undecidable. It is interesting though that, arguably, none of the working physicist problems had been ever proven undecidable -- until T. Cubitt, D. Perez-Garcia and M. M. Wolf proved recently that, for a physically reasonable class of systems, no algorithm can decide whether a given system has a spectral gap. We explain the spectral gap problem, its importance for physics and possible consequences of this exciting new result.

Bulletin of the European Association for Theoretical Computer Science•Jun 1, 2017•2 citations

Spectral Gap Undecidability Dominates Quantum Many-Body Physics — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability of the spectral gap in quantum many-body systems (Cubitt et al.) is the dominant mathematical result; other findings are peripheral (hexaquark SU(3) multiplet, graph recoloring, spectral line precision, traffic models, leaf counting). | MATH: The spectral gap problem: given a translationally-invariant Hamiltonian \( H = \sum_i h_i \) on a 2D lattice (finite local Hilbert space), determining whether the gap \( \Delta = E_1 - E_0 \) (difference between ground state and first excited energy) is zero or positive is undecidable. This maps the halting problem onto the gap via a construction where the gap closes iff a Turing machine halts. Key constants: no specific numeric constants, but the proof uses a lattice of qudits with local dimension \( d \geq 2 \) (often \( d=2 \) suffices for the 2D case), and relies on the existence of a "gadget" Hamiltonian whose spectrum encodes the machine's computation. | CONNECTION: The undecidability proof constructs a Hamiltonian wh Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Sep 15, 2026•0 citations

Instability of the undecidable behavior of the spectral gap in 1D

Laura Castilla-Castellano, Angelo Lucia

The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] or more dimensions [T. S. Cubitt et al., "Undecidability of the spectral gap", Nature 528 (2015) and Forum of Mathematics Pi, 10 (2022)]. In this work, we focus on the 1-dimensional result, showing that the constructed family with undecidable behavior is extremely sensitive to perturbations. In particular, for any $\varepsilon > 0$, there exists a 1-local, rank 1, perturbation with norm $O(\varepsilon)$, such that the spectral gap problem for the family in [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] now becomes decidable.

quant-pharXiv:2607.08686•Jul 10, 2026•0 citations

The Undecidability of the Spectral Gap: An Expository Account of a Fundamental Limitation in Quantum Many-Body Physics

Doug Doucette

This paper provides a self-contained conceptual overview of one of the most striking results in contemporary quantum many-body physics: the undecidability of the spectral gap problem. The spectral gap—the energy difference between a system's ground state and its first excited state—is a fundamental property that distinguishes insulating from conducting behavior and marks quantum phase transitions. In 2015, Cubitt, Pérez-García, and Wolf proved that deciding whether a translationally invariant quantum spin system with finite-range interactions is gapped or gapless is algorithmically undecidable. This result was extended to one-dimensional systems by Bausch and colleagues in 2020, overturning the intuition that lower-dimensional systems are inherently more tractable. The proof architecture rests on two main ingredients: aperiodic tilings and history-state constructions. Aperiodic tilings encode undecidable combinatorial properties into the spatial structure of the Hamiltonian, while history states embed the evolution of a Turing machine into the ground state. By combining these elements, the authors construct explicit Hamiltonians whose spectral gap depends directly on whether a simulated Turing machine halts—a problem known to be undecidable. Thus, no algorithm can classify every instance correctly. The paper also distinguishes two forms of undecidability: algorithmic undecidability, which asserts that no Turing machine can solve the problem for all instances, and axiomatic independence, which shows that for some Hamiltonians, the gap status is not determined by the standard axioms of mathematics. These results impose fundamental limits on numerical simulation and phase classification, but they do not render all systems intractable. They demarcate a boundary between decidable and undecidable behavior, revealing deep connections between physics, computation, and logic.

•Aug 6, 2026•0 citations

Comment on "On the uncomputability of the spectral gap"

Toby S. Cubitt, David Pérez-Garcı́a, Michael M. Wolf

The aim of this short note is to clarify some of the claims made in the comparison made in [S. Lloyd, On the uncomputability of the spectral gap, arXiv:1602.05924] between our recent result [T.S. Cubitt, D. Perez-Garcia, M.M. Wolf, Undecidability of the spectral gap, Nature 528, 207-211 (2015), arXiv:1502.04573] and his 1994 paper [S. Lloyd, Necessary and sufficient conditions for quantum computation, J. Mod. Opt. 41(12), 2503-2520 (1994)].

arXiv:1603.00825•Mar 2, 2016•3 citations

Undecidability as Structural Physics: From Halting to Spectral Gaps — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability is not a computational artifact but a structural feature of formal systems, now extending into quantum many-body physics — where the halting problem maps onto spectral gap questions. | MATH: Halting problem (Turing, 1936): no computable function H(P,I) decides if program P halts on input I. Gödel incompleteness: for any consistent, recursively axiomatizable theory T ⊇ Robinson arithmetic, ∃ sentence G with T⊬G and T⊬¬G. Reducibility: A ≤_T B via Turing reduction — solving B solves A. Quantum extension: the spectral gap problem (given a translationally invariant local Hamiltonian, does the gap vanish in the thermodynamic limit?) is undecidable (Cubitt, Perez-Garcia, Wolf, 2015) — proof uses a lattice of spins encoding a Turing machine's halting behavior into the gap's existence. | CONNECTION: The undecidability proofs rely on encoding computation into discrete lattices — the quantum result uses a 2D spin lattice with local interactions, echoing crystallographic l Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 22, 2026•0 citations
We treat the results of the 2015 paper by Cubitt et al. entitled “Undecidability of the Spectral Gap”, and the constructions required to arrive at these results. This paper showed that a specific quantum mechanical problem (the “spectral gap problem”) is algorithmically undecidable, using techniques from computer science. We also treat the theory from quantum mechanics and computer science that is required to understand these results and constructions.
FINDING: Undecidability of the spectral gap in quantum many-body systems (Cubitt et al.) is the dominant mathematical result; other findings are peripheral (hexaquark SU(3) multiplet, graph recoloring, spectral line precision, traffic models, leaf counting). | MATH: The spectral gap problem: given a translationally-invariant Hamiltonian H=∑ihi H = \sum_i h_i H=∑i​hi​ on a 2D lattice (finite local Hilbert space), determining whether the gap Δ=E1−E0 \Delta = E_1 - E_0 Δ=E1​−E0​ (difference between ground state and first excited energy) is zero or positive is undecidable. This maps the halting problem onto the gap via a construction where the gap closes iff a Turing machine halts. Key constants: no specific numeric constants, but the proof uses a lattice of qudits with local dimension d≥2 d \geq 2 d≥2 (often d=2 d=2 d=2 suffices for the 2D case), and relies on the existence of a "gadget" Hamiltonian whose spectrum encodes the machine's computation. | CONNECTION: The undecidability proof constructs a Hamiltonian wh Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] or more dimensions [T. S. Cubitt et al., "Undecidability of the spectral gap", Nature 528 (2015) and Forum of Mathematics Pi, 10 (2022)]. In this work, we focus on the 1-dimensional result, showing that the constructed family with undecidable behavior is extremely sensitive to perturbations. In particular, for any ε>0\varepsilon > 0ε>0, there exists a 1-local, rank 1, perturbation with norm O(ε)O(\varepsilon)O(ε), such that the spectral gap problem for the family in [J. Bausch et al., "Undecidability of the spectral gap in one dimension", Physical Review X 10 (2020)] now becomes decidable.
This paper provides a self-contained conceptual overview of one of the most striking results in contemporary quantum many-body physics: the undecidability of the spectral gap problem. The spectral gap—the energy difference between a system's ground state and its first excited state—is a fundamental property that distinguishes insulating from conducting behavior and marks quantum phase transitions. In 2015, Cubitt, Pérez-García, and Wolf proved that deciding whether a translationally invariant quantum spin system with finite-range interactions is gapped or gapless is algorithmically undecidable. This result was extended to one-dimensional systems by Bausch and colleagues in 2020, overturning the intuition that lower-dimensional systems are inherently more tractable. The proof architecture rests on two main ingredients: aperiodic tilings and history-state constructions. Aperiodic tilings encode undecidable combinatorial properties into the spatial structure of the Hamiltonian, while history states embed the evolution of a Turing machine into the ground state. By combining these elements, the authors construct explicit Hamiltonians whose spectral gap depends directly on whether a simulated Turing machine halts—a problem known to be undecidable. Thus, no algorithm can classify every instance correctly. The paper also distinguishes two forms of undecidability: algorithmic undecidability, which asserts that no Turing machine can solve the problem for all instances, and axiomatic independence, which shows that for some Hamiltonians, the gap status is not determined by the standard axioms of mathematics. These results impose fundamental limits on numerical simulation and phase classification, but they do not render all systems intractable. They demarcate a boundary between decidable and undecidable behavior, revealing deep connections between physics, computation, and logic.
FINDING: Undecidability is not a computational artifact but a structural feature of formal systems, now extending into quantum many-body physics — where the halting problem maps onto spectral gap questions. | MATH: Halting problem (Turing, 1936): no computable function H(P,I) decides if program P halts on input I. Gödel incompleteness: for any consistent, recursively axiomatizable theory T ⊇ Robinson arithmetic, ∃ sentence G with T⊬G and T⊬¬G. Reducibility: A ≤_T B via Turing reduction — solving B solves A. Quantum extension: the spectral gap problem (given a translationally invariant local Hamiltonian, does the gap vanish in the thermodynamic limit?) is undecidable (Cubitt, Perez-Garcia, Wolf, 2015) — proof uses a lattice of spins encoding a Turing machine's halting behavior into the gap's existence. | CONNECTION: The undecidability proofs rely on encoding computation into discrete lattices — the quantum result uses a 2D spin lattice with local interactions, echoing crystallographic l Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com