From: Hal <hfinney@shell.portal.com>
Date: Wed, 30 Mar 94 20:30:31 PST
To: cypherpunks@toad.com
Subject: Crypto and new computing strategies
Message-ID: <199403310431.UAA16193@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


British physicist David Deutsch has been writing for several years on
the theoretical properties of computers which would exploit quantum
mechanics.  Here is the abstract from his paper in Proc. R. Soc. Lond. A,
v 400, p97-117, 1985:

Quantum Theory, the Church-Turing Principle and the Universal Quantum
Computer

"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 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 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
be performed 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 classical complexity theory."