Continued fractions with Shor's algorithm: which convergent?

Question

Suppose I am using Shor's order finding algorithm to calculate the order $r$ of $x\leq N$ with respect to $N$. After some run of the QPE subroutine, I obtain a good, $L$-bit approximation to $s/r$ for some $s\leq r$. According to, say, Nielsen and Chuang, because my estimation $\phi$ is sufficiently close, when I do the continued-fractions algorithm (CFA) on $\phi$, one of the convergents will be exactly $s/r$.

My question is, how will we know which convergent? It certainly isn't necessarily the last convergent, since this will be equal to the binary approximation $\phi$ and not $s/r$. Is there a guess-and-check stage that goes on here and if so, does efficiently of the algorithm depend on the number of convergents being small relative to $N$?

Edit: I should mention that I am also curious why the answer is what it is. Namely, if we are able to make a specific choice of convergent, what mathematical argument allows us to do so?

Answer 1

Following excellent answers from Danylo Y and Reinhard, and more follow up discussion with the latter, I would like to provide my own answer that uses only basic properties of continued fractions, which can be found on Wikipedia.

Theorem: Let $\varphi \in [0,1)$ be a rational number, and let $N>1$ be an integer. Suppose $s/r$ is a positive rational such that $r<N$, and $$ \left\vert\varphi - \frac{s}{r}\right\vert < \frac{1}{2N^2}. $$ then $s/r$ is a convergent in the continued fraction expansion of $\varphi$. Moreover, $s/r$ is the unique rational satisfying the above inequality amongst all rationals with denominator $q < N$.

Proof: See Nielsen and Chuang for a proof that $s/r$ exists. We only demonstrate uniqueness. Suppose $p/q$ is another fraction which satisfies the inequality of Theorem 1. Then, by the triangle inequality, it is necessarily the case that $$ \begin{aligned} \left\vert\frac{s}{r}-\frac{p}{q}\right\vert &< \frac{1}{N^2} \\ \frac{\vert sq-rp\vert}{rq} &< \frac{1}{N^2} \\ \vert sq-rp\vert &< \frac{rq}{N^2} < 1. \end{aligned} $$ Since the left side is a nonnegative integer, we must have that it equals zero. Hence $$ sq = rp $$ which implies that the fractions are, in fact, equal. $$\tag*{$\blacksquare$}$$ Remark: We note that this result implies that $s/r$ is a best approximant to $\varphi$ amongst all fractions with denominator bounded by $N$. Hence, it can be found in python with fraction.limit_denominator(N) as Craig Gidney mentioned.

Corollary: In the notation of the Theorem, let $h_j/k_j$ represent the $j$th convergent of $\varphi$ for $j = 0, 1, \dots, n-1$ in reduced form. Then $s/r = h_i/k_i$, where $i$ is the largest index such that $k_j \geq N$ for all $j > i$.

Proof: We rely on the known fact that the sequence $\{k_j\}$ is monotonically increasing (see wikipedia or Nielsen and Chuang). As a special case, if $\varphi = s/r$, then $s/r$ is the last convergent, and all $k_j$ are bounded by $N$. Hence, $i = n-1$ and the statement holds vacuously in this case.

More generally, suppose $\varphi \neq s/r$. By the Theorem, $s/r = h_i/k_i$, and since $\varphi \neq s/r$ this cannot be the last convergent. Also by the Theorem, this is the unique convergent that satisfies the properties of (a) the inequality and (b) denominator $k_i < N$. Consider all subsequent convergents: $j > i$. Then, using the fact that convergents get increasingly (and monotonically) close to $\varphi$ (see wikipedia), these convergents satisfy (a). Therefore, by uniqueness, they cannot satisfy (b). Hence, $k_j \geq N$ for all such $j$.

However, by assumption we have $r < N$, hence $k_i < N$. We conclude that $i$ is the largest index for which the denominator is strictly bounded by $N$. This completes the proof. $$\tag*{$\blacksquare$}$$

The essential result is that, in Shor's order finding algorithm, we don't have to try all convergents. The last convergent with denominator smaller than $N$ is guaranteed to be $s/r$, where $r<N$ is the order.

Answer 2

