Part IV · Advantage — 8d

Shor & the QFT

The algorithm that put quantum computing on the map — and on the radar of every cryptographer. Its secret is a swerve: don’t factor the number, find a hidden rhythm instead, and let the factors fall out.

↩ before you start · keep these handy
·From Ch. 8: Shor is the exponential speedup — and only one sub-step is quantum.
·From 0.2: a repeating signal has a frequency, and a Fourier transform is the tool that finds it.
·mod = the remainder after dividing; gcd = the largest number dividing two integers (Euclid's algorithm).
🔑 symbol decoder · every new mark, in plain words
Nthe number you want to factor (15 in the lab). aa chosen base sharing no factor with N — the seed of the rhythm. modthe remainder after dividing — e.g. 17 mod 15 = 2. rthe period: ax mod N repeats every r steps. QFTthe quantum Fourier transform — a frequency detector. gcdgreatest common divisor; turns the period r into the actual factors.
feel

Cracking a number by its rhythm

Pick a number you want to factor, say 15, and any companion a. Look at the sequence a¹, a², a³, … all taken mod 15. It always repeats — it has a period r. Finding that period is the hard part, and it’s the only part a quantum computer does. Once you know r, ordinary grade-school arithmetic turns it into the factors.

📻 everyday picture

Tuning a radio. You don't know the station's frequency, but you sweep the dial and the signal snaps into focus at one spot — the frequency reveals itself. Shor turns factoring into exactly this: the number hides a repeating rhythm, and the quantum Fourier transform is the dial that locks onto it in one sweep. Find the rhythm, and the factors fall out by plain arithmetic.

recapDon't factor directly — find the period r of ax mod N; that's the only quantum step.
play

Find the period, read the factors

Choose a base a. The strip shows ax mod 15 repeating; the spectrum below is what the quantum Fourier transform sees — evenly spaced spikes whose spacing hands you the period r. Then watch the two factors of 15 drop out of a single gcd.

▸ period finderN = 15
a =
ax mod 15  —  period repeats every r = {{ period }}
{{ c.val }}
{{ c.x }}
quantum Fourier transform  —  {{ period }} evenly-spaced peaks reveal the period
period  r = {{ period }}  ·  ar/2 mod 15 = {{ half }}
gcd({{ half }} − 1, 15) = {{ p }}  ·  gcd({{ half }} + 1, 15) = {{ q }}
15 = {{ p }} × {{ q }}  ✓
ar/2 ≡ −1 (mod 15) → only trivial factors. Pick another base and retry.
recapThe QFT turns the repeating sequence into evenly spaced peaks whose spacing gives the period r.
math

Period in, factors out

If r is even and ar/2 ≠ −1 (mod N), then ar/2 is a non-trivial square root of 1, and the factors come straight from Euclid’s gcd:

ar ≡ 1  ⇒  (ar/2−1)(ar/2+1) ≡ 0  (mod N)
factors = gcd(ar/2 − 1, N)  and  gcd(ar/2 + 1, N)

Only one step needs a quantum computer: finding r. The quantum Fourier transform takes the periodic superposition and concentrates it into sharp peaks spaced by M/r — so one measurement reveals the rhythm that a classical machine would need exponentially long to detect.

✎ worked example · factor 15 with base a = 7
1.7¹,7²,7³,7⁴ mod 15 = 7, 4, 13, 1 — repeats, so r = 4
2.r is even → ar/2 = 7² = 49 ≡ 4 (mod 15)
3.gcd(4−1, 15) = 3;  gcd(4+1, 15) = 5
4.15 = 3 × 5. ✓ — only step 1 needed a quantum computer.
recapAn even period with ar/2 ≠ −1 hands you the factors via two gcds; only finding r is quantum.
⚠ common misconception

“Shor tries all possible factors in parallel.” It never divides by trial factors at all. It reframes factoring as period-finding, and only the period hunt is quantum — the rest is multiplication and gcd you could do by hand. The QFT isn’t checking answers; it’s detecting a frequency.

This is the exponential one — the reason RSA encryption is built on the difficulty of factoring, and the reason a large enough quantum computer would undo it. Note the honest caveat the lab shows: sometimes a base gives a useless result and you simply pick another and retry. A handful of tries is still astronomically faster than classical factoring.

✓ you can now
✓explain why Shor finds a period instead of trying trial factors
✓turn a known period r into factors with ar/2 and two gcds
✓say what the QFT does (detect a frequency) and why this threatens RSA
← 8c Grover Search next · 09 Noise & Decoherence →