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

XRDS Crossroads The ACM Magazine for Students

Undecidability of the spectral gap

Johannes Bausch

Published Sep 20, 2016• 49 citations
Publisher

Abstract

What happens to undecidability in the quantum computing paradigm?
DOI
10.1145/2983547

Related papers

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

Doug Doucette

•Aug 6, 2026•0 citations

Undecidability of the Spectral Gap: An Epistemological Look

Emiliano Ippoliti, S. Caprara

Journal for General Philosophy of Science•Mar 1, 2021•3 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

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

Limits and Solvability of Quantum Computing

World scientific series on nonlinear science, series A•Nov 25, 2024•0 citations

Undecidability of the Spectral Gap Proven via Reduction from the Tiling Problem — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability of the spectral gap in quantum many-body systems is proven via reduction from the undecidable tiling problem, linking quantum physics to Turing's halting problem. MATH: Reduction: Halting problem ≤ Turing machine ≤ tiling problem ≤ spectral gap problem. Key constants: none directly; relies on logical undecidability, not numerical constants. CONNECTION: Tiling problem uses Wang tiles, which are directly related to quasicrystalline tilings and Penrose tilings (golden ratio φ = 1.618, 1/φ = 0.618). The undecidability proof for the spectral gap uses a Hamiltonian whose ground state encodes a tiling; the spectral gap is zero iff the tiling is aperiodic. Aperiodic tilings are intimately linked to the golden ratio and fivefold symmetry (crystallographically forbidden). DEPTH: 9 — This result shows that fundamental physical properties (energy gaps) can be logically undecidable, implying limits to what can be computed or known about quantum systems. It bridges comp Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Aug 2, 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.
FINDING: Undecidability of the spectral gap in quantum many-body systems is proven via reduction from the undecidable tiling problem, linking quantum physics to Turing's halting problem. MATH: Reduction: Halting problem ≤ Turing machine ≤ tiling problem ≤ spectral gap problem. Key constants: none directly; relies on logical undecidability, not numerical constants. CONNECTION: Tiling problem uses Wang tiles, which are directly related to quasicrystalline tilings and Penrose tilings (golden ratio φ = 1.618, 1/φ = 0.618). The undecidability proof for the spectral gap uses a Hamiltonian whose ground state encodes a tiling; the spectral gap is zero iff the tiling is aperiodic. Aperiodic tilings are intimately linked to the golden ratio and fivefold symmetry (crystallographically forbidden). DEPTH: 9 — This result shows that fundamental physical properties (energy gaps) can be logically undecidable, implying limits to what can be computed or known about quantum systems. It bridges comp Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com