Deutsch [Deutsch, 1985] mentions some ways in which superpositonal quantum computation can help us understand other physical phenomena:
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.
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.
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.