2
$\begingroup$

Quantum algorithms are inherently probabilistic. Let's say I run Shor's factoring algorithm on some number. There's a chance that the output I observe is incorrect. Does the many-worlds theory suggest that I'm simply in a universe where the output happened to be wrong? Because the probability of error is slim, does that mean the vast majority of universes realize a correct execution of the algorithm?

Edit: Thanks to Mark S for pointing me to Effects of quantum computing on parallel universes which fully explores my question. Also, a big thanks to everyone who commented here! The questions raised and resources raised have only helped to enhance my curiosity about the subject.

$\endgroup$
  • 2
    $\begingroup$ This is covered in chapter 10 of Quantum Computing since Democritus by Scott Aaronson. You'll also find a ton of posts about the MWI on his Shtetl-Optimized blog. $\endgroup$ – Sanchayan Dutta Jan 26 at 6:47
  • 5
    $\begingroup$ Hi TWal, and welcome to QCSE. This may answer your question? Effects of quantum computing on parallel universes If not, can you consider revising your question more? $\endgroup$ – Mark S Jan 27 at 23:57
0
$\begingroup$

Quantum algorithm can give answers with 100% certainty. For example, Grover's algorithm can give the answer with certainty when the ratio of "good" items to "bad" items satisfies some constraints. The uncertainty exists when the output state is not an eigenstate of the measurement observable.

On the other hand, Shor's algorithm is a hybrid of classical and quantum steps. The quantum order finding step might fail to find an appropriate "order" in an iteration, but you cannot say it is incorrect. Instead, the measurement gives one of the phases of the unitary operator $U|y\rangle =|xy \text{(mod } N\text{)}\rangle$, the phase can then be used to derive the order classically. However only some of these orders can be used to find the factors. If the order found after measurement is not appropriate, Shor's algorithm need to repeat the quantum step (together with some classic steps). (There are multiple phases because the input $|1\rangle$ is a superposition of many eigenvectors associated with these phases.)

Many word theory is more philosophical than computationally or informational. Using this theory, at least one of the world will find an appropriate order in the first iteration and Shor's algorithm will stop quicker. In some world, all iterations fail (as long as you continue) to find the appropriate order and Shor's algorithm will not finish. Of course, Shor proved that the probability of not finishing can be arbitrarily low given enough iterations.

Some people reject many world theory using a joke: you can believe it in the other worlds. To me, the challenge is where does the (exponential, enormous) extra energy come as worlds split all the time?

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @czwang: You mentioned that Grover algorithm is able to find a correct answer with 100 % certainty. From many-worlds perspective, does this mean that Grover work properly only in one of these many worlds? Or, does this mean that there is no splitting of words ? $\endgroup$ – Martin Vesely Jan 26 at 6:59
  • 3
    $\begingroup$ Why should there be extra energy as a result of world splitting? (What's your normalisation?) $\endgroup$ – Niel de Beaudrap Jan 26 at 12:20
  • 2
    $\begingroup$ @Martin Vesely: In the special cases, Grover algorithm ends in a single eigenstate with eigenvalue 1 before measurement. As a result, measurement does not result in world splitting. $\endgroup$ – czwang Jan 26 at 17:06
  • 1
    $\begingroup$ @Niel de Beaudrap: as far as I understand, energy is preserved in each world. Splitting adds new worlds, each contains the same amount of energy as the world before the split. I am not saying this assumption is wrong, just I have a hard time to believe it. $\endgroup$ – czwang Jan 26 at 17:10
  • 1
    $\begingroup$ @TWal: you are right, the sentence is a bit misleading. I will edit it to clarify and hopefully address you questions. $\endgroup$ – czwang Jan 26 at 17:34

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