8
$\begingroup$

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?

$\endgroup$

4 Answers 4

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Exactly what I was looking/hoping for. Thanks! Clearly there's a lot of depth to the topic of continued fractions. $\endgroup$
    – Jacob
    Apr 16 at 13:28
  • $\begingroup$ I am also curious about this last point. Perhaps it would be well-suited for the mathematics stack exchange. My question is, how many fractions $p/q$ with denominator $q<N$ satisfy the inequality in your lemma? Probably multiple, and here we might find a counterexample. $\endgroup$
    – Jacob
    Apr 16 at 13:54
  • $\begingroup$ Update: fraction.limit_denominator should work. I believe any best approximation satisfying the assumptions of your lemma is unique. Existence is given by Theorem 5.1. $\endgroup$
    – Jacob
    Apr 16 at 14:22
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you @Craig. I guess I am also curious why that is the case, but I did not make this explicit in my question. I will make an edit to reflect this. $\endgroup$
    – Jacob
    Mar 24, 2021 at 15:39
  • $\begingroup$ @Jacob Well, I suppose I'm not sure how you would do better than that number as the guess. That being said, it's certainly not guaranteed to be correct. For example, instead of finding k it may find k/2 or k/3. It's not so unlikely that a factor of the period gets dropped. A common optimization is to check if multiples of the found denominator are periods, or to compute the lcm of multiple found denominators to significantly decrease the chance of missing factors of the period. $\endgroup$ Mar 24, 2021 at 16:22
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks @Danylo, I appreciate the validation :) I will point out that your 7/13 example is not a counterexample, since $7332 > 13$. It looks like Reinhard's answer may shed the light we seek. $\endgroup$
    – Jacob
    Apr 16 at 12:50
  • 1
    $\begingroup$ @Jacob I assumed $N > 13$ and quite big. But $N$ can't be bigger than $2^{10}$ since we took only 20-bit approximation in the example. So, it seems Reinhard is right. $\endgroup$
    – Danylo Y
    Apr 16 at 14:49
  • $\begingroup$ I see my misunderstanding now, thanks for clarifying! $\endgroup$
    – Jacob
    Apr 16 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.