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

arXiv:2607.08686

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

Laura Castilla-Castellano, Angelo Lucia

quant-phSubmitted Jul 9, 2026• Announced Jul 10, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
18 pages, 2 figures

Related papers

Undecidability of the spectral gap in rotationally symmetric Hamiltonians

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 [] or more dimensions []. In these works, families of nearest-neighbor interactions are constructed whose spectral gap depends on the outcome of a Turing machine halting problem, therefore making it impossible for an algorithm to predict its existence. While these models are translationally invariant, they are not invariant under the other symmetries of the lattice, a property which is commonly found in physically relevant cases. This poses the question of whether the spectral gap problem could be decidable for Hamiltonians with stronger symmetry constraints. We give a negative answer to this question, in the case of models with four-body (plaquette) interactions on the square lattice satisfying rotation, but not reflection, symmetry: rotational symmetry is not enough to make the problem decidable.

arXiv:2410.13589•Physical Review Research•Dec 4, 2025•1 citation

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 of the Spectral Gap in One Dimension

Johannes Bausch, Toby S. Cubitt, Angelo Lucia +1 more

A new analysis proves that it is not possible for numerical algorithms to determine if a 1D quantum system has a spectral gap, showing that basic properties of even simple systems are, in some instances, impossible to predict.

arXiv:1810.01858•Physical Review X•Aug 17, 2020•37 citations

Undecidability of the Spectral Gap

J.B. Houben

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.

•Jan 1, 2016•0 citations

Undecidability of the Spectral Gap

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

Abstract 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. Moreover, this constant can be taken equal to the operator norm of the local operator that generates the Hamiltonian (the local interaction strength). The result still holds true if one restricts to arbitrarily small quantum perturbations of classical Hamiltonians. The proof combines a robustness analysis of Robinson’s aperiodic tiling, together with tools from quantum information theory: the quantum phase estimation algorithm and the history state technique mapping Quantum Turing Machines to Hamiltonians.

arXiv:1502.04573•Forum of Mathematics Pi•Jan 1, 2022•14 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
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.
The problem of determining the existence of a spectral gap in a lattice quantum spin system was previously shown to be undecidable for one [] or more dimensions []. In these works, families of nearest-neighbor interactions are constructed whose spectral gap depends on the outcome of a Turing machine halting problem, therefore making it impossible for an algorithm to predict its existence. While these models are translationally invariant, they are not invariant under the other symmetries of the lattice, a property which is commonly found in physically relevant cases. This poses the question of whether the spectral gap problem could be decidable for Hamiltonians with stronger symmetry constraints. We give a negative answer to this question, in the case of models with four-body (plaquette) interactions on the square lattice satisfying rotation, but not reflection, symmetry: rotational symmetry is not enough to make the problem 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.
Abstract 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. Moreover, this constant can be taken equal to the operator norm of the local operator that generates the Hamiltonian (the local interaction strength). The result still holds true if one restricts to arbitrarily small quantum perturbations of classical Hamiltonians. The proof combines a robustness analysis of Robinson’s aperiodic tiling, together with tools from quantum information theory: the quantum phase estimation algorithm and the history state technique mapping Quantum Turing Machines to Hamiltonians.
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