The physical Church-Turing thesis and the principles of quantum theory

Notoriously, quantum computation shatters complexity theory, but is innocuous to computability theory [5]. Yet several works have shown how quantum theory as it stands could breach the physical Church-Turing thesis [10, 11]. We draw a clear line as to when this is the case, in a way that is inspired by Gandy [7]. 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. The Church-Turing thesis. The physical Church-Turing thesis states that any function that can be computed by a physical system can be computed by a Turing Machine. There are many mathematical functions that cannot be computed on a Turing Machine (the halting function h: N → {0, 1} that decides whether the ith Turing Machine halts, the function that decides whether a multivariate polynomial has integer solutions, etc.). Therefore, the physical Church-Turing thesis is a strong statement of belief about the limits of both physics and computation