FAC ∈ BQP (Shor)

Inclusion · quantum setting · Shor97

Statement

Factoring is in BQP: a quantum algorithm finds a nontrivial factor of an $n$-bit composite $N$ with constant success probability using $\tilde{O}(n^2)$ quantum gates with fast integer multiplication, or $\tilde{O}(n^3)$ with schoolbook arithmetic — Shor97.

Sketch

Factoring $N$ reduces classically to finding the multiplicative order $r$ of a random $a\in {\mathbb{Z}}_N^{\ast }$: for odd $N$ that is not a prime power, the other cases being handled classically, with probability at least $1/2$ the order $r$ is even, $a^{r/2}\not\equiv -1(\mathrm{mod}N)$, and $\gcd (a^{r/2}-1,N)$ is a nontrivial factor. The order is the period of $x\mapsto a^x\mathrm{mod}N$, which the quantum Fourier transform over ${\mathbb{Z}}_{2^m}$ with $2^m\approx N^2$ recovers through continued fractions — Shor97.

Notes

• The same period finding solves discrete logarithms, so factoring- and discrete-logarithm-based cryptography fall to a large quantum computer — Shor97.