Chaitin Phase Transition
Preprint
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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Undecidability of the Spectral Gap in One DimensionPhysical Review X, 2020
- Spectral gaps of frustration-free spin systems with boundaryJournal of Mathematical Physics, 2019
- Local gap threshold for frustration-free spin systemsJournal of Mathematical Physics, 2016
- Gapped and gapless phases of frustration-free spin-12 chainsJournal of Mathematical Physics, 2015
- Anyons in an exactly solved model and beyondAnnals of Physics, 2006
- Fault-tolerant quantum computation by anyonsAnnals of Physics, 2003
- Quantum algorithms revisitedProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1998
- Energy gaps and elementary excitations for certain VBS-quantum antiferromagnetsJournal of Statistical Physics, 1988
- Rigorous results on valence-bond ground states in antiferromagnetsPhysical Review Letters, 1987
- Zur Theorie des FerromagnetismusThe European Physical Journal A, 1928