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:1910.01631 · Nature Communications

Uncomputability of phase diagrams

Johannes Bausch, Toby S. Cubitt, James D. Watson

Published Jan 19, 2021• 34 citations
arXivHTMLPDF

Abstract

The phase diagram of a material is of central importance in describing the properties and behaviour of a condensed matter system. In this work, we prove that the task of determining the phase diagram of a many-body Hamiltonian is in general uncomputable, by explicitly constructing a continuous one-parameter family of Hamiltonians H(φ), where [Formula: see text], for which this is the case. The H(φ) are translationally-invariant, with nearest-neighbour couplings on a 2D spin lattice. As well as implying uncomputablity of phase diagrams, our result also proves that undecidability can hold for a set of positive measure of a Hamiltonian's parameter space, whereas previous results only implied undecidability on a zero measure set. This brings the spectral gap undecidability results a step closer to standard condensed matter problems, where one typically studies phase diagrams of many-body models as a function of one or more continuously varying real parameters, such as magnetic field strength or pressure.

DOI
10.1038/s41467-020-20504-6

Related papers

Chaitin Phase Transition

James Purcell, Zhi Li, Toby S. Cubitt

We construct a family of Hamiltonians whose phase diagram is guaranteed to have a single phase transition, yet the location of this phase transition is uncomputable. The Hamiltonians $H(ϕ)$ describe qudits on a two-dimensional square lattice with translationally invariant, nearest-neighbour interactions tuned by a continuous parameter $ϕ\in(0,1]$. For all $ϕ\in(0,1]$, $H(ϕ)$ is in one of two phases, one a gapless phase, the other a gapped phase. The phase transition occurs when $ϕ$ equals the Chaitin's constant $Ω$, a well-defined real number that encodes the Halting problem, and hence is uncomputable for Turing machines and undecidable for any consistent recursive axiomatization of mathematics. Our result implies that no general algorithm exists to determine the phase diagrams even under the promise that the phase diagram is exceedingly simple, and illustrates how uncomputable numbers may manifest in physical systems.

arXiv:2410.02600•Oct 3, 2024•6 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•21 citations

Undecidability of the Spectral Gap Problem via Halting Problem Encoding — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Undecidability in the spectral gap problem for quantum many-body systems proves that determining whether a system is gapped or gapless is algorithmically impossible in general. | MATH: The spectral gap problem is mapped to the halting problem via translationally invariant Hamiltonians on a 2D lattice; the set of gapped Hamiltonians is Π₂-complete in the arithmetic hierarchy. Key constants: no specific numerical constants emerge, but the proof relies on encoding Turing machine states into local Hamiltonian terms. | CONNECTION: No direct geometric harmony ratios (0.382, 0.618, etc.) appear. However, the lattice structure (2D square lattice) and translational invariance connect to crystallographic symmetry groups (p4m wallpaper group). The undecidability result implies that spectral gaps—which determine whether a system is an insulator (gapped) or conductor (gapless)—cannot be universally predicted, breaking the dream of a complete mathematical description of matter. | DEPTH: 9/1 Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 20, 2026•0 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

Uncomputably complex renormalisation group flows

James D. Watson, Emilio Onorati, Toby S. Cubitt

Renormalisation group methods are among the most important techniques for analysing the physics of many-body systems: by iterating a renormalisation group map, which coarse-grains the description of a system and generates a flow in the parameter space, physical properties of interest can be extracted. However, recent work has shown that important physical features, such as the spectral gap and phase diagram, may be impossible to determine, even in principle. Following these insights, we construct a rigorous renormalisation group map for the original undecidable many-body system that appeared in the literature, which reveals a renormalisation group flow so complex that it cannot be predicted. We prove that each step of this map is computable, and that it converges to the correct fixed points, yet the resulting flow is uncomputable. This extreme form of unpredictability for renormalisation group flows had not been shown before and goes beyond the chaotic behaviour seen previously.

arXiv:2102.05145•Nature Communications•Dec 9, 2022•14 citations

