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

<p><strong>Theorem.</strong> 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$.</p>

<p>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.</p>

<hr>

<p>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$.</p>

<p>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$.</p>

<hr>

<p>See also <a href="https://math.stackexchange.com/q/1139381/14578">https://math.stackexchange.com/q/1139381/14578</a>.</p>

CC BY-SA 3.0
2015-03-21T00:17:59.633Z
2015-03-21T00:17:59.633Z
2017-04-13T12:19:19.363Z
D.W.
<p>I don't think you have to do iterations over <span class="math-container">$r'$</span> for checking. In fact, performing iterations would lead to <span class="math-container">$O(L^4)$</span> complexity instead of <span class="math-container">$O(L^3)$</span> 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.</p>
<p>First, I'll post some facts in number theory here.</p>
<p><strong>Fact 1</strong>. Let <span class="math-container">$ \varphi $</span> be a rational number. Suppose <span class="math-container">$ s, r $</span> are co-prime integers such that <span class="math-container">$ \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2r^2} $</span>, then <span class="math-container">$ s/r $</span> is a convergent of the continued fraction for <span class="math-container">$ \varphi $</span>.</p>
<p><strong>Fact 2</strong>. Suppose <span class="math-container">$ \varphi = \left[ a_0, \cdots , a_N \right] $</span>. Denote the <span class="math-container">$ n $</span>-th convergent as <span class="math-container">$ p_n/q_n $</span>. Then <span class="math-container">$ q_n $</span> is increasing in <span class="math-container">$ n $</span>, while <span class="math-container">$ \left| \dfrac{p_n}{q_n} - \varphi \right| $</span> is decreasing in <span class="math-container">$ n $</span>.</p>
<p><strong>Fact 3</strong>. Let <span class="math-container">$ \varphi $</span> be a real number and <span class="math-container">$ N \ge 2 $</span> be an integer, then there is at most one fraction <span class="math-container">$ s/r $</span> with <span class="math-container">$ 1 \le r &lt; N $</span> and <span class="math-container">$ \gcd(s,r)=1 $</span> such that <span class="math-container">$ \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2N^2} $</span>.</p>
<p>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 <span class="math-container">$ N $</span> must be spaced on the real axis with a distance at least <span class="math-container">$ \dfrac{1}{N^2} $</span>.</p>
<p>Now, let's go back to the specific situation in your question. By performing phase estimation algorithm with <span class="math-container">$ t = 2L + 1 + \left\lceil \log \left( 2 + \dfrac{1}{2\epsilon} \right) \right\rceil $</span> qubits in the first register, with high probability at least <span class="math-container">$ 1-\epsilon $</span>, we will obtain an estimate, <span class="math-container">$ \varphi $</span>, of some <span class="math-container">$ s/r $</span> for a randomly picked <span class="math-container">$ s $</span> accurate to <span class="math-container">$ 2L+1 $</span> bits. Thus, <span class="math-container">$ \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2^{2L+1}} \le \dfrac{1}{2N^2} &lt; \dfrac{1}{2r^2} $</span>.</p>
<p>Suppose <span class="math-container">$ \gcd(s,r)=1 $</span>. From <strong>Fact 1</strong>, we know that <span class="math-container">$ s/r $</span> is a convergent of the continued fraction of <span class="math-container">$ \varphi $</span>. From <strong>Fact 2</strong> and <strong>Fact 3</strong>, we know that <span class="math-container">$ r $</span> must be the largest <span class="math-container">$ q_n $</span> that is smaller than <span class="math-container">$ N $</span> (since otherwise there will be <span class="math-container">$ q_{n'} $</span> such that <span class="math-container">$ r &lt; q_{n'} &lt; N $</span> and therefore <span class="math-container">$ \left| \dfrac{p_{n'}}{q_{n'}} - \varphi \right| &lt; \left| \dfrac{s}{r} - \varphi \right| \le \dfrac{1}{2N^2} $</span>, which is in conflict with <strong>Fact 3</strong>).</p>
<p>In conclusion, supposing <span class="math-container">$ \gcd(s,r)=1 $</span>, with high probability, we can obtain the right <span class="math-container">$ r $</span> following the procedure: Calculate the convergents of <span class="math-container">$ \varphi $</span> using the continued fraction algorithm one by one, until we arrive at the last convergent (the denominator will be <span class="math-container">$r$</span>) or we find that <span class="math-container">$ q_n \ge N $</span> (<span class="math-container">$ q_{n-1} $</span> will be <span class="math-container">$r$</span>).</p>
<p>The sentence <em>&quot;The number <span class="math-container">$r′$</span> is our candidate for the order&quot;</em> in the textbook is to remind us that there is still possibility that <span class="math-container">$ \varphi $</span> is a bad estimate or <span class="math-container">$ \gcd(s,r) $</span> happens not to be one.</p>

CC BY-SA 4.0
2020-07-07T05:28:09.213Z
2020-07-07T05:28:09.213Z
Conn-CaoYK
<p>I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$.</p>

<p>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$.</p>

<p>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?</p>

<quantum-computing><factoring>
Continued Fraction Algorithm in Shor's Algorithm
Zach Dean
# Continued Fraction Algorithm in Shor's Algorithm

(Asked by: username_0 on 2015-03-20)

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?

**Tags:** quantum-computing, factoring


---

## 2 answers

### Answer by username_1 on 2015-03-21. Score: 7 | Accepted answer

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 by username_2 on 2020-07-07. Score: 3

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.


---

