4
$\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.)

$\endgroup$
5
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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