Shor's algorithm

Shor's factoring algorithm uses quantum period finding to determine a modular order and then extracts factors classically with greatest common divisors.

After continued-fraction recovery in quantum order finding, an even candidate denominator $q$ can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and $N$. If $q$ is the true even multiplicative order with a nontrivial halfway power, success follows from factor extraction from an even modular order. A candidate that is not a period can occasionally still yield a factor; testing $a^q\equiv 1$ before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.

If $r$ is even, $a^r\equiv 1(\mathrm{mod}N)$, and $a^{r/2}\not\equiv -1(\mathrm{mod}N)$, then $\gcd (a^{r/2}-1,N)$ is a nontrivial factor unless the order was not minimal.

For an odd integer $N$ having at least two distinct prime divisors, choose a uniform unit $a\mathrm{mod}N$. The Chinese remainder theorem for unit groups makes its odd-prime-power components independent cyclic groups. Failure of factor extraction from an even modular order requires all components to have equal 2-primary order exponents. For any component each possible exponent has probability at most $1/2$, so conditioning on another component bounds failure by $1/2$. Excluding the identity unit only improves the success proportion.

Quantum order finding Fourier-transforms a superposition of arguments having the same modular-exponentiation value, producing peaks near multiples of the reciprocal period.

For $\gcd (x,n)=1$ and order $r$, multiplication by $x$ modulo $n$ is a unitary operator. On the orbit of one it cyclically permutes $r$ basis states. The displayed orthonormal eigenstates have eigenvalues $e^{2\pi is/r}$, and $|1⟩=r^{-1/2}{\sum }_s|u_s⟩$. Thus quantum phase estimation on this efficiently prepared state samples a uniform $s$ without knowing $r$. Controlled powers are implemented by quantum modular exponentiation. Sufficient phase resolution allows continued-fraction recovery in quantum order finding; the reduced denominator equals $r$ only when $s$ is coprime to $r$.

In quantum order finding, a phase $s/r$ produces amplitude $Q^{-1}{\sum }_{x=0}^{Q-1}{e}^{2\pi ix(s/r-j/Q)}$ after an inverse quantum Fourier transform. Its nearest grid point has probability at least $4/{\pi }^2$, by bounding the sine ratio of this finite geometric Fourier amplitude. The initial modular orbit state is an equal-weight superposition of the $r$ phase eigenstates, so the phase label is uniform.

Quantum modular exponentiation is the reversible computation that mapsIt can be implemented in polynomial time in the bit lengths of $x$ and $N$ by repeated squaring and controlled modular multiplication.

The Fourier amplitude of equally spaced basis states is a finite geometric sum with peaks where the Fourier phase increment is nearly one.

For $A$ terms with phase ratio $q$, the amplitude factor is $(1-q^A)/(1-q)$, with limiting value $A$ when $q=1$.

If a measured ratio approximates a reduced $k/r$ within $1/(2r^2)$, continued-fraction convergents recover the candidate denominator $r$.

Two distinct reduced fractions with denominators below $N$ differ by more than $1/N^2$, so an interval of radius $1/(2N^2)$ contains at most one.