5
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Would you by chance know where to find a proof of this theorem? There doesn't appear to be one in the book. $\endgroup$
    – paulinho
    Dec 29, 2020 at 15:49
  • 1
    $\begingroup$ @paulinho Appendix 4, section A4.3 of Nielsen & Chuang. $\endgroup$
    – DaftWullie
    Dec 30, 2020 at 7:56

Your Answer

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

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