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

Let's go a step back.Consider the steps in the order finding subroutine.

$\frac{s}{r}$ is the phase of the eigenvalue of the "mod" operator in the routine. What we obtain after the inverse Fourier Transform in phase determination is an n-bit approximation to $\frac{s}{r}$.

This in base 10 is like a real number $0.232..$ upto some number of digits.What we require is the fraction which represent this number($\frac{s}{r}$) from which we can obtain $r$ for further use in the algorithm.

Suppose you obtain the approximation as $0.234$.A naive way to get the rational representation is write it as follows and cancelling the common factors: $$\frac{234}{1000} \rightarrow \frac{117}{500}$$ and see that $gcd(117,500) = 1$.

This naive method required you to know the factors of the numerator and the denominator.But since we are in an algorithm that actually finds the factors of a given integer, this naive method is of no avail to us.

Here is where continued fractions come in. Define the following: $$x = 0.234$$ $$x_0 = x;a_0 = [x]$$ Now let $$x_{i+1} = \frac{1}{x_i - a_i} ; a_{i+1} = [x_{i+1}]$$ until $x_i = a_i$ for some $i$.

Observe that this procedure yield the convergents $[a_0;a_1,...]$ for x.For example applying it $x=0.234$ we observe that $a_0 = 0$,$a_1 = 4$,$a_2 = 3$,$a_3 = 1$,$a_4 = 1$,$a_5 = 1$,$a_6 = 10$ and the algorithm stops.

Hence using these convergents we have $$0.234 = 0 + \frac{1}{4 + \frac{1}{3 + \frac{1}{1...}}}$$Substituting the values on the RHS, we obtain a rational number $\frac{117}{500}$.By this procedure we obtain the same rational number only here we need not know the factors beforehand.

Though in this conjured example, it may seem that cancelling factors would be easy and short, the continued fractions method offers generality as well as speed as the only operations that we are doing is division and addition.