Editing Shor's algorithm (section)

==== Choosing the size of the first register ====
Phase estimation requires choosing the size of the first register to determine the accuracy of the algorithm, and for the quantum subroutine of Shor's algorithm, <math>2n</math> qubits is sufficient to guarantee that the optimal bitstring measured from phase estimation (meaning the <math>|k\rangle</math> where <math display="inline">k / 2^{2n}</math> is the most accurate approximation of the phase from phase estimation) will allow the actual value of <math>r</math> to be recovered.

Each <math>|\phi_j\rangle</math> before measurement in Shor's algorithm represents a superposition of integers approximating <math>2^{2 n} j/r</math>. Let <math>|k\rangle</math> represent the most optimal integer in <math>|\phi_j\rangle</math>. The following theorem guarantees that the continued fractions algorithm will recover <math>j/r</math> from <math>k/2^{2 {n}}</math>:
{{Math theorem
| math_statement = If <math>j</math> and <math>r</math> are <math>n</math> bit integers, and
<math display="block">\left\vert \frac{j}{r} - \phi\right\vert \leq \frac{1}{2 r^2}</math>
then the continued fractions algorithm run on <math>\phi</math> will recover both <math display="inline">\frac{j}{\gcd(j,\; r)}</math> and <math display="inline">\frac{r}{\gcd(j,\; r)}</math>.
}}
<ref name=":0" /> As <math>k</math> is the optimal bitstring from phase estimation, <math>k/2^{2 {n}}</math> is accurate to <math>j/r</math> by <math>2n</math> bits. Thus,<math display="block">\left\vert\frac{j}{r} - \frac{k}{2^{2n}}\right\vert \leq \frac{1}{2^{2 {n} + 1}} \leq \frac{1}{2N^2} \leq \frac{1}{2r^2}</math>which implies that the continued fractions algorithm will recover <math>j</math> and <math>r</math> (or with their greatest common divisor taken out).