Spectral Gap of Quantum Many-Body Hamiltonians Is Undecidable — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The spectral gap of a quantum many-body Hamiltonian is undecidable — no algorithm can determine whether a given local Hamiltonian has a gap or is gapless. | MATH: Cubitt–Perez-Garcia–Wolf (Nature 528, 207–211, 2015): constructs a family of frustration-free, translation-invariant, nearest-neighbor Hamiltonians H(φ) on a 2D lattice such that the spectral gap Δ(H(φ)) encodes the halting problem. Formally: the ground-state energy density and gap are non-computable; the "gap function" Δ: ℕ→ℝ is not Turing-computable. The construction reduces from Wang tilings / aperiodic tilings (Berger's theorem) to a quantum Hamiltonian whose ground state is a tiling configuration. | CONNECTION: The construction relies on aperiodic tilings (Wang tiles) which are governed by local matching rules — a discrete analog of crystallographic symmetry breaking. The undecidability arises from the absence of a periodic ground state, i.e., the breakdown of translational symmetry at the quantum level. No dire Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 27, 2026•0 citations
The phase diagram of a material is of central importance in describing the properties and behaviour of a condensed matter system. In this work, we prove that the task of determining the phase diagram of a many-body Hamiltonian is in general uncomputable, by explicitly constructing a continuous one-parameter family of Hamiltonians H(φ), where [Formula: see text], for which this is the case. The H(φ) are translationally-invariant, with nearest-neighbour couplings on a 2D spin lattice. As well as implying uncomputablity of phase diagrams, our result also proves that undecidability can hold for a set of positive measure of a Hamiltonian's parameter space, whereas previous results only implied undecidability on a zero measure set. This brings the spectral gap undecidability results a step closer to standard condensed matter problems, where one typically studies phase diagrams of many-body models as a function of one or more continuously varying real parameters, such as magnetic field strength or pressure.
We construct a family of Hamiltonians whose phase diagram is guaranteed to have a single phase transition, yet the location of this phase transition is uncomputable. The Hamiltonians H(ϕ)H(ϕ)H(ϕ) describe qudits on a two-dimensional square lattice with translationally invariant, nearest-neighbour interactions tuned by a continuous parameter ϕ∈(0,1]ϕ\in(0,1]ϕ∈(0,1]. For all ϕ∈(0,1]ϕ\in(0,1]ϕ∈(0,1], H(ϕ)H(ϕ)H(ϕ) is in one of two phases, one a gapless phase, the other a gapped phase. The phase transition occurs when ϕϕϕ equals the Chaitin's constant ΩΩΩ, a well-defined real number that encodes the Halting problem, and hence is uncomputable for Turing machines and undecidable for any consistent recursive axiomatization of mathematics. Our result implies that no general algorithm exists to determine the phase diagrams even under the promise that the phase diagram is exceedingly simple, and illustrates how uncomputable numbers may manifest in physical systems.
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: Undecidability in the spectral gap problem for quantum many-body systems proves that determining whether a system is gapped or gapless is algorithmically impossible in general. | MATH: The spectral gap problem is mapped to the halting problem via translationally invariant Hamiltonians on a 2D lattice; the set of gapped Hamiltonians is Π₂-complete in the arithmetic hierarchy. Key constants: no specific numerical constants emerge, but the proof relies on encoding Turing machine states into local Hamiltonian terms. | CONNECTION: No direct geometric harmony ratios (0.382, 0.618, etc.) appear. However, the lattice structure (2D square lattice) and translational invariance connect to crystallographic symmetry groups (p4m wallpaper group). The undecidability result implies that spectral gaps—which determine whether a system is an insulator (gapped) or conductor (gapless)—cannot be universally predicted, breaking the dream of a complete mathematical description of matter. | DEPTH: 9/1 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
Renormalisation group methods are among the most important techniques for analysing the physics of many-body systems: by iterating a renormalisation group map, which coarse-grains the description of a system and generates a flow in the parameter space, physical properties of interest can be extracted. However, recent work has shown that important physical features, such as the spectral gap and phase diagram, may be impossible to determine, even in principle. Following these insights, we construct a rigorous renormalisation group map for the original undecidable many-body system that appeared in the literature, which reveals a renormalisation group flow so complex that it cannot be predicted. We prove that each step of this map is computable, and that it converges to the correct fixed points, yet the resulting flow is uncomputable. This extreme form of unpredictability for renormalisation group flows had not been shown before and goes beyond the chaotic behaviour seen previously.
FINDING: The spectral gap of a quantum many-body Hamiltonian is undecidable — no algorithm can determine whether a given local Hamiltonian has a gap or is gapless. | MATH: Cubitt–Perez-Garcia–Wolf (Nature 528, 207–211, 2015): constructs a family of frustration-free, translation-invariant, nearest-neighbor Hamiltonians H(φ) on a 2D lattice such that the spectral gap Δ(H(φ)) encodes the halting problem. Formally: the ground-state energy density and gap are non-computable; the "gap function" Δ: ℕ→ℝ is not Turing-computable. The construction reduces from Wang tilings / aperiodic tilings (Berger's theorem) to a quantum Hamiltonian whose ground state is a tiling configuration. | CONNECTION: The construction relies on aperiodic tilings (Wang tiles) which are governed by local matching rules — a discrete analog of crystallographic symmetry breaking. The undecidability arises from the absence of a periodic ground state, i.e., the breakdown of translational symmetry at the quantum level. No dire Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com