"Quantum theory, the Church-Turing principle and the universal quantum computer" (Deutsch 1985b) appears to introduce the term of "quantum parallelism" (the term is not in "Quantum Theory as a Universal Physical Theory" (Deutsch 1985a)). He makes two obvious (to me) claims:
"Quantum parallelism cannot be used to improve the mean running time of parallelizable algorithms." (p. 112, top)
Quantum parallelism could be used to prove the many-worlds interpretation of quantum mechanics, specifically:
I have described elsewhere (Deutsch 1985; cf. also Albert 1983) how it would be possible to make a crucial experimental test of the Everett (‘many-universes’) interpretation of quantum theory by using a quantum computer (thus contradicting the widely held belief that it is not experimentally distinguish- able from other interpretations). However, the performance of such experiments must await both the construction of quantum computers and the development of true artificial intelligence programs. In explaining the operation of quantum computers I have, where necessary, assumed Everett’s ontology. Of course the explanations could always be ‘translated’ into the conventional interpretation, but not without entirely losing their explanatory power. Suppose, for example, a quantum computer were programmed as in the Stock Exchange problem described. Each day it is given different data. The Everett interpretation explains well how the computer’s behaviour follows from its having delegated subtasks to copies of itself in other universes. 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?
My reading of the paper is the Deutsch, in 1985, thinks that quantum turing machines are fundamentally more powerful than classical turing machines, because QTMs can simulate a CTM but CTMs cannot simulate a QTM.
My reason for asking the question is that Deutsch seems to be implying that quantum parallelism is real, and that it can be used for significant speedup, but my understanding is that quantum parallelism, in this sense, does not exist.
So is this early article wrong and, if so, how can it be wrong? Are the proofs wrong? Or is the quantum parallelism something that is conjectured and not proven?
And what about the many worlds?