Undecidability in Physics: a Review
arXiv:2410.16532 · doi:10.1016/j.physrep.2025.06.004
Abstract
The study of undecidability in problems arising from physics has experienced a renewed interest, mainly in connection with quantum information problems. The goal of this review is to survey this recent development. After a historical introduction, we first explain the necessary results about undecidability in mathematics and computer science. Then we briefly review the first results about undecidability in physics which emerged mostly in the 80s and early 90s. Finally we focus on the most recent contributions, which we divide in two main categories: many body systems and quantum information problems.
72 pages, v2
References in corpus (56)
- Experimental loophole-free violation of a Bell inequality using entangled electron spins separated by 1.3 km
- Significant-loophole-free test of Bell's theorem with entangled photons
- Random Numbers Certified by Bell's Theorem
- A strong loophole-free test of local realism
- Matrix Product Density Operators: Simulation of finite-T and dissipative systems
- An Area Law for One Dimensional Quantum Systems
- Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Non-locality and Communication Complexity
- Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
- Undecidability of the Spectral Gap (short version)
- Device independent quantum random number generation
- Solving Gapped Hamiltonians Locally
- Measurement-based quantum computation beyond the one-way model
- Connes' embedding problem and Tsirelson's problem
- Advances in device-independent quantum key distribution
- Tsirelson's problem and Kirchberg's conjecture
- A quantum version of Wielandt's inequality
- Unbounded number of channel uses are required to see quantum capacity
- Matrix product operators and states: NP-hardness and undecidability
- On computational irreducibility and the predictability of complex physical systems
- Coarse-graining of cellular automata, emergence, and the predictability of complex systems
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Quantum measurement occurrence is undecidable
- More Really is Different
- Constructing Turing complete Euler flows in dimension
- Survey on Nonlocal Games and Operator Space Theory
- Fundamental limitations in the purifications of tensor networks
- Computational universes
- Size-Driven Quantum Phase Transitions
- Undecidability of the fate of relaxation in one-dimensional quantum systems
- Undecidability in quantum thermalization
- Encoding Universal Computation in the Ground States of Ising Lattices
- Projected Entangled Pair States: Fundamental analytical and numerical limitations
- Memory effects can make the transmission capability of a communication channel uncomputable
- An invertible map between Bell non-local and contextuality scenarios
- Logical independence and quantum randomness
- Non-signaling deterministic models for non-local correlations have to be uncomputable
- Uncomputability of Phase Diagrams
- Undecidable problems in quantum field theory
- Undecidability in Tensor Network States
- Measurement-based quantum computation and undecidable logic
- Uncomputability and complexity of quantum control
- Quantum logic is undecidable
- Computability and Beltrami fields in Euclidean space
- Undecidability of the Spectral Gap (full version)
- Uncomputably Complex Renormalisation Group Flows
- On the universality of the incompressible Euler equation on compact manifolds, II. Non-rigidity of Euler flows
- Quantum complementarity and logical indeterminacy
- Many bounded versions of undecidable problems are NP-hard
- On the uncomputability of the spectral gap
- A Note on the Second Spectral Gap Incompleteness Theorem
- Incompleteness Ex Machina
- How Real is Incomputability in Physics?
- On the set of reduced states of translation invariant, infinite quantum systems
- Chaitin Phase Transition