Shor's algorithm effectiveness

In Shor's algorithm we require the period to be even. If the period is not even or $$x^{r/2}+1 \equiv 0 \bmod N$$ then we have to restart the process and pick a new random $$x$$. Why do we know that the process will work for some $$x$$ and still be quicker than the current method of just checking if factors work?

(Here $$r$$ is the period, $$x$$ is the random number given at the start of Shor's, $$N$$ is the number to be factorised.)

1 Answer

Check out Thoerem 5.3 in Nielsen and Chuang. It conveys that we are almost guaranteed to get a good value of $$x$$ (the probability is stated to be at least $$1-\frac{1}{2^m}$$ where there are $$m$$ unique prime factors of $$N$$). The expected number of repetitions of the algorithm (due to this effect) is only just more than 1. At worst, it's 2. There's no absolute guarantee that in a particular instance you wouldn't need many, many repetitions, it's just ridiculously unlikely.

• Would you by chance know where to find a proof of this theorem? There doesn't appear to be one in the book. Dec 29 '20 at 15:49
• @paulinho Appendix 4, section A4.3 of Nielsen & Chuang. Dec 30 '20 at 7:56