Quantum Cookbook

Part V · Chapter 31 · Final chapter of Part V

Shor's Algorithm

Read ~24 min Prerequisites Ch. 23, Ch. 29–30 Tools full factoring pipeline widget, code cell Live
Basic

This is the algorithm that made quantum computing famous outside physics departments: a way to factor large numbers exponentially faster than any known classical method — fast enough to break the RSA encryption protecting most of the internet, if a large enough quantum computer ever runs it. Every piece you need is already built. This chapter is purely assembly.

The classical reduction: factoring becomes order-finding

Shor's real insight wasn't quantum at all — it was noticing that factoring N reduces to a different problem: pick some a coprime to N, and find its order r, the smallest positive integer with aʳ ≡ 1 (mod N). Once you have an even r, simple classical arithmetic (Euclid's gcd algorithm) almost always hands you a real factor of N:

gcd(a^(r/2) − 1, N) and gcd(a^(r/2) + 1, N)

The only quantum step in the entire algorithm is finding r quickly. That's it. Everything else — the reduction above, and the final gcd computation — runs on an ordinary classical computer.

Intermediate

Finding the order, quantum-mechanically

Define the unitary U|x⟩ = |ax mod N⟩. Its eigenvalues are exactly e^(2πis/r) for integers s — which means Ch. 30's quantum phase estimation, applied to U, estimates s/r directly. A classical algorithm called continued fractions then recovers r from that fraction. This is the entire quantum contribution: QPE turns "find r by trial division" (exponentially slow) into "estimate a phase" (efficient).

Fig. 31.1 — the whole algorithm, end to endquantum step in the middle, classical on both ends
pick a, check gcd(a,N)=1 QPE on U|x⟩=|ax mod N⟩ (quantum step) continued fractions → r classical classical (gcd step happens after, too)
The quantum computer is doing exactly one thing in this whole pipeline: estimating a phase. Everything else is classical arithmetic you could run by hand for small enough numbers — which Fig. 31.2 actually does.
Fig. 31.2 — the complete pipeline, livepick N and a, watch every step

The bar chart is the literal sequence aˣ mod N — watch it repeat every r steps (blue bars mark each repeat point). The QPE line runs an actual phase estimation independently and recovers the same r a completely different way, as a cross-check.
Advanced

Why this is exponentially faster than anything classical

The best known classical factoring algorithm (the general number field sieve) takes time that grows roughly exponentially in the number of digits of N. Shor's algorithm's quantum step — QPE on modular exponentiation — takes time that grows only polynomially. For small numbers like 15, this difference is invisible; a laptop factors 15 instantly either way. For numbers with hundreds of digits — exactly the size used in real RSA encryption — the classical approach becomes intractable while Shor's algorithm, run on a sufficiently large and reliable quantum computer, would not. That gap, not the specific number 15, is the actual reason this algorithm matters: it's the single clearest example known of a quantum algorithm solving a practically important problem exponentially faster than any classical alternative.

Building a quantum computer with enough reliable qubits to factor a cryptographically meaningful number remains a hard, unsolved engineering problem — which is exactly the kind of noise and error this book's Part II (density matrices, damping channels) and the broader field of quantum error correction exist to fight.

Fig. 31.3 — code, runs in your browser
The classical half of Shor's algorithm, in full — pair this with Fig. 30.2's QPE code from the previous chapter and you have every piece of the real algorithm, minus only the controlled modular-exponentiation circuit itself.

End of Part V

Quantum parallelism, oracles, and phase kickback (Ch. 22–23) built the foundation; Deutsch, Deutsch–Jozsa, and Bernstein–Vazirani (Ch. 25–27) showed the pattern at its simplest; Grover (Ch. 28) showed a different kind of speedup entirely; the QFT and phase estimation (Ch. 29–30) built the machinery this chapter just spent its entire length putting to use. There's no algorithm left in this book bigger than the one you just finished.

Check your understanding

What classical problem does factoring N reduce to?

Finding the order r of some a coprime to N — the smallest r with aʳ ≡ 1 (mod N).

Check your understanding

What is the only genuinely quantum step in Shor's algorithm?

Quantum phase estimation applied to the unitary U|x⟩=|ax mod N⟩, used to find the order r. The reduction to order-finding and the final gcd computation are both classical.

Check your understanding

For N=15, a=7, the order is r=4. What two factors does the gcd step recover?

3 and 5 — gcd(7²−1, 15)=3 and gcd(7²+1, 15)=5, and indeed 15=3×5.

Check your understanding

Why does Shor's algorithm fail (need a retry with a different a) if r turns out to be odd?

Because the factor-recovery step needs to compute a^(r/2), which requires r to be even. An odd r can't be halved into a meaningful integer exponent, so the algorithm restarts with a different choice of a.

Check your understanding

Why is Shor's algorithm considered a much bigger deal than, say, factoring 15 would suggest?

Because the speedup is exponential — the gap between classical and quantum factoring time grows enormously as N gets larger, to the point of being intractable classically but efficient quantumly for RSA-sized numbers. The small examples in this chapter demonstrate the mechanism; the real-world stakes only appear at scale.

Review queue

Scroll back to a chapter's quiz cards to review them once they're due — a full cross-chapter queue view is a planned upgrade.