Deutsch [Deutsch, 1985] mentions some ways in which superpositonal quantum computation can help us understand other physical phenomena:

**Complexity measure**-
Traditional computation-based complexity measures (e.g., the complexity of a string of digits is the length of the shortest computer program that can print that string) have the problem that they classify noise as complex. The stochastic nature of quantum computation allows one to use it to provide a complexity measure that will classify noise as non-complex, since it can be generated by a very simple program on a quantum computer.

**Foundations**-
Deutsch suggests that this complexity measure could be used in the following way: one can postulate that the universe moves from the quantum-simple to the quantum-complex, and derive the third law of thermodynamics, and the psychological arrow of time from that.

**Experimentation**-
Given that a quantum computer is a true quantum system, one could program it so that its operation actually tests various physical hypotheses.

However, the aspect of the relevance of quantum computation to physics on which I wish to concentrate has to do with the interpretation of quantum mechanics. The standard interpretation of quantum phenomena is in terms of wave/particle duality: each quantum is a system with both particle and wave aspects. In the two slit experiment, for example, the particle-like aspect of the system is realized in, among other things, there being a hit on the plate at a particular point; at the same time, the wave-like aspect of the system is realized in the fact that the probability of there being a hit at any given point is [roughly] the value of the wave function at that point. These aspects are thought to be complementary: both are necessary, but in a sense they are also mutually exclusive.

There are other interpretations, however. The two to be
mentioned briefly here are Everett's *many worlds*
interpretation [Everett, 1983], in which the superpositional state
is actually a superposition of universes, one for each possible
value of the observable; and Bohm's *ontological* or *causal*
interpretation [Bohm and Hiley, 1993], in which there are particles, but
they are always accompanied by a new type of field (the *
quantum field*), which in turn yields a potential (the *
quantum potential*). The quantum field (and thus the quantum
potential) is shaped by the experimental configuration, and thus
can affect the trajectory of the particle in such a way as to
generate the kind of behaviour (apparent indeterminacy, non-
local sensitivity to slit configuration, etc.) that the standard
interpretation attempts to explain in terms of the wave-like
aspect of a quantum.

Deutsch sees quantum computation as implying the many worlds interpretation of quantum mechanics. He uses the many-worlds interpretation freely in explaining his ideas, and although he admits that these explanations could be re-formulated for other interpretations, he feels this can only be done with some loss of explanatory power.

On Deutsch's view, a superposition of *n* quantum states can be used
to perform parallel processing, although only one of the *n* results
will be accessible in a given world. Although the expected *mean*
running time of a superpositional quantum computation is no better
than a classical parallel version, Deutsch claims that some of the
time the computation may take much less time than the fastest possible
classical implementation. He reasons as follows: assume that a
quantum computer has been set up to compute a task which classically
takes at least two days; assume that there is a program that extracts
the info from the superpositional state in negligible time, with a
certain probability of success per unit time (per day, suppose). Then
there is a non-zero probability that the information will be extracted
from the superpositional state in just one day, faster than the
classical limit. One can just check the halt bit to see if a two-day
computation has occurred in one day. Deutsch uses the illustration of
a Stock Exchange simulation program that predicts activity one day in
advance, but classically takes two days to run; if run on a quantum
computer, there will be lucky days where one manages to run the
simulation in only one day, so one can actually use the predictions to
invest successfully.

Deutsch suggests that the many-worlds interpretation is necessary for
understanding such a program when he asks: ``On the days when the
computer succeeds in performing two processor-days of computation, how
would the conventional interpretations explain the presence of the
correct answer? *Where was it computed?*'' [Deutsch, 1985, p 114, emphasis
his,]. I'm not convinced that quantum computation supports
the many-worlds interpretation, mainly becaused I am not convinced
that Deutsch's account of the Stock Exchange simulator is correct.

For one thing, the presence of a halt bit would seem to destroy the
coherence of the state being used in the computation. As Deutsch
himself points out, a quantum computer ``must not be observed before
the computation has ended, since this would, in general, alter its
relative state'' [Deutsch, 1985, p 104,]. So he requires that there
be a halt bit that can be observed, without affecting the operation of
the quantum computer. But this seems paradoxical: if the halt bit
depends on the computational state, then surely observing it will
collapse the superpositional state, just as observing a light that
indicates the presence of poison in Schrödinger's Box will either
kill or save Schrödinger's Cat. On the other hand, if the halt bit
*is* independent of the computation, then it isn't really a halt
bit, any more than a flip of a coin would be: if the halt bit goes on,
it can only be an accident that the machine has in fact halted. But
even if the halt bit *could* indicate to one that the computation
had been achieved in a shorter time than a classical computation,
there seems to be no guarantee that this computational result is the
one available in our world; the most we can know is that the correct
result was obtained in *some* world. Whether that knowledge could
be used in the way Deutsch intends has not been made clear.

Furthermore, even if one is convinced (as Penrose seem to be) that quantum parallelism can do the work that Deutsch claims it can, it seems that one can dispute (as Penrose does) Deutsch's claim that this argues in favour for the many-worlds interpretation [Penrose, 1989, p 401, fn 9,].

Despite these disagreements, I am intrigued by Deutsch's explicit endorsement of the idea that the various interpretations of quantum mechanics can be distinguished experimentally. Whether or not the ontological interpretation is required in order to properly explain, think about and design quantum learning systems remains to be seen.

Wed Nov 20 01:10:59 GMT 1996