Does Shor's algorithm imply the existence of the multiverse?

Question

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

Answer 1

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?

Answer 2

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.

Answer 3

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?