I also stumbled upon this question few weeks ago. Of course one can always try all convergents since there are not that many (the denominators grow exponentially fast), but we know already that exactly one of them equals $s/r$ (if phase estimation ran successfully). Of course it can happen that $s$ has a common factor with $r$ but how to deal with this is discussed in the book - so we do not care here. So it is an interesting question to ask which one it is.

In fact, it really is the last convergent with a denominator smaller than $N$.

I gave a proof here. But I will repeat it in this answer.

Let us recall that we not only know that $r<N$ we also know that $\varphi$ is approximated up to $2L+1$ bits (with probability at least $1-\varepsilon$) according to the book (not just $L$ bits). This shows:

$$ \left|\frac{s}{r} - \varphi\right| \leq \frac{1}{2N^2}, $$

since $N$ is an $L$ bit number. Note that this information is lost in Theorem 5.1 of the book. The claim now directly follows from this little Lemma:

Let $s < r < N$ be non-negative integers and $\varphi\in[0,1)$ real. Assume

$$ \left|\varphi - \frac{s}{r}\right| < \frac{1}{2 N^2} . $$

Then $s/r$ is a convergent of $\varphi$ and the next convergent has a denominator which is larger than $N$.

PROOF: The book already showed that $s/r$ is a convergent of $\varphi$. Let us focus on the claim that it is the last one. Let us write $s/r=p_n/q_n$ with coprime nominator and denominator. Furthermore assume that $\varphi=[a_0,\ldots,a_n,z_{n+1}]$ where $z_{n+1}$ is allowed to be /real/ number (and at least $1$).

It can be shown (see e.g. here), that

$$ \varphi - \frac{p_n}{q_n} = \frac{(-1)^{n+1}}{q_n(z_{n+1}q_n+q_{n-1})} . $$

In fact this follows from the better known formula (see e.g. wikipedia):

$$ \varphi = \frac{z_{n+1}p_n + p_{n-1}}{z_{n+1}q_n + q_{n-1}} . $$

Also recall the well known recursion formulas:

$$\begin{align*} p_{n+1} &= a_{n+1}p_n + p_{n-1} , \\ q_{n+1} &= a_{n+1}q_n + q_{n-1} , \\ z_{n+1} &= (z_n - \lfloor z_n \rfloor)^{-1} \end{align*}$$

Hence:

$$ q_n (q_{n+1} + q_n/z_{n+2}) = q_n (z_{n+1} q_n + q_{n-1}) \geq 2 N^2 . $$

Since $q_n < N$, $q_n < q_{n+1}$, and $z_i\geq 1$ we deduce $q_{n+1}>N$. QED.

This should answer the question. But let me give some final note on fraction.limit_denominator(N). In general this does not return a convergent. Instead it returns a so called best approximation (see the python documentation), that is, a fraction so that no other fraction with smaller denominator better approximates the target. Convergents are best approximations but not the other way around (For example $1/2$ is a best approximation of $5/7$ but no convergent).

But this does not imply that one cannot use fraction.limit_denominator(N) to find $s/r$. A lemma like the above but with convergents replaced by best approximations might be true. I didn't look into that. But I also suspect that to efficiently compute best approximations one has to first calculate convergents anyway.

Answer 3

You use the last one whose denominator is less than $N$, the number you're trying to factor. The value returned by fraction.limit_denominator(N) in python.

If you're still particularly worried about it, there's nothing really stopping you from trying all of them.

Answer 4

This is actually a good question that most texts don't bother to explain.

I don't see a reason why we should pick the largest possible convergent, that is, $p_k/q_k$ such that $q_k < N$ but $q_{k+1} \ge N$.

If we know absolutely nothing about $r$, except $r < N$, then we know nothing about $s/r$ as well. Thus, the first convergent $p_1/q_1$ is no less preferable option than the largest.

For example, if $s/r = 7/13$, then $20$-bit approximation $\phi$ will be equal to $\lfloor 7/13 \cdot 2^{20} \rfloor / 2^{20}$. It has continued fraction form $[0; 1, 1, 6, 7332, 1, 1, 5]$.

While $7/13 = [0; 1, 1, 6]$, next convergents are clearly leading you away.

So that, the correct way is to check all convergents. But this is not really a problem, since the probability that $s/r$ is irreducible is $\varphi(r)/r$, which is quite high. With this probability some $q_k$ equals $r$. We just need to check it.