Source-linked AI summary
The physical Church-Turing thesis and the principles of quantum theory
Pablo Arrighi, Gilles Dowek
TL;DR
Quantum theory permits evolutions that could violate the physical Church-Turing thesis, raising the question of which physically motivated constraints can rule this out. The paper proves a quantum version of Gandy’s theorem, showing that quantum-system evolution is computable under its stated hypotheses.
Problem
The paper asks whether physically motivated constraints can reconcile quantum theory’s infinite-dimensional unitary evolutions with the physical Church-Turing thesis, given that unrestricted evolutions may violate it.
Source: §1 · pp. 1–2Method
The authors extend Gandy’s approach by proving a quantum theorem under assumptions including homogeneity, bounded density and information-propagation velocity, quiescence, and unitarity.
Source: §7 · p. 12Results
Under homogeneity of Euclidean space and time, bounded spatial density and information-propagation velocity, quiescence, and unitarity, quantum-system evolution is computable.
Source: §7 · p. 12Takeaways & Limitations
The authors present the result as a step toward a computable quantum theory and report that examples show dropping any one of the hypotheses suffices to break the result.
Source: §7 · p. 12Each hypothesis of the quantum theorem is necessary for it to hold.
Source: §6 · p. 11
Abstract
from arXiv · showhide
Notoriously, quantum computation shatters complexity theory, but is innocuous to computability theory. Yet several works have shown how quantum theory as it stands could breach the physical Church-Turing thesis. We draw a clear line as to when this is the case, in a way that is inspired by Gandy. Gandy formulates postulates about physics, such as homogeneity of space and time, bounded density and velocity of information --- and proves that the physical Church-Turing thesis is a consequence of these postulates. We provide a quantum version of the theorem. Thus this approach exhibits a formal non-trivial interplay between theoretical physics symmetries and computability assumptions.
1 Introduction
The physical Church-Turing thesis says every function computed by a physical system is Turing-computable, making it a strong claim about the limits of physics and computation. The paper takes up the search for physically motivated limits on quantum theory, transposing Gandy’s approach to connect physical hypotheses with computability.
1 Introduction
- The physical Church-Turing thesis holds that every function computed by a physical system can be computed by a Turing machine, excluding non-computable functions such as the halting function.The passage presents this as a strong statement of belief about the limits of both physics and computation.Source: §1 · p. 1
- Quantum computers may outperform classical computers, but Deutsch notes they remain classically simulable; unrestricted quantum theory nevertheless permits evolutions that could violate the physical Church-Turing thesis [26] [21].Nielsen’s proposed unitary uses the halting function to provide a counterexample [26].Source: §1 · pp. 1–2
- Because physically motivated quantum evolutions can involve infinite-dimensional unitary operators, the paper pursues natural, non-ad-hoc limits that retain physical reasons while making quantum theory computable [26].The introduction frames this as a response to the gap between quantum Turing machines and full-blown quantum theory.Source: §1 · p. 2
- Gandy motivates the approach: physical hypotheses, particularly bounded information velocity and finite information density, can underpin computability and can be transposed to quantum theory.Gandy’s proof relies on physical hypotheses rather than an axiomatic notion of algorithm.Source: §1 · p. 2
2 Gandy’s theorem for classical physics
Gandy’s theorem shows that, from a given initial global state, the system’s global state at each time kT is computable under assumptions of spatial and temporal homogeneity, bounded information density and propagation speed, and quiescence. The proof represents the dynamics as a computable finite local rule.
2 Gandy’s theorem for classical physics
- The hypotheses require spatial and temporal homogeneity, finite state spaces for finite regions, bounded propagation speed, and quiescence preserved outside a finite region.Quiescence and bounded propagation together ensure that a quiescent neighborhood remains quiescent after one time step.Source: §2 · pp. 2–3
- Under Gandy’s hypotheses, the global state at time kT is a computable function of k and the initial global state.The proof establishes computability by reconstructing the global evolution from a finite local rule.Source: §2 · pp. 3–4
- The proof partitions space into cells with a common finite state set and represents global states as configurations that are quiescent almost everywhere.Bounded information density makes each cell’s state set finite; quiescence ensures only finitely many cells are non-quiescent.Source: §2 · p. 4
- Homogeneity and bounded propagation yield a time-independent local update rule whose output depends only on a finite neighborhood and not on the cell’s location.The finite rule is computable and reconstructs the global evolution.Source: §2 · p. 4
3 Necessity
Each hypothesis of Proposition 1 is necessary: dropping any one while retaining the other four permits a dynamics or configuration that computes an undecidable set U. The counterexamples show how spatial or temporal irregularities, unbounded information density or propagation speed, or non-quiescent input can encode U.
Spatial homogeneity
- Without spatial homogeneity, irregular cell states or local rules can encode U, allowing a single update to reveal whether each index belongs to U.The construction applies a NOT operation at cell i exactly when U(i) = 1, or uses cell-specific state spaces {q, 2i, 2i + 1}.Source: §3 · p. 5
Temporal homogeneity
- Without time homogeneity, time-dependent dynamics can encode U by applying NOT after i time steps exactly when U(i) = 1.The example is G(t + iT)(a)(C) = Not_U(i)(a(C)).Source: §3 · p. 5
Bounded density of information
- Without bounded information density, a cell with state space N could apply the noncomputable function f_U to its state.The paper defines f_U as a one-to-one function mapping the nth element of U to 2n and the nth element of its complement to 2n + 1.Source: §3 · p. 5
Bounded velocity of propagation
- Without bounded propagation velocity, dynamics could transform a segment qx1^iq into qNot_U(i)(x)1^iq, encoding U in the output.Here x is 0 or 1, so the transformed segment reveals whether U(i) = 1.Source: §3 · p. 5
Quiescence
- Without quiescence, an uncomputable initial configuration could yield an uncomputable output even under trivial dynamics, so this hypothesis states that the input configuration is computable.The paper identifies this as a way to ensure the input is computable.Source: §3 · p. 5
4 Hypotheses in the quantum case
The section reformulates Gandy’s finite-density and finite-propagation hypotheses for quantum systems, distinguishing their potentially infinite state descriptions from finite, accessible information. It also specifies assumptions on state-space dimension and scalars, causality, quiescence, homogeneity, and unitarity.
4 Hypotheses in the quantum case
- Quantum states can have infinitely many descriptions, yet accessible information remains constrained: EPR correlations transmit no information faster than light, and a qubit stores at most one accessible bit.This distinction motivates quantum versions of Gandy’s finite-density and finite-velocity assumptions.Source: §4 · p. 6
4.1 Bounded density of information
- Each finite cell must have a finite-dimensional state space over a finite extension of the rationals, allowing finitely many measurement outcomes while excluding non-computable scalars.The restriction retains scalars generated by a universal gate set [12] and is described as having few consequences in discrete space and time; continuous theories may be affected [14] [11].Source: §4.1 · p. 6
4.2 Bounded velocity of propagation of information
- Quantum bounded propagation is formalized by causality: after a fixed time T, a region’s density matrix depends only on its radius-1 neighborhood.This axiomatic condition is equivalent to localizability—implementation by local gates in a finite-depth, infinite-width circuit—though localizability is a stronger supposition [3]. The formulation builds on a C∗-algebra approach [28] rooted in quantum field theory; subsystem density matrices alone do not reconstruct a compound state.Source: §4.2 · p. 7
4.3 Quiescence
- Quiescent states must be pure so a region is quiescent exactly when both parts of any partition are quiescent.The remaining quiescence hypothesis is unchanged from the classical case.Source: §4.3 · p. 7
4.4 Overall –
- The overall quantum assumptions retain space-time homogeneity and unitarity while giving density, propagation, and quiescence quantum-specific formulations.The density condition requires finite-dimensional state spaces over a finite extension of the rationals; propagation is expressed through local dependence of density matrices, and quiescent regions use canonical pure states.Source: §4.1 · p. 6, §4.4 · pp. 7–8, §4.2 · p. 7
5 A quantum version of Gandy’s theorem
Under the setting and hypotheses of Section 4, the global state at time kT is computable from k relative to an indexing of the state space.
5 A quantum version of Gandy’s theorem
- Every local linear map on H is computable.A local map acts on a fixed finite block of cells and leaves the remaining configuration unchanged.Source: §5 · p. 9
- Under Section 4’s setting and hypotheses, the global state at time kT is computable from k relative to an indexing of the state space.The theorem assumes a given initial global state.Source: §5 · p. 9
- Finite density and spatial homogeneity give each cell the same finite-dimensional state space, while quiescence ensures only finitely many cells are non-quiescent.These conditions let the global state be represented in H, the vector space of formal linear combinations of configurations.Source: §5 · p. 10
- Causality and unitarity allow the evolution to be decomposed using the Arrighi-Nesme-Werner theorem [3, 4] into fixed local K and Swap operations, which are computable.Spatial homogeneity makes the local K operation the same at each translated cell.Source: §5 · pp. 9–10
- The computation finds the finite region around non-quiescent cells, applies K and Swap there, and thereby computes the state after each time step.The passage gives this algorithm as the basis for computability of the function mapping k to G^k|ψ0⟩.Source: §5 · pp. 10–11
6 Necessity.
The section argues that every hypothesis of Theorem 2 is necessary, while identifying limits and caveats in the quantum case. Classical counterexamples transfer to quantum settings, but the quantum hypotheses raise additional issues about scalar computability and unitarity.
Necessity
- Classical counterexamples also apply in the quantum setting, supporting the necessity of the remaining classical-case hypotheses within the quantum hypotheses.The section notes that differences remain for bounded density of information and unitarity.Source: §6 · p. 11
- Finite-dimensional cell state spaces are necessary, but the counterexample does not establish that scalars must be finite extensions of the rationals; scalars should remain computable complex numbers.Using an uncomputable complex amplitude in a unitary transformation would let repeated measurements approximate it, beyond deterministic or probabilistic Turing machines [26].Source: §6 · p. 11
- Allowing quantum operations would invalidate Proposition 2: their stochastic classical evolutions can encode an undecidable set in correlations and enable its probabilistic computation.The counterexample satisfies bounded velocity of information, raising concern that this condition is too weak for quantum operations without a unitarity-plus-causality-implies-localizability theorem; strengthening causality is difficult [3], [6] [18] [29], [22].Source: §6 · pp. 11–12
7 Conclusion
The paper proves a quantum version of Gandy’s theorem: under physically motivated assumptions including homogeneity, bounded density, bounded propagation velocity, quiescence, and unitarity, quantum-system evolution is computable. It identifies these assumptions as a line between settings that preserve or may breach the physical Church-Turing thesis.
Summary
- Under homogeneity of Euclidean space and time, bounded spatial density and information-propagation velocity, quiescence, and unitarity, quantum-system evolution is computable.This is the paper’s quantum version of Gandy’s theorem, alongside the classical version [20, 15, 30].Source: §7 · p. 12
- Local linear operators are computable under stable vector-space computability [2], while entangled systems require the result that unitarity plus causality implies localizability [3].The paper’s Proposition 1 establishes the local-operator result; together, these ingredients support the computability theorem.Source: §7 · p. 12
Future work
- Examples show that dropping one of the hypotheses can suffice for quantum evolution to breach the physical Church-Turing thesis, distinguishing the positive result from negative results [26] [21].Further work could study reasonable measurement or extend the analysis to continuous time.Source: §7 · p. 12
- The role of bounded information density remains an open physical question, including whether dividing space into pieces under that condition conflicts with isotropy.The authors ask whether bounded density is compatible with modern physics.Source: §7 · p. 13
Bigger picture
- The physical Church-Turing thesis depends on the underlying physical theory; in General Relativity, certain space-times have been proposed to permit hypercomputation [19].More broadly, establishing formal relations among hypotheses can rule out scenarios that are inconsistent with those relations, even when some hypotheses cannot be refuted.Source: §7 · p. 13