qc000015.htm

4.3 Deutsch’s computer

Deutsch’s [48] starting point is a challenge to the Church–Turing Thesis. Any classical computation evolves from a set of input states to a set of output states; states are “labelled" in some standard way. For a classical Turing machine, the output is a definite function of the prepared input; the measurement can, at least in principle, be done by an outside observer and will be the same if the measurement is repeated. In this way one can define, in a coherent way, the notion of Turing computable function. Two Turing machines are computationally equivalent when they compute the same function.

Quantum machines (and probabilistic or stochastic machines) do not compute functions in the above sense! The output state of a stochastic machine is “random" and only the probability distribution function for possible outputs depends on the input state. The quantum state of a quantum machine, although completely determined by the input state, is not an observable and, consequently, the user has no access to it. There exists, however, various ways to generalize the notion of “computational equivalence" for such machines. One possible way is to look carefully at labels. Like in the classical case, labels should be provided for all possible combinations of input states. As measurements cannot in general determine the output state, labels for output states should be done for the set of pairs consisting of an output observable and a possible measured value of that observable. Such a pair contains the specification of a possible experiment that could in principle carry on the output together with a possible result of the experiment. We can now say that two computing machines are computationally equivalent under given labellings if any possible experiment (or sequence of experiments) in which their inputs were prepared equivalently (with respect to the input labellings) and observables corresponding to each other under the output labellings are measured, the measured values of these observables are statistically indistinguishable. According to the above criterion, a given computing machine “computes" a unique function.

Figure 13: David Deutsch

The Church–Turing Thesis is manisfestly non-physical. There is, however, a subtle physical principle deriving from it, which, according to Deutsch [48], p. 99, reads:

Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means. _

This statement asks for some definitions. A finitely realizable physical system includes any physical object on which experimentation is possible. A computing machine

is capable of perfectly simulating a physical system

, under given labelling of inputs and outputs, if there is a program for

that makes

computationally equivalent to

under that labelling. Re-phrased,

becomes under a certain program and a fixed labelling, a system “computationally indistinguishable" from

. Deutsch [48], p.100, argued that the above principle is stronger than the Church–Turing Thesis: it is not satisfied by Turing machines in classical physics, but it is compatible with quantum theory. This observation motivates the interest, and the urgency, in seeking a “truly quantum" model of computation.

Deutsch’s quantum Turing machine has an infinite sequence of qubits (the tape),

, and a control consisting of a finite sequence of qubits,

. In addition, Deutsch uses an observable,

, which has an integer as possible value. The state of the quantum computer is a unit vector in the space spanned by basis vectors

. The dynamics is given by a constant unitary operator

. With these ingredients, Deutsch [48] has described a universal quantum computer, that is one capable of simulating perfectly every finitely realizable physical system (hence, every quantum computer). As applications he proposed the random generation procedure described in Section 3.6.