A novel, “physical”, version of Church’s thesis is proposed: Any finite realizable physical system can be simulated by a universal finite means computing machine. It is claimed that the thesis is false in classical physics due to the continuous nature of the states available to finite realizable classical systems. A construction is offered for the appropriate finite means quantum computer, and it is claimed that such a “machine” does obey the “physical” version of a Church thesis given above. The universal quantum computer differs from the classical primarily in allowing a class of programs which evolve computational basis states into linear superpositions of one another. The problem of the irreducible interaction of a finite system with an external environment is discussed in this computational context. Next it is argued that “quantum theory is a theory of parallel interfering universes”, and that “there are circumstances under which different computations performed in different universes can be combined in
[ the universal quantum computer ] giving it a limited capacity for parallel processing”. The “quantum parallelism” allegedly shows up in the ability in some cases to do a better job of minimizing some minimum or maximum computation time than could be obtained by a stricly serial quantum computation. It is claimed that these results can be used to give an experimental test of the Everett (“many-universe”) interpretation of quantum mechanics against the other interpretations, contrary to the usual belief that all the interpretations are experimentally indistinguishable. It is claimed that only the Everett interpretation offers an answer to the question which arises when computation is speeded up by “parallel processing”: “where did the parallel computations take place?”. Next the discussion turns to the use of quantum computation to determine “complexity” of a state. It is argued that counterintuitive results of a definition of C. H. Bennett become more acceptable in the quantum context. Other relations to such problems as “why quantum mechanics is the case” and the direction of time and growth of complexity are briefly touched upon.