Chapter 23 — Key Takeaways (Shor's Algorithm)
The one place an exponential speedup, a useful problem, and satisfiable conditions all coincide.
★ Most of it is classical
To factor $N$: pick random $a$, find the order $r$ with $a^r \equiv 1 \pmod N$. If $r$ is even and $a^{r/2}\not\equiv-1$:
$$\left(a^{r/2}-1\right)\left(a^{r/2}+1\right) = a^r - 1 \equiv 0 \pmod N \;\Longrightarrow\; \gcd\!\left(a^{r/2}\pm1,\,N\right)$$
The quantum computer's entire job is finding $r$.
a r a^(r/2) mod 15 factor note
2 4 4 3 ok
3 - - 3 lucky: gcd(a,N) > 1
7 4 4 3 ok
11 2 11 5 ok
14 2 14 None a^(r/2) = -1 mod N
Two failure modes, one free win: odd $r$ · $a^{r/2}\equiv-1$ · $\gcd(a,N)>1$ (Euclid hands you the answer, no quantum computer needed — always check first).
N usable a N usable a
15 6/7 (86%) 35 18/23 (78%)
21 6/11 (55%) 77 30/59 (51%)
33 10/19 (53%) 143 90/119 (76%)
At least half — the standard theorem for $N$ with ≥2 distinct odd prime factors.
Order finding = phase estimation
$$U_a|y\rangle = |ay \bmod N\rangle, \qquad \text{eigenvalues } e^{2\pi i s/r}$$
The period is in the denominator of the phase.
⚛️ You never prepare an eigenvector. The work register starts in $|1\rangle$, which is an equal superposition of all $r$ of them: $|1\rangle = \frac{1}{\sqrt r}\sum_s |u_s\rangle$. Phase estimation returns one phase at random — exactly what you want. This is Simon's algorithm over $\mathbb{Z}_N$, with continued fractions in place of Gaussian elimination.
★ Continued fractions
Fraction(s, 2**t).limit_denominator(N).denominator
s s/2^t convergent r found note
0 0.000000 0 1 useless
64 0.250000 1/4 4 correct
128 0.500000 1/2 2 a divisor -- often good enough
192 0.750000 3/4 4 correct
⚠️ Verify:
pow(a, r, N) == 1. One line, microseconds, and it turns a Monte Carlo algorithm into a Las Vegas one.
★ Factoring 15, end to end ($a = 7$, $t = 8$, 2048 shots)
bits s s/2^t convergent r count %
10000000 128 0.500000 1/2 2 526 25.7%
11000000 192 0.750000 3/4 4 524 25.6%
01000000 64 0.250000 1/4 4 520 25.4%
00000000 0 0.000000 0 1 478 23.3%
Exactly four outcomes near 25% — the values $s = k\cdot2^t/r$. Sharp because $k/4$ is dyadic (Ch. 22 §22.4).
period votes {4: 1044, 2: 526, 1: 478} -> r = 4, pow(7,4,15) = 1 ✓
7^2 mod 15 = 4; gcd(3,15) = 3, gcd(5,15) = 5 -> 15 = 3 x 5
Success rate depends on policy — and both are correct, since the factor is verified either way:
STRICT require pow(a,r,N)==1 first 1044/2048 = 51.0%
PERMISSIVE reduce on any candidate 1570/2048 = 76.7%
The gap is $s=128 \to r=2$, which fails the order check ($7^2\bmod15 = 4$) but still reduces: $\gcd(6,15)=3$. Discarding it costs 26 points for no benefit. Irreducible failures are $s=0$ (23.3%, roughly $1/r$).
★★ Randomized on two levels
Level 1 — the choice of $a$ (50–86% usable). Level 2 — the measurement ($s=0$ always wasted).
repeat:
a <- random; if gcd(a,N) > 1: return gcd(a,N) # free win
r <- QUANTUM ORDER FINDING # the only quantum step
if pow(a,r,N) != 1: continue # bad convergent
if r odd: continue
y <- pow(a, r//2, N); if y == N-1: continue
f <- gcd(y±1, N); if 1 < f < N: return f
Every failure is cheap to detect, and the returned answer is verified — multiply the factors.
★★ The QFT is a rounding error
n bits QFT gates mod-exp Toffolis ~0.3n³ ratio
64 2,016 78,643 39x
1024 523,776 322,122,547 615x
2048 2,096,128 2,576,980,377 1,229x
At 2048 bits the QFT is 0.08% of the circuit. Ch. 22's AQFT saves 82% of that 0.08% — i.e. 0.07%.
🔬 The AQFT still matters (it removes rotations no hardware can apply — feasibility, not count). But if you want Shor cheaper, every hour belongs in reversible modular arithmetic, which is why the serious literature is almost entirely about that.
The interesting part of an algorithm and the expensive part are frequently not the same part.
The full cost
RSA bits logical q T count physical qubits runtime
256 772 20,401,094 2,429,840 3.4 min
1024 3,092 1,309,965,025 11,168,726 4.2 hr
2048 6,189 10,496,900,071 24,937,084 1.5 days
Doubling the key ×8 the T count ($n^3$), ×2 the qubits ($3n$). The wall is time, not width.
★★★ Against the best classical algorithm
GNFS is sub-exponential: $\exp\big((64/9)^{1/3}(\ln N)^{1/3}(\ln\ln N)^{2/3}\big)$. Shor is polynomial.
RSA bits GNFS ~ 2^x Shor T ~ 2^x gap
256 46.7 24.3 22.4
1024 86.8 30.3 56.5
2048 116.9 33.3 83.6
$2^{117}$ against $2^{33}$. The gap to a working attack is HARDWARE — four to five orders of magnitude in qubit count — NOT ALGORITHMS.
🔬 What this means for cryptography
Shor BREAKS RSA, Diffie–Hellman, and ECC. Not weakens — breaks. No key-doubling defence exists, because the algorithm is polynomial in key length: doubling multiplies the attacker's work by 8.
The number has moved, and only downward — Gidney & Ekerå's figure was >1 order of magnitude below earlier estimates, entirely through better constructions.
And the deadline precedes the machine:
$$\text{migration deadline} = (\text{arrival}) - (\text{data confidentiality lifetime})$$
data must stay secret safe until (machine 2040) migrate by
5 years 2035 2035
20 years 2020 ALREADY PASSED
30 years 2010 LONG PASSED
Prioritize by data lifetime, not threat proximity. Use hybrid deployment to dissolve the maturity objection. Use AES-256 — Grover's key-halving is answered by doubling, and is a separate question.
Common pitfalls
- Believing "factored 15" means the hard part was implemented (it is a lookup table).
- Skipping
pow(a, r, N) == 1verification. - Discarding candidates that are divisors of the period.
- Assuming one $a$ suffices, or one shot.
- Optimizing the QFT to make Shor cheaper.
- Answering "when does the machine arrive" instead of "how long must this stay secret."
Project piece added this chapter
vqelab/shor.py — classical_reduction (returns the reason, which drives the retry),
brute_force_order, usable_base_fraction, period_candidates (several, in convergent order),
order_finding_circuit (raises for $N\neq15$ rather than pretending to generalize),
shor() with both randomization levels and a strict_order_check policy flag, and a FactorResult
with a verified property. 17 tests pass, including
test_reduction_fails_with_THE_RIGHT_REASON_at_a_equals_14,
test_at_least_half_of_bases_are_usable, and test_the_result_is_ALWAYS_verified.