Quantum dynamics

Non-deterministic Turing machine

Probabilistic Turing machine

Open quantum system

Quantum Turing machine

Turing machine

Computer science

Computation

Quantum computer

Quantum algorithm

Quantum network

Quantum mechanics

Description number

Algorithm

Theoretical computer science

Quantum process

Quantum

Universal Turing machine

Physics

Super-recursive algorithm

Proceedings of the Royal Society of London A Mathematical and Physical Sciences

It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic ...

Quantum theory, the Church–Turing principle and the universal quantum computer