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

Bulletin of the European Association for Theoretical Computer Science

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

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

Published Jun 1, 2017• 2 citations
OpenAlex

Abstract

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.

Related papers

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

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

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

Andrew Stewart Caldin

FINDING: Undecidability is not a computational artifact but a structural feature of formal systems — it propagates into physics (quantum many-body problems, spectral gaps) via reduction, revealing a hierarchy of unknowability. | MATH: Halting problem (Turing, 1936): no computable function H(p,i) decides if program p halts on input i. Gödel's incompleteness: for any consistent formal system F containing arithmetic, ∃ statement G_F such that F⊬G_F and F⊬¬G_F. Reduction: Problem A ≤_T Problem B means an oracle for B solves A; undecidability transfers A ≤ B ⇒ B undecidable. Quantum analog: spectral gap problem (Cubitt, Perez-Garcia, Wolf, 2015) — determining if a 2D spin-lattice Hamiltonian has a gap above ground state is undecidable (reduction from halting problem to Hamiltonian construction). | CONNECTION: The reduction lattice forms a partial order with a maximal undecidable class (Σ₁⁰-complete) — structurally analogous to root system hierarchies (e.g., E₈ has 240 roots; the undecidabil Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 21, 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

Spectral Gap Problem Undecidable: Turing Limits in Quantum Many-Body Physics — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The spectral gap problem is undecidable in general — no algorithm can determine whether a quantum many-body Hamiltonian has a spectral gap or is gapless, establishing a Gödel/Turing-style limit inside physics itself. | MATH: Given a translation-invariant, nearest-neighbour Hamiltonian H on a 2D spin lattice, the ground-state energy density and the question "is Δ = E₁ − E₀ > 0?" are undecidable (Cubitt, Pérez-García, Wolf, Nature 2015). The construction encodes a universal Turing machine into the low-energy spectrum; the spectral gap's presence/absence maps to halting/non-halting. | CONNECTION: No direct golden-ratio or crystallographic constant appears in the undecidability result itself. The relevant symmetry structure is the 2D lattice translation group ℤ² and the local SU(2)/finite-group gauge structure of the spin Hamiltonian — a lattice/crystallographic setting, but the undecidability is a logical (computability) property, not a geometric-harmony ratio. | DEPTH: 9 FINDIN Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 28, 2026•0 citations

Quantum Spectral Gap Provably Undecidable, Linking Physics to Halting Problem — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The spectral gap problem — determining whether a quantum Hamiltonian's energy spectrum has a gap above the ground state — is provably undecidable in general, linking quantum many-body physics to the halting problem and Gödelian limits. | MATH: The key construction (Cubitt, Perez-Garcia, Wolf, 2015) reduces the halting problem to a family of 2D spin-lattice Hamiltonians \( H(n) \) on a fixed lattice, where the spectral gap (difference between ground state energy \( E_0 \) and first excited state \( E_1 \)) is either \( \Delta > 0 \) (gapped) or \( \Delta = 0 \) (gapless), depending on whether a Turing machine halts. The Hamiltonian is built from translationally invariant local terms with frustration-free ground states; the gap closes as \( \Delta \sim 1/\text{poly}(n) \) in the gapless case. No closed-form equation for \( \Delta \) exists — it is algorithmically uncomputable. | CONNECTION: The construction uses a lattice structure (square lattice, 2D) with local interaction ter Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 26, 2026•0 citations
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.
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
FINDING: Undecidability is not a computational artifact but a structural feature of formal systems — it propagates into physics (quantum many-body problems, spectral gaps) via reduction, revealing a hierarchy of unknowability. | MATH: Halting problem (Turing, 1936): no computable function H(p,i) decides if program p halts on input i. Gödel's incompleteness: for any consistent formal system F containing arithmetic, ∃ statement G_F such that F⊬G_F and F⊬¬G_F. Reduction: Problem A ≤_T Problem B means an oracle for B solves A; undecidability transfers A ≤ B ⇒ B undecidable. Quantum analog: spectral gap problem (Cubitt, Perez-Garcia, Wolf, 2015) — determining if a 2D spin-lattice Hamiltonian has a gap above ground state is undecidable (reduction from halting problem to Hamiltonian construction). | CONNECTION: The reduction lattice forms a partial order with a maximal undecidable class (Σ₁⁰-complete) — structurally analogous to root system hierarchies (e.g., E₈ has 240 roots; the undecidabil Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: The spectral gap problem is undecidable in general — no algorithm can determine whether a quantum many-body Hamiltonian has a spectral gap or is gapless, establishing a Gödel/Turing-style limit inside physics itself. | MATH: Given a translation-invariant, nearest-neighbour Hamiltonian H on a 2D spin lattice, the ground-state energy density and the question "is Δ = E₁ − E₀ > 0?" are undecidable (Cubitt, Pérez-García, Wolf, Nature 2015). The construction encodes a universal Turing machine into the low-energy spectrum; the spectral gap's presence/absence maps to halting/non-halting. | CONNECTION: No direct golden-ratio or crystallographic constant appears in the undecidability result itself. The relevant symmetry structure is the 2D lattice translation group ℤ² and the local SU(2)/finite-group gauge structure of the spin Hamiltonian — a lattice/crystallographic setting, but the undecidability is a logical (computability) property, not a geometric-harmony ratio. | DEPTH: 9 FINDIN Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: The spectral gap problem — determining whether a quantum Hamiltonian's energy spectrum has a gap above the ground state — is provably undecidable in general, linking quantum many-body physics to the halting problem and Gödelian limits. | MATH: The key construction (Cubitt, Perez-Garcia, Wolf, 2015) reduces the halting problem to a family of 2D spin-lattice Hamiltonians H(n) H(n) H(n) on a fixed lattice, where the spectral gap (difference between ground state energy E0 E_0 E0​ and first excited state E1 E_1 E1​) is either Δ>0 \Delta > 0 Δ>0 (gapped) or Δ=0 \Delta = 0 Δ=0 (gapless), depending on whether a Turing machine halts. The Hamiltonian is built from translationally invariant local terms with frustration-free ground states; the gap closes as Δ∼1/poly(n) \Delta \sim 1/\text{poly}(n) Δ∼1/poly(n) in the gapless case. No closed-form equation for Δ \Delta Δ exists — it is algorithmically uncomputable. | CONNECTION: The construction uses a lattice structure (square lattice, 2D) with local interaction ter Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com