It is argued that underlying the Church-Turing hypothesis there is an implicit
physical assertion. Here, this assertion is presented explicitly as a physical prin￾ciple: ‘every finitely realizable 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 Tur￾ing machines is described, and it is shown that quantum theory and the ‘universal
quantum computer’ are compatible with the principle. Computing machines re￾sembling 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 tasks can be per￾formed faster by a universal quantum computer than by any classical restriction
of it. The intuitive explanation of these properties places an intolerable strain on
all interpretations of quantum theory other than Everett’s. Some of the numerous
connections between the quantum theory of computation and the rest of physics
are explored. Quantum complexity theory allows a physically more reasonable
definition of the ‘complexity’ or ‘knowledge’ in a physical system than does clas￾sical complexity theory