In The Fabric of Reality, David Deutsch argues the following:

To those who still cling to a single-universe world-view, I issue this challenge: explain how Shor's algorithm works. I do not merely mean predict that it will work, which is merely a matter of solving a few uncontroversial equations. I mean provide an explanation. When Shor's algorithm has factorized a number, using $10^{500}$ or so times the computational resources that can be seen to be present, where was the number factorized? There are only about $10^{80}$ atoms in the entire visible universe, an utterly minuscule number compared with $10^{500}$. So if the visible universe where the extent of physical reality, physical reality would not even remotely contain the resources required to factorize such a large number. Who did factorize it, then? How, and where, was the computation performed?

Doesn't this imply the existence of the multiverse? How/where could the number be factorized otherwise?

This thread does not answer this question, as 1. the fact that there are still some unknowns doesn't necessarily mean the multiverse theory is wrong, and 2. it doesn't explain how/where the number could be factorized otherwise if not in the so-called "parallel universes".

  • $\begingroup$ Welcome to QCSE! I like this question but versions of it has been asked before. Have you seen this question and some of the answers? $\endgroup$ Mar 2, 2023 at 0:32
  • $\begingroup$ In particular, Deutsch’s argument would apply equally well to a quantum algorithm that efficiently solves a 3-SAT problem, but there is no evidence that a quantum computer could do that. Many people find this position in his book to be an incomplete argument for the multiverse. $\endgroup$ Mar 2, 2023 at 0:35
  • $\begingroup$ @MarkS thanks for sharing! I had already read that thread earlier, but it doesn't seem to really answer how/where the number could be factorized otherwise, unfortunately. If it doesn't happen in the so-called "parallel universes", where does it happen? $\endgroup$ Mar 2, 2023 at 1:10
  • $\begingroup$ By the way, if I understand your answer correctly, it doesn't necessarily refute the existence multiverse, as you indicate that there are still some unknowns, but the existence of these unknowns doesn't mean the multiverse theory is wrong. $\endgroup$ Mar 2, 2023 at 1:11
  • 1
    $\begingroup$ Does this answer your question? Effects of quantum computing on parallel universes $\endgroup$ Mar 2, 2023 at 21:25

3 Answers 3


MWI doesn't merely imply Shor's algorithm, it explains it. I don't agree with the assertion that the other interpretations of quantum mechanics simply must have their own interpretation of where the computational resources required for Shor's algorithm are sourced. Because the truth is that MWI interpretation is the only one that seriously provides explanation, and the challenge remains unanswered.

So the 'Z' referred to is assumed without any evidence that the supposed alternative explanations given by the alternate interpretations that constitute Z actually exist. This is the whole point of Deutsch's argument for MWI.

To reply to the general related question of why we should ask where this computation is taking place. Deutsch argues that computation is physical and therefore requires physical computational resources. It seems perfectly legitimate therefore to ask where these resources come from, in the same way that we might ask where the memory and flippable bits that are performing the computation that allows me to post this message actually are. Would you deny that they are in our universe? If universe is to mean anything?

  • 1
    $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Sep 3, 2023 at 22:49
  • 2
    $\begingroup$ let me remark that this view is subjective, as in, there are many experts in the field which would disagree with this view (and, of course, there will be others which agree). A sentence such as "Because the truth is that MWI interpretation is the only one that seriously provides explanation" is for example quite loaded, and pretty much just a personal opinion. I'm writing this because the phrasing here might make it seem like these things are established and taken as true in the relevant community. Which they aren't $\endgroup$
    – glS
    Sep 8, 2023 at 12:43

This is an example of the fallacy "if I know X implies Y and I know Y then I know X". But it could also be that Z implies Y. In this case, Y is Shor's algorithm, X is the many worlds interpretation, and Z is any other interpretation of quantum mechanics.

Suppose someone likes the QBism interpretation. You ask them if they expect factoring to work. They say "Of course! Because [qbism interpretation of what factoring is doing].". Then you say "by the way, I factored a number with Shor's algorithm yesterday". Do you really expect them to then say "Oh! Well then QBism is disproved, and I shall become a many worldser!"?

To distinguish between different hypothesis, you need tests where the hypothesis disagree on what the outcome will be. If you can find any quantum interpretations that say Shor's algorithm won't work, then running Shor's algorithm will disprove those interpretations. But I suspect you'll find that interpretations other than many worlds have their own way of explaining what Shor's algorithm is doing.

All that said, I do think that someone who believes collapse interpretations are correct is more likely to think "maybe, MAYBE, we'll run into some kind of spontaneous collapse mechanism that prevents scaling". Whereas a many worldser will bet confidently and without reservation on "of course Shor's algorithm has to work". In this sense, applying Bayes rule to "Shor's algorithm worked" must cause a small update away from collapse interpretations (by eliminating the ones with spontaneous collapse) and towards many-worlds interpretations. And seeing it not work would cause an enormous update away from many-worlds.

  • $\begingroup$ Why would collapse interpretations have a lower prior to Shor’s algorithm working? Can’t you be a good Copenhagenigast and also accept the threshold theorem? $\endgroup$ Mar 2, 2023 at 2:40
  • 1
    $\begingroup$ @MarkS Yes they can. But they might also wonder if there are any spontaneous collapse processes. Or not. But I suspect a person who believes collapse interpretations is more likely to wonder whether there are spontaneous collapse processes then a person who believes in many worlds. That's all I meant by they would assign a lower probability. A person can of course assert collapse with no spontaneous collapse, in which case they are assigning a very high probability to Shor working. $\endgroup$ Mar 2, 2023 at 2:45
  • $\begingroup$ BTW: The logical fallacy is known as the converse error. $\endgroup$ Mar 2, 2023 at 6:32

David Deutsch had been pondering the implications of similar thought-experiments since well before even Shor's algorithm. In his earlier 1985 paper he considered using a quantum computer to track the stock market in superposition, providing almost exactly the same question as he poses in The Fabric of Reality but swapping factoring numbers with stock market predictions:

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?

Shor's remarkable '94 discovery certainly made Deutsch's rhetorical questioning more pronounced than a question about using a quantum computer for record keeping on the stock market, but even the above question in the earlier '85 paper, in my mind, suffers exactly the same problems as discussed earlier. For example, why does he insist that "it" be computed somewhere? This comment about "delegating subtasks" also seems quite anthropic. Why must any task be delegated?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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