6
$\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$
1
$\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 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$ – Craig Gidney Mar 24 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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