I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$.

We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies \begin{equation} \Big| \dfrac{s}{r} - \psi \Big| \leq \dfrac{1}{2r^{2}} \end{equation} which means that if $\psi$ has continued fraction algorithm $[a_0,\dots,a_N]$ then $\dfrac{s}{r}$ has continued fraction $[a_0,\dots,a_k]$ for $k \leq N$.

The book just says that then applying the continued fractions algorithm to $\psi$ we obtain $r'$ which is our estimate for $r$. I'm not too sure how exactly we arrive at this value of $r'$. Is it just that once we obtain our expansion $\psi = [a_0,\dots,a_N]$, we obtain a value $r'_{m}$ for each of the $m^{th}$ convergent expansions and see which one is correct?


Yes, that's exactly the idea. It is inspired by the following fact:

Theorem. Let $\psi$ be an irrational number, and suppose $|\psi - s/r| \le 1/2r^2$. Then $s/r$ is one of the convergents of the continued fraction expansion of $\psi$.

In other words, every "very good" approximation to $\psi$ can be obtained by computing the continued fraction representation of $\psi$ and looking at one of its convergents.

In the specific situation you mentioned, we know $\psi$, and we don't know $s$ or $r$. However, we know that there exist $s,r$ such that $|\psi - s/r| \le 1/2r^2$. It follows from the theorem that $s/r$ must be one of the convergents of the continued fraction of $\psi$.

Therefore, if we iterate through the convergents of the continued fraction for $\psi$, this is guaranteed to find $s,r$. Moreover, this procedure is efficient: you'll only have to look at $O(\lg r)$ convergents, so the running time will be polynomial in $\lg N$.

See also https://math.stackexchange.com/q/1139381/14578.


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.