# Continued Fraction Algorithm in Shor's Algorithm

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 $$\Big| \dfrac{s}{r} - \psi \Big| \leq \dfrac{1}{2r^{2}}$$ 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?

• You might want to try this on Theoretical Computer Science instead of here. It seems your question deals with the mechanics of the quantum computation rather than the underlying physics mechanics of quantum computing. That is, you have an algorithm question and not a physics one. – Reid Erdwien Mar 20 '15 at 21:52
• $\uparrow$ Which book? Which page? – Qmechanic Mar 20 '15 at 22:17
• @Qmechanic Quantum Computation and Quantum Information. M. Nielsen and I. Chuang – Zach Dean Mar 20 '15 at 22:47
• This question was asked on cstheory.SE, and a much better answer was given. This one is rather misleading. – Peter Shor Jul 4 '16 at 12:25

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.

• Actually, canceling factors doesn't work at all because it doesn't get all good approximations. Suppose the right answer is 11/47 ≈ 0.2340425 — pretty close to 0.234. How do you get that by canceling factors? It's easy with continued fractions: 11/47 = 1/(4+1/(3+1/(1+1/(1+1))). – Peter Shor Jul 4 '16 at 18:44