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:2410.02600

Chaitin Phase Transition

James Purcell, Zhi Li, Toby S. Cubitt

Published Oct 3, 2024• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2410.02600

Related papers

Uncomputability of phase diagrams

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

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 φ∈R, 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.

•Mar 10, 2020•18 citations

Uncomputability of phase diagrams

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

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.

arXiv:1910.01631•Nature Communications•Jan 19, 2021•20 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

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 in quantum thermalization

Naoto Shiraishi, Keiji Matsumoto

The investigation of thermalization in isolated quantum many-body systems has a long history, dating back to the time of developing statistical mechanics. Most quantum many-body systems in nature are considered to thermalize, while some never achieve thermal equilibrium. The central problem is to clarify whether a given system thermalizes, which has been addressed previously, but not resolved. Here, we show that this problem is undecidable. The resulting undecidability even applies when the system is restricted to one-dimensional shift-invariant systems with nearest-neighbour interaction, and the initial state is a fixed product state. We construct a family of Hamiltonians encoding dynamics of a reversible universal Turing machine, where the fate of a relaxation process changes considerably depending on whether the Turing machine halts. Our result indicates that there is no general theorem, algorithm, or systematic procedure determining the presence or absence of thermalization in any given Hamiltonian.

arXiv:2012.13889•Nature Communications•Aug 24, 2021•26 citations

The Complexity of Approximating Critical Points of Quantum Phase Transitions

James D. Watson, Johannes Bausch

Phase diagrams chart material properties with respect to one or more external or internal parameters such as pressure or magnetisation; as such, they play a fundamental role in many theoretical and applied fields of science. In this work, we prove that provided the phase of the Hamiltonian at a finite size reflects the phase in the thermodynamic limit, approximating the critical boundary in its phase diagram to constant precision is $P^{QMA_{EXP}}$-complete. This holds even for translationally-invariant nearest neighbour couplings, and even if the system's phase diagram is promised to have a single critical boundary delineating two phases. For the simpler case of a single parameter, the same problem remains $QMA_{EXP}$-hard. Our results extend the study of quantum phases to systems with more realistic phase diagrams than previously studied. Furthermore, our findings place complexity-theoretic constraints on the effectiveness of (computational or analytic) methods based on finite size criteria, similar in spirit to the Knabe bound, for the task of extrapolating the properties (e.g. gapped/gapless) of a system from finite-size observations to the thermodynamic limit.

arXiv:2105.13350•May 27, 2021•5 citations
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: 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 φ∈R, 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.
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.
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.
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 investigation of thermalization in isolated quantum many-body systems has a long history, dating back to the time of developing statistical mechanics. Most quantum many-body systems in nature are considered to thermalize, while some never achieve thermal equilibrium. The central problem is to clarify whether a given system thermalizes, which has been addressed previously, but not resolved. Here, we show that this problem is undecidable. The resulting undecidability even applies when the system is restricted to one-dimensional shift-invariant systems with nearest-neighbour interaction, and the initial state is a fixed product state. We construct a family of Hamiltonians encoding dynamics of a reversible universal Turing machine, where the fate of a relaxation process changes considerably depending on whether the Turing machine halts. Our result indicates that there is no general theorem, algorithm, or systematic procedure determining the presence or absence of thermalization in any given Hamiltonian.
Phase diagrams chart material properties with respect to one or more external or internal parameters such as pressure or magnetisation; as such, they play a fundamental role in many theoretical and applied fields of science. In this work, we prove that provided the phase of the Hamiltonian at a finite size reflects the phase in the thermodynamic limit, approximating the critical boundary in its phase diagram to constant precision is PQMAEXPP^{QMA_{EXP}}PQMAEXP​-complete. This holds even for translationally-invariant nearest neighbour couplings, and even if the system's phase diagram is promised to have a single critical boundary delineating two phases. For the simpler case of a single parameter, the same problem remains QMAEXPQMA_{EXP}QMAEXP​-hard. Our results extend the study of quantum phases to systems with more realistic phase diagrams than previously studied. Furthermore, our findings place complexity-theoretic constraints on the effectiveness of (computational or analytic) methods based on finite size criteria, similar in spirit to the Knabe bound, for the task of extrapolating the properties (e.g. gapped/gapless) of a system from finite-size observations to the thermodynamic limit.