3
$\begingroup$

"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:

  1. "Quantum parallelism cannot be used to improve the mean running time of parallelizable algorithms." (p. 112, top)

  2. Quantum parallelism could be used to prove the many-worlds interpretation of quantum mechanics, specifically:

Interpretational implications

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?

$\endgroup$
1
3
$\begingroup$

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.

This is an interpretational issue. If you are an Everettian, then quantum parallelism is real and this is the source of the speedup. If you're not, then it's not real and this sense of quantum parallelism does not exist. I believe that, for Deutsch, the only way that he understands some of this is if the many worlds theory is true. For him, running these experiments and seeing the speedup is a form of proof of many worlds. Although it is not in the form of making falsifiable predictions.

This does not make any actual experiment or theory in his papers wrong. It's just this interpretational issue that is unresolved.

$\endgroup$
4
  • $\begingroup$ Well, presumably there either is a speedup or there isn't, right? $\endgroup$
    – vy32
    Jul 21 '20 at 3:13
  • 1
    $\begingroup$ There is a speed up. This is about how you explain the origin of that speed up. $\endgroup$
    – DaftWullie
    Jul 21 '20 at 5:04
  • $\begingroup$ Just question, if many-worlds interpretation of quantum mechanics implies exponential speed-up, what about Grover algorithm which offers only quadratic speed-up? Isn't it the counter example to many-worlds explanation? $\endgroup$ Jul 21 '20 at 6:25
  • $\begingroup$ many worlds gives one possible way of understanding/interpreting the origin of an exponential speed-up if there is one. It makes essentially no testable hypotheses that distinguish it from any other (standard) interpretation. $\endgroup$
    – DaftWullie
    Jul 21 '20 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.