Quantum Theory, The Church-Turing Principle And The Universal Quantum Computer

Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer D. Deutsch Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences, Vol. 400, No. 1818. (Jul. 8, 1985), pp. 97-117.
Stable URL: http://links.jstor.org/sici?sici=0080-4630%2819850708%29400%3A1818%3C97%3AQTTCPA%3E2.0.CO%3B2-A Proceedings of the Royal Society of London. Series A,Mathematical and Physical Sciences is currently published by The Royal Society.

Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies ofarticles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at http://www.jstor.org/journals/rsl.html. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of suchtransmission.

JSTOR is an independent not-for-profit organization dedicated to and preserving a digital archive of scholarly journals. For more information regarding JSTOR, please contact support@jstor.org.

http://www.jstor.org Thu Apr 12 15:07:45 2007

Proc. R. Soc. Lond. A 400, 97-117 (1985) Printed in Great Britain

Quantum theory, the Church-Turing principle and the universal quantumcomputer
B Y D. D E U T S C H

Department of Astrophysics, South Parks Road, Oxford O X 1 3RQ, U.K. (Communicated by R. Penrose, F.R.S. - Received 13 July 1984)

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 simulatedby 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, a t 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 tasks can beperformed 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 reasonabledefinition of the ' complexity ' or ' knowledge ' in a physical system than does classical complexity theory.

The theory of computing machines has been extensively developed during the last few decades. Intuitively, a computing machine is any physical system whose dynamical evolution takes it from one of a set of 'input' states to one of a set of 'output' states. The states are labelled insome canonical way, the machine is prepared in a state with a given input label and then, following some motion, the output state is measured. For a classical deterministic system the measured output 1,abelis a definite function f of the prepared input label; moreover the value of that label can in principle be measured by an outside observer (the ' u s e r ' ) and the machine is said to 'compute'...