The Period-Finding Subroutine

The previous lesson showed that factoring reduces to finding the period of the function $f(x) = a^x \bmod N$ for a randomly chosen base $a$. This lesson walks through the quantum circuit that computes that period exponentially faster than any known classical algorithm.

The period-finding problem

Fix integers $a$ and $N$ with $\gcd(a, N) = 1$. The function $f(x) = a^x \bmod N$ is periodic: there exists a smallest positive integer $r$ — the order of $a$ modulo $N$ — such that

$a^r \equiv 1 \pmod{N}, \quad \text{hence} \quad f(x + r) = f(x) \text{ for all } x.$

Classically, finding $r$ requires sub-exponential time: the best-known algorithms (based on the number-field sieve) run in $\exp\!\bigl(O((\log N)^{1/3}(\log\log N)^{2/3})\bigr)$, which is super-polynomial in the bit-length $n = \log_2 N$. Shor's quantum subroutine reduces this to $O((\log N)^3)$ elementary quantum gates — an exponential advantage over all known classical approaches.

Register sizes

The circuit uses two registers:

• Input register: $n$ qubits, where $n = \lceil \log_2 N^2 \rceil$ (enough to hold at least $N^2$ distinct values). For $N = 15$, $n = 8$ qubits suffice since $15^2 = 225 \leq 256 = 2^8$.
• Output (ancilla) register: $\lceil \log_2 N \rceil$ qubits to store values of $f(x)$.

Together the combined state lives in a $2^n \times N$-dimensional Hilbert space, but we only use $O(\log N)$ qubits per register — a resource that grows polynomially with the size of the number being factored.

The circuit, step by step

Step 1 — Superpose all inputs

Apply $H^{\otimes n}$ to the input register, which starts in $|0\rangle^{\otimes n}$:

$H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n - 1} |x\rangle.$

All $2^n$ candidate exponents now exist simultaneously in superposition. The output register remains $|0\rangle$.

Step 2 — Apply the modular-exponentiation oracle

A unitary $U_f$ maps $|x\rangle|0\rangle \mapsto |x\rangle|a^x \bmod N\rangle$. After this step the full state is

$\frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-1} |x\rangle |a^x \bmod N\rangle.$

The function values are entangled with their inputs — neither register has a well-defined value on its own.

Step 3 — Measure the output register

Measuring $|a^x \bmod N\rangle$ collapses the output register to some particular value $v = a^{x_0} \bmod N$. Because $f$ is periodic with period $r$, the surviving terms in the input register are exactly those $x$ values where $a^x \equiv v \pmod{N}$. These form the arithmetic progression $x_0, x_0 + r, x_0 + 2r, \ldots$ The post-measurement input register state is

$\frac{1}{\sqrt{M}} \sum_{k=0}^{M-1} |x_0 + kr\rangle,$

where $M \approx 2^n / r$ is the number of surviving terms.

This is a uniform superposition of equally-spaced integers — a signal with a well-defined frequency $1/r$ encoded in the amplitudes.

Step 4 — Inverse QFT on the input register

The Quantum Fourier Transform (QFT) is the quantum analogue of the discrete Fourier transform. Its inverse maps the equally-spaced superposition into a superposition of integer multiples of $2^n / r$:

$\text{QFT}^\dagger \left(\frac{1}{\sqrt{M}} \sum_{k=0}^{M-1} |x_0 + kr\rangle\right) \approx \frac{1}{\sqrt{r}} \sum_{j=0}^{r-1} e^{2\pi i x_0 j / r}\, \left|\frac{j \cdot 2^n}{r}\right\rangle.$

Each term in this sum carries a phase $e^{2\pi i x_0 j/r}$ and points to the integer $j \cdot 2^n / r$. The amplitudes concentrate at multiples of $2^n/r$.

Step 5 — Measure the input register

Measuring the input register after the inverse QFT yields one of the values $j \cdot 2^n / r$ with high probability. Dividing by $2^n$ gives an approximation to the rational $j/r$. Classical continued-fraction expansion (the topic of the next lesson) then extracts the denominator $r$ from this approximation.

Circuit diagram

Measure the bottom line and apply continued fractions to recover $r$.

Why the QFT finds the period

Recall that a classical DFT of a sequence with period $r$ in a window of size $Q = 2^n$ has large coefficients at the frequencies $j/r$ for $j = 0, 1, \ldots, r-1$. The QFT does the same thing quantumly: it maps amplitude patterns with period $r$ to states that are localized near integer multiples of $Q/r$. A single measurement then samples one of those frequencies — the analogy to reading off one peak in a classical Fourier spectrum.

The probability that a single measurement yields a "useful" outcome (one from which $r$ can be recovered) is $\Omega(1/\log \log r)$, so a constant number of repetitions suffice.

Putting it together

The complete subroutine costs $O(n^3)$ quantum gates: $O(n)$ for the initial Hadamards, $O(n^3)$ for $U_f$, and $O(n^2)$ for the inverse QFT (which dominates $H^{\otimes n}$ but not $U_f$). This contrasts with the best classical approach to order-finding, which runs in $\exp\!\bigl(O(n^{1/3}(\log n)^{2/3})\bigr)$ time — super-polynomial in $n = \log_2 N$.

The next lesson builds the inverse QFT explicitly and shows how it extracts a rational approximation from the measured value, completing the final bridge from quantum measurement to factored prime.

Sign in on the full site to ask questions and join the discussion.