Continued Fraction Algorithm in Shor's Algorithm

Question

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?

Answer 1

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.

Answer 2

I don't think you have to do iterations over $r'$ for checking. In fact, performing iterations would lead to $O(L^4)$ complexity instead of $O(L^3)$ as claimed in the textbook. So how do we know which convergent of the continued fraction is the one we are looking for? The way is as follows.

First, I'll post some facts in number theory here.

Fact 1. Let $ \varphi $ be a rational number. Suppose $ s, r $ are co-prime integers such that $ \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2r^2} $, then $ s/r $ is a convergent of the continued fraction for $ \varphi $.

Fact 2. Suppose $ \varphi = \left[ a_0, \cdots , a_N \right] $. Denote the $ n $-th convergent as $ p_n/q_n $. Then $ q_n $ is increasing in $ n $, while $ \left| \dfrac{p_n}{q_n} - \varphi \right| $ is decreasing in $ n $.

Fact 3. Let $ \varphi $ be a real number and $ N \ge 2 $ be an integer, then there is at most one fraction $ s/r $ with $ 1 \le r < N $ and $ \gcd(s,r)=1 $ such that $ \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2N^2} $.

The first two facts are well-known theorems about continued fractions. While the third one is just a corollary by observing that any two different fractions with denominators smaller than $ N $ must be spaced on the real axis with a distance at least $ \dfrac{1}{N^2} $.

Now, let's go back to the specific situation in your question. By performing phase estimation algorithm with $ t = 2L + 1 + \left\lceil \log \left( 2 + \dfrac{1}{2\epsilon} \right) \right\rceil $ qubits in the first register, with high probability at least $ 1-\epsilon $, we will obtain an estimate, $ \varphi $, of some $ s/r $ for a randomly picked $ s $ accurate to $ 2L+1 $ bits. Thus, $ \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2^{2L+1}} \le \dfrac{1}{2N^2} < \dfrac{1}{2r^2} $.

Suppose $ \gcd(s,r)=1 $. From Fact 1, we know that $ s/r $ is a convergent of the continued fraction of $ \varphi $. From Fact 2 and Fact 3, we know that $ r $ must be the largest $ q_n $ that is smaller than $ N $ (since otherwise there will be $ q_{n'} $ such that $ r < q_{n'} < N $ and therefore $ \left| \dfrac{p_{n'}}{q_{n'}} - \varphi \right| < \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2N^2} $, which is in conflict with Fact 3).

In conclusion, supposing $ \gcd(s,r)=1 $, with high probability, we can obtain the right $ r $ following the procedure: Calculate the convergents of $ \varphi $ using the continued fraction algorithm one by one, until we arrive at the last convergent (the denominator will be $r$) or we find that $ q_n \ge N $ ($ q_{n-1} $ will be $r$).

The sentence "The number $r′$ is our candidate for the order" in the textbook is to remind us that there is still possibility that $ \varphi $ is a bad estimate or $ \gcd(s,r) $ happens not to be one.