Editing Shor's algorithm (section)

==== Continued-fraction algorithm to retrieve the period ====
Then, we apply the [[continued fraction|continued-fraction]] algorithm to find integers <math>b</math> and <math>c</math>, where <math>b/c</math> gives the best fraction approximation for the approximation measured from the circuit, for <math>b, c < N</math> and [[Coprime integers|coprime]] <math>b</math> and <math>c</math>. The number of qubits in the first register, <math>2n</math>, which determines the accuracy of the approximation, guarantees that
<math display="block">
 \frac{b}{c} = \frac{j}{r},
</math>
given the best approximation from the superposition of <math>|\phi_j\rangle</math> was measured<ref name="siam"/> (which can be made arbitrarily likely by using extra bits and truncating the output). However, while <math>b</math> and <math>c</math> are coprime, it may be the case that <math>j</math> and <math>r</math> are not coprime. Because of that, <math>b</math> and <math>c</math> may have lost some factors that were in <math>j</math> and <math>r</math>. This can be remedied by rerunning the quantum order-finding subroutine an arbitrary number of times, to produce a list of fraction approximations
<math display="block">
 \frac{b_1}{c_1}, \frac{b_2}{c_2}, \ldots, \frac{b_s}{c_s},
</math>
where <math>s</math> is the number of times the subroutine was run. Each <math>c_k</math> will have different factors taken out of it because the circuit will (likely) have measured multiple different possible values of <math>j</math>. To recover the actual <math>r</math> value, we can take the [[least common multiple]] of each <math>c_k</math>:
<math display="block">
 \operatorname{lcm}(c_1, c_2, \ldots, c_s).
</math>
The least common multiple will be the order <math>r</math> of the original integer <math>a</math> with high probability. In practice, a single run of the quantum order-finding subroutine is in general enough if more advanced post-processing is used.<ref name="Ekerå24">{{cite journal |last1=Ekerå |first1=Martin |title=On the Success Probability of Quantum Order Finding |journal=ACM Transactions on Quantum Computing |date=May 2024 |volume=5 |issue=2 |pages=1–40 |doi=10.1145/3655026 |doi-access=free |arxiv=2201.07791 }}</ref>