How superposition and interference reveal hidden periodicity in modular arithmetic
Given integers $a$ and $N$ with $\gcd(a, N) = 1$, consider the function:
This function is periodic. The order (or period) $r$ is the smallest positive integer such that:
Equivalently, $f(x+r) = f(x)$ for all $x \geq 0$. Finding $r$ efficiently is the key to factoring $N$.
If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then at least one of $\gcd(a^{r/2} - 1,\; N)$ or $\gcd(a^{r/2} + 1,\; N)$ is a non-trivial factor of $N$.
Classically, finding the period $r$ of $a^x \bmod N$ by brute force requires up to $r$ evaluations — and $r$ can be nearly as large as $N$ itself. The best classical algorithms for the underlying factoring problem are sub-exponential but still super-polynomial in the number of digits:
| Algorithm | Complexity | Type |
|---|---|---|
| Trial division | $O(\sqrt{N})$ | Exponential in bit-length |
| Pollard's rho | $O(N^{1/4})$ | Exponential in bit-length |
| General Number Field Sieve | $O\!\left(e^{c(\ln N)^{1/3}(\ln\ln N)^{2/3}}\right)$ | Sub-exponential |
| Shor's algorithm (quantum) | $O\!\left((\log N)^3\right)$ | Polynomial |
The quantum speedup comes from two ingredients:
The period-finding algorithm uses two quantum registers and four stages:
Walk through the circuit step-by-step for the example $N = 15$, $a = 7$ (period $r = 4$) with 4 counting qubits:
After all the controlled operations, the full state is $\frac{1}{4}\sum_{x=0}^{15}|x\rangle|7^x \bmod 15\rangle$. Each counting register value $|x\rangle$ is paired with a specific work register value $|f(x)\rangle$. If we group the terms by their work register value, something remarkable appears — each group forms a periodic pattern in $x$ with the same period $r = 4$:
Each bar is one term $|x\rangle|f(x)\rangle$ in the superposition, colored by the work register value $f(x) = 7^x \bmod 15$:
Now imagine measuring the work register. The state collapses to only those $|x\rangle$ values that share the same $f(x)$ — a periodic subset with period $r$. Click a button to see what happens:
The Quantum Fourier Transform maps a computational basis state $|j\rangle$ to:
The key insight: if the input state is periodic with period $r$, then the QFT output has amplitudes concentrated at multiples of $Q/r$ — and nearly zero everywhere else. Let's see exactly why this happens.
After the modular exponentiation, the counting register holds a periodic superposition — equal amplitudes at evenly-spaced positions $x_0,\; x_0 + r,\; x_0 + 2r,\; \ldots$:
where $m \approx Q/r$ is the number of terms. Applying the QFT, the amplitude at output $|k\rangle$ is:
Since $|\omega^{x_0 k}| = 1$, the probability $|\alpha_k|^2 = |S(k)|^2 / (Qm)$ depends only on the sum $S(k)$. Each term in this sum is a unit-length phasor (a complex number on the unit circle) with angle $\varphi_j = 2\pi j \cdot rk/Q$. Consecutive phasors differ by a fixed phase step:
When $k$ is a multiple of $Q/r$, the phase step $\Delta\varphi$ is a multiple of $2\pi$. Every phasor points in the same direction. They add up: $|S(k)| = m$, giving probability $\approx 1/r$.
When $k$ is NOT a multiple of $Q/r$, the phasors spread around the unit circle and cancel each other out. The geometric series gives $|S(k)| \approx 0$. The more terms (larger $m$), the more complete the cancellation.
Explore this visually — drag the slider to change $k$ and watch the phasors align or cancel:
Each entry $(\text{QFT})_{jk} = \frac{1}{\sqrt{Q}}\,\omega^{jk}$. The color encodes the phase of $\omega^{jk}$:
Choose an input state and observe how the QFT transforms it. Periodic inputs produce sharp peaks in the output:
Choose $N$ and $a$ to run the full quantum period-finding algorithm. Observe how the measurement probabilities cluster around multiples of $Q/r$, allowing us to extract $r$.
After measuring the counting register and obtaining outcome $y$ from a register of size $Q = 2^n$, we need to extract the period $r$. The key idea: the measured $y$ satisfies:
for some integer $s$ with $0 \leq s < r$. We use the continued fractions algorithm to find the best rational approximation $s/r$ from the decimal $y/Q$.
Any real number $\alpha$ can be written as $\alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}}$, denoted $[a_0; a_1, a_2, \ldots]$. The convergents $p_k/q_k$ are the best rational approximations with denominator $\leq q_k$.
The quantum period-finding algorithm combines quantum parallelism, entanglement, and Fourier analysis into a single coherent pipeline:
| Stage | What Happens |
|---|---|
| 1 Superposition | Hadamard gates create $\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}|x\rangle|0\rangle$ |
| 2 Entanglement | Controlled-$U_f$ maps to $\frac{1}{\sqrt{Q}}\sum_{x}|x\rangle|a^x \bmod N\rangle$ |
| 3 Interference | QFT$^{-1}$ concentrates amplitudes at multiples of $Q/r$ |
| 4 Measurement | Yields $y \approx sQ/r$ with high probability |
| 5 Post-processing | Continued fractions extract $r$ from $y/Q$ |
| 6 Factoring | $\gcd(a^{r/2} \pm 1, N)$ yields non-trivial factors |
Run the complete Shor's algorithm pipeline end-to-end. Pick a number $N$ to factor, and watch each stage unfold — from choosing a random base $a$ through quantum period finding to extracting the factors:
You now understand how quantum period finding works — from superposition and modular exponentiation through QFT interference and continued fractions. In the next module, we put all the pieces together into Shor's complete factoring algorithm, including error handling, success probability analysis, and what it means for real-world cryptography.
Continue to Shor's AlgorithmTest your understanding of quantum period finding. Select the best answer for each question.