> "Everything else in this book is a technique. This is the reason anyone is funding the field."
Prerequisites
- 15
- 19
- 20
- 21
- 22
Learning Objectives
- Reduce factoring to order finding and implement the classical half.
- Build the order-finding circuit as phase estimation on modular multiplication.
- Recover the period from a measured phase using continued fractions.
- Account for both levels of randomization and the resulting retry structure.
- Identify where the algorithm's cost actually lies.
- State honestly what breaks, when, and what to do about it.
In This Chapter
Chapter 23: Shor's Algorithm
"Everything else in this book is a technique. This is the reason anyone is funding the field."
Overview
Shor's algorithm factors integers in polynomial time. It is the one place in this book where an exponential speedup, a genuinely useful problem, and a satisfiable set of conditions all coincide — and where none of the previous chapters' caveats apply.
Chapter 21's Grover was quadratic. Chapter 22's QFT was fast and unreadable. Chapter 20's algorithms solved problems constructed to be solvable. Shor breaks RSA.
The comparison against the best classical algorithm:
RSA bits GNFS ~ 2^x, x = Shor T count ~ 2^x, x =
256 46.7 24.3
1024 86.8 30.3
2048 116.9 33.3
At 2048 bits: roughly $2^{117}$ classical operations against $2^{33}$ quantum T gates. The classical figure is beyond anything that will ever be built; the quantum figure is ten billion T gates, which Chapter 15 priced at 24.9 million physical qubits and 1.5 days.
The gap is hardware, not algorithms, and that is a completely different situation from every other chapter in Part IV.
Structurally it is Chapter 20's Simon's algorithm over $\mathbb{Z}_N$ instead of $(\mathbb{Z}_2)^n$, with Chapter 22's phase estimation replacing the Hadamard layer and continued fractions replacing Gaussian elimination. The shape is identical: a quantum subroutine produces a constraint, and classical post-processing turns constraints into answers.
And it works. Factoring 15 with $a = 7$, measured:
bits s s/2^t convergent r count
01000000 64 0.250000 1/4 4 520
10000000 128 0.500000 1/2 2 526
11000000 192 0.750000 3/4 4 524
00000000 0 0.000000 0 1 478
period r = 4 -> gcd(7^2 - 1, 15) = 3 -> 15 = 3 x 5
In this chapter, you will learn to:
- Reduce factoring to order finding, and implement the classical half.
- Build the order-finding circuit.
- Recover the period with continued fractions.
- Handle two levels of randomization.
- Locate the algorithm's real cost.
- State what this means for cryptography, carefully.
Learning Paths
How to read this chapter by track. - 🔰 Beginner — §23.1 and §23.5. The classical reduction is most of the algorithm and needs no quantum mechanics. - 🔬 Researcher — §23.6 and §23.7; where the cost is, and how the estimates have moved. - 🤖 Quantum ML — skim; the structural lesson in §23.8 is the transferable part. - 🏗️ Quantum Engineer — §23.6. Modular exponentiation is 99.92% of the circuit. - 🔐 Security — all of it, then Chapter 38.
23.1 Factoring Is Not the Quantum Part
The single most useful thing to understand about Shor's algorithm: most of it is classical, and the quantum part solves a different problem.
The reduction. To factor $N$, pick a random $a$ coprime to $N$ and find the order $r$ — the smallest positive integer with
$$a^r \equiv 1 \pmod N$$
If $r$ is even and $a^{r/2} \not\equiv -1 \pmod N$, then
$$\left(a^{r/2}-1\right)\left(a^{r/2}+1\right) = a^r - 1 \equiv 0 \pmod N$$
so $N$ divides that product without dividing either factor, and
$$\gcd\!\left(a^{r/2} \pm 1,\; N\right)$$
gives a non-trivial factor. Everything above is elementary number theory. The quantum computer's entire job is finding $r$.
Worked for $N = 15$, over every $a$:
a r a^(r/2) mod 15 factor note
2 4 4 3 ok
3 - - 3 lucky: gcd(a,N) > 1
4 2 4 3 ok
7 4 4 3 ok
8 4 4 3 ok
11 2 11 5 ok
13 4 4 3 ok
14 2 14 None a^(r/2) = -1 mod N
Two failure modes and one free win.
gcd(a, N) > 1 — you picked an $a$ sharing a factor with $N$, and Euclid hands you the answer
with no quantum computer at all. Rare for large $N$, and always checked first.
$a^{r/2} \equiv -1$ — the reduction collapses, as at $a = 14$. Pick a different $a$.
Odd $r$ — same response.
How often does a random $a$ work?
N usable a
15 6/7 (86%)
21 6/11 (55%)
33 10/19 (53%)
35 18/23 (78%)
77 30/59 (51%)
143 90/119 (76%)
At least half, which is the standard theorem for $N$ with at least two distinct odd prime factors. A handful of attempts suffices, and each is cheap to check.
23.1.1 Which Assumption Actually Does the Work
The reduction is three lines of algebra, and it is worth knowing which line is load-bearing, because that is what the retry loop is testing.
Let $r$ be the order of $a$ and suppose $r$ is even. Put $x = a^{r/2}$. Then
$$x^2 = a^r \equiv 1 \pmod N \quad\Longrightarrow\quad N \mid (x-1)(x+1)$$
$\gcd(x-1, N)$ is a non-trivial factor exactly when $N$ divides the product but neither factor separately. Two things must therefore hold, and they are not symmetric.
$N \nmid (x-1)$ is free. That condition says $a^{r/2}\not\equiv 1 \pmod N$ — which is precisely the statement that $r/2$ is not the order of $a$. It cannot be, because $r$ is the smallest exponent with $a^r \equiv 1$. The minimality in the definition of "order" is doing the work here, and it is why the quantum subroutine has to return the order rather than any exponent that happens to satisfy $a^k \equiv 1$.
$N \nmid (x+1)$ is not free. That condition says $a^{r/2}\not\equiv -1 \pmod N$, and nothing forbids it. It is the second failure mode, it must be tested, and $a = 14$, $N = 15$ is where it fires.
The asymmetry is visible in the code, and it is a good sanity check on any implementation:
if y == N - 1: # tested -- can happen
return None, "a^(r/2) = -1 mod N"
# y == 1 is never tested, because minimality of r forbids it
An implementation that tests y == 1 is being defensive about a bug somewhere else. The check is
not useless — but if it ever fires, the problem is upstream in the period recovery, not in the
reduction.
Why $r$ must be even is now immediate: with $r$ odd there is no integer $r/2$, so there is no square root of 1 to split. There is nothing to salvage; you draw a new $a$.
And once both conditions hold, $N$'s prime factors are distributed across $x-1$ and $x+1$ with at least one on each side. $\gcd(x-1,N)$ collects the ones on its side — a proper divisor, strictly between 1 and $N$. The entire payoff of the quantum computation is delivered by a Euclid step.
23.1.2 The Table Is the Chinese Remainder Theorem
§23.1's table looks like seven independent facts about 15. It is two facts about 3 and 5.
$$\mathbb{Z}_{15}^{*} \;\cong\; \mathbb{Z}_{3}^{*} \times \mathbb{Z}_{5}^{*}, \qquad a \mapsto (a \bmod 3,\; a \bmod 5)$$
Under this isomorphism $a^k \equiv 1 \pmod{15}$ holds exactly when it holds modulo 3 and modulo 5 separately, so
$$r = \operatorname{lcm}\!\big(\operatorname{ord}_3(a),\; \operatorname{ord}_5(a)\big)$$
Every row of §23.1's table falls out of the two component orders:
a a mod 3 a mod 5 ord_3 ord_5 lcm r mod 15
2 2 2 2 4 4 4
4 1 4 1 2 2 2
7 1 2 1 4 4 4
8 2 3 2 4 4 4
11 2 1 2 1 2 2
13 1 3 1 4 4 4
14 2 4 2 2 2 2
Seven rows reproduced from a group with two elements and a group with four.
The failure condition becomes readable in the same terms. $a^{r/2}\equiv -1 \pmod{15}$ requires $a^{r/2}\equiv-1$ modulo 3 and modulo 5 at once. Writing $v_2(\cdot)$ for the number of factors of two in an integer, that happens exactly when the two component orders carry the same power of two:
a v2(ord_3) v2(ord_5) equal? reduction fails?
2 1 2 no no
4 0 1 no no
7 0 2 no no
8 1 2 no no
11 1 0 no no
13 0 2 no no
14 1 1 YES YES
One row satisfies the condition, and it is the one row that fails. The reduction does not collapse for a mysterious reason at $a = 14$. It collapses because the period's factor of two arrives from both primes simultaneously, so $a^{r/2}$ lands on $-1$ in both coordinates at once.
📐 Math Aside — where "at least half" comes from, and why RSA moduli sit exactly on the bound.
Let $N = p_1^{e_1}\cdots p_k^{e_k}$ with $k$ distinct odd primes, and draw $a$ uniformly from $\mathbb{Z}_N^{*}$. By the Chinese remainder theorem that is $k$ independent uniform draws $a_i$, one per prime power, and each $\mathbb{Z}_{p_i^{e_i}}^{*}$ is cyclic of even order.
Write $d_i = v_2(\operatorname{ord}(a_i))$. Then $v_2(r) = \max_i d_i$, and §23.1.1's two failure modes collapse into a single statement:
- $r$ is odd $\iff$ every $d_i = 0$;
- $a^{r/2}\equiv-1 \pmod N \iff$ every $d_i$ equals $v_2(r)$, and is non-zero.
So the reduction fails if and only if all $k$ values $d_i$ are equal. In a cyclic group of even order, no single value of $d_i$ is taken with probability more than $1/2$, so
$$\Pr[\text{all } d_i \text{ equal}] = \sum_{j}\prod_{i=1}^{k}\Pr[d_i = j] > \;\le\; \left(\tfrac12\right)^{k-1}\sum_j \Pr[d_1 = j] \;=\; 2^{\,1-k}$$
At $k = 2$ that is $1/2$ — the theorem §23.1 quotes.
And $k = 2$ is the worst case, which is exactly what an RSA modulus is. $N = pq$ has two distinct odd primes and sits precisely at the bound. §23.1's table shows how tight it is: $N = 77 = 7\times11$ came in at 51% and $N = 33 = 3\times11$ at 53%.
Adding a prime factor makes the reduction easier, and the effect is measurable:
text N factorization k bound usable a measured 15 3 x 5 2 50% 6/7 86% 77 7 x 11 2 50% 30/59 51% 105 3 x 5 x 7 3 75% 42/47 89% 165 3 x 5 x 11 3 75% 70/79 89% 1155 3 x 5 x 7 x 11 4 88% 450/479 94%Every measurement clears its bound, and the semiprimes are the ones that clear it narrowly. A small, cheerful piece of bad news: the integers cryptography actually uses are the integers where the classical half of Shor's algorithm needs the most retries — and "the most" is still under two attempts in expectation (§23.5.1).
23.2 Order Finding Is Phase Estimation
Now the quantum part. Define the unitary
$$U_a|y\rangle = |ay \bmod N\rangle$$
Its eigenvectors have eigenvalues $e^{2\pi i s/r}$ for $s = 0, 1, \dots, r-1$ — the period appears in the denominator of the phase. So estimating the phase estimates the period, and Chapter 22 §22.4 already built that machinery.
The circuit is exactly phase estimation:
1. SUPERPOSE H on t counting qubits
2. KICK BACK controlled-U_a^(2^j) from counting qubit j
= controlled MODULAR EXPONENTIATION
3. INTERFERE inverse QFT on the counting register
Stage 2 is the whole engineering problem, and §23.6 shows it is 99.92% of the circuit at cryptographic sizes.
⚛️ The Physics Underneath — you do not need to prepare an eigenvector.
Phase estimation as Chapter 22 presented it assumes you can prepare an eigenvector of $U$. Here you cannot — the eigenvectors of $U_a$ depend on $r$, which is what you are trying to find.
The trick is that you do not have to. The work register is initialized to $|1\rangle$, which is an equal superposition of all $r$ eigenvectors:
$$|1\rangle = \frac{1}{\sqrt r}\sum_{s=0}^{r-1}|u_s\rangle$$
Phase estimation on a superposition of eigenvectors returns one of their phases, chosen at random — which is exactly what you want, and why §23.4's measurement outcomes are uniformly spread over $s/r$.
This is Chapter 20's Simon's algorithm again. There, each measurement gave a random $y$ with $y \cdot s = 0$; here, each gives a random $s/r$. Both are constraints, both are sampled uniformly, and both need classical post-processing to combine.
23.2.1 The Eigenvectors, Written Out
The callout above asserts that $|1\rangle$ is an equal superposition of all $r$ eigenvectors. Here is the construction, because it is four lines and because every feature of §23.4's measured distribution comes out of it.
For $s = 0, 1, \dots, r-1$ define
$$|u_s\rangle = \frac{1}{\sqrt r}\sum_{k=0}^{r-1} e^{-2\pi i s k/r}\,\big|a^k \bmod N\big\rangle$$
$U_a$ relabels each basis state $|a^k\rangle \mapsto |a^{k+1}\rangle$, and the labels are cyclic because $a^r \equiv a^0 \equiv 1$. Reindex with $k' = k+1$:
$$U_a|u_s\rangle = \frac{1}{\sqrt r}\sum_{k'} e^{-2\pi i s(k'-1)/r}\big|a^{k'}\big\rangle = e^{2\pi i s/r}\,|u_s\rangle$$
Eigenvalue $e^{2\pi i s/r}$, with the period in the denominator, exactly as claimed.
Now sum them:
$$\frac{1}{\sqrt r}\sum_{s=0}^{r-1}|u_s\rangle = \frac1r\sum_{k=0}^{r-1}\left(\sum_{s=0}^{r-1}e^{-2\pi i s k/r}\right)\big|a^k\big\rangle$$
The inner sum is a geometric series in $e^{-2\pi i k/r}$: it equals $r$ when $k = 0$ and zero for every other $k$. What survives is $|a^0\rangle = |1\rangle$.
Three consequences, each visible in §23.4's table:
One X gate prepares the state. qc.x(t) sets the work register to $|1\rangle$. No knowledge of
$r$, no state preparation, no ancillas — which is why Chapter 22's "you must be able to prepare an
eigenvector" precondition evaporates here rather than being satisfied.
The measurement returns a uniformly random $s$. All $r$ eigenvectors enter with the same amplitude $1/\sqrt r$, so each phase $s/r$ comes back with probability exactly $1/r$.
$s = 0$ is one of the eigenvectors, not a defect. Its eigenvalue is $e^0 = 1$ and its phase is $0/r$, which carries no information about $r$ at all. It arrives $1/r$ of the time by construction and no implementation choice can suppress it. §23.4's 478 counts are that eigenvector, and §23.5's "level 2" randomization is exactly this fact.
23.2.2 Controlled-$U^{2^j}$ Does Not Cost $2^j$ Multiplications
Stage 2 applies controlled-$U_a^{2^j}$ from counting qubit $j$. Read literally that is $2^j$ multiplications, and summed over $j$ it is $2^t - 1$ of them — exponential in the width of the counting register, which would sink the algorithm on its own.
It is not, for one reason:
$$U_a^{2^j} = U_{\,a^{2^j} \bmod N}$$
Multiplying by $a$, $2^j$ times, is multiplying by $a^{2^j}\bmod N$ once — and $a^{2^j}\bmod N$ is a classical constant, obtained by $j$ modular squarings on the laptop driving the experiment.
So the circuit performs $t$ controlled modular multiplications by $t$ different, classically precomputed constants. That single substitution is the difference between exponential and polynomial, and it is where "modular exponentiation" gets its name: the exponentiation happens on the classical side.
The cost chain follows immediately, and it is the origin of §23.6's $n^3$:
t = 2n counting qubits (section 23.3.2)
x n controlled modular additions per multiplication
x O(n) Toffolis per modular addition
= O(n^3) Toffolis
⚙️ Under the Transpiler — the demonstration circuit does the exponential thing anyway.
§23.4's helper contains
for _ in range(power). It applies the permutation $2^j$ times rather than exponentiating the constant, because for $N=15$ the constants are not available as a general construction — only as the hand-built table Case Study 1 dissects.Measured, $a = 7$, $t = 8$:
```text j power = 2^j gates in the block 0 1 7 1 2 14 2 4 28 3 8 56 4 16 112 5 32 224 6 64 448 7 128 896
total repetitions of the multiply-by-7 permutation: 255 ( = 2^8 - 1 )```
Transpiled to Aer's basis, the 12-qubit circuit is depth 3,297, size 3,368:
text ccx 2,295 cx 1,020 cp 28 h 16 x 1 measure 8The 28
cpgates are the entire inverse QFT — $t(t-1)/2 = 28$, which is exactly the $n = 8$ row of §23.6's table. Everything else is multiplication. The QFT is 0.8% of the transpiled instruction count, measured directly and in miniature; §23.6's 0.08% at 2048 bits is the same statement at scale.At
optimization_level=3into a[cx, u]basis it becomes 13,316 CX gates at depth 24,032. The transpiler does not collapse the 255 repetitions: they sit inside a controlled custom gate that it decomposes rather than analyses, and the permutation's period-4 structure is invisible to it.Two thousand two hundred and ninety-five Toffolis to factor 15, in a circuit whose expensive component was replaced by a lookup table. That number measures how the demonstration was written, not what the algorithm costs.
23.3 Continued Fractions
The measurement gives an integer $s$, and $s/2^t \approx k/r$ for some unknown $k$. You need $r$ from a noisy approximation to a fraction whose denominator you want.
That is exactly what continued fractions do — the convergents of $s/2^t$ include $k/r$ whenever $t$ is large enough, and Python has it built in:
Fraction(s, 2**t).limit_denominator(N).denominator
Worked, $N = 15$, true period $r = 4$, $t = 8$:
s s/2^t convergent r found
0 0.000000 0 1 <- useless
64 0.250000 1/4 4 <- correct
128 0.500000 1/2 2 <- a divisor
192 0.750000 3/4 4 <- correct
Three of four outcomes are usable, and the fourth ($s = 0$) is always possible and always useless.
Note $s = 128$ gives $r = 2$ rather than 4 — a divisor of the true period. That still works here: $\gcd(7^1 - 1, 15) = \gcd(6, 15) = 3$. A divisor of the period is often good enough, which is why the practical success rate exceeds what a naive analysis predicts.
23.3.1 The Expansions, by Hand
limit_denominator hides a three-line algorithm. The continued-fraction expansion of $s/2^t$ is the
Euclidean algorithm on the pair $(s,\,2^t)$, and for these four outcomes it terminates in two or three
steps.
Take $s = 192$:
192 / 256 = 0 remainder 192 a0 = 0
256 / 192 = 1 remainder 64 a1 = 1
192 / 64 = 3 remainder 0 a2 = 3
[0; 1, 3] convergents 0, 1, 3/4
All four measured outcomes, expanded:
s s / 2^t expansion convergents denominator
0 0 / 256 [0] 0 1
64 64 / 256 [0; 4] 0, 1/4 4
128 128 / 256 [0; 2] 0, 1/2 2
192 192 / 256 [0; 1, 3] 0, 1, 3/4 4
Two or three terms each. Continued fractions is not a heavy post-processing step; it is Euclid on two $t$-bit integers, and it costs microseconds at any $t$ you will ever run.
Compare the structural sibling. Chapter 20's Simon's algorithm post-processes by Gaussian elimination, and it cannot produce anything until it has collected $n-1$ independent constraints — every measurement is a partial result. Continued fractions works on a single measurement, which is why §23.5.1's retry loop can extract a candidate period from every distinct outcome in one job rather than having to accumulate a system of equations first.
Note what limit_denominator(N) returns: the last convergent whose denominator is at most $N$, not
the list of them. That is the right default and it is not always the right answer, which is why
vqelab's period_candidates walks the convergents in order and returns several. On this table it
makes no difference. At larger $N$, where the phase is not exact, it does.
23.3.2 How Many Counting Qubits
Two theorems meet at $t$, and together they fix the shape of the whole circuit.
Continued fractions. If $|x - k/r| < 1/(2r^2)$ with $\gcd(k,r) = 1$, then $k/r$ appears among the convergents of $x$. That is a classical theorem about rational approximation and has nothing to do with quantum mechanics.
Phase estimation (Chapter 22 §22.4). With $t$ counting qubits, the most likely outcome $s$ satisfies $|s/2^t - \varphi| \le 2^{-(t+1)}$.
Set $\varphi = k/r$ and demand that the second guarantee imply the first's hypothesis:
$$\frac{1}{2^{\,t+1}} < \frac{1}{2r^{2}} \qquad\Longleftrightarrow\qquad 2^{\,t} > r^{2}$$
Since $r < N$, choosing $2^{t} \ge N^{2}$ suffices — that is, $t = 2n$ counting qubits for an $n$-bit modulus.
N n = ceil(log2 N) t = 2n 2^t N^2 guaranteed
15 4 8 256 225 yes
21 5 10 1,024 441 yes
143 8 16 65,536 20,449 yes
That is where §23.2.2's $t = 2n$ came from, and why the counting register is twice the width of the work register in every resource estimate in this chapter.
📊 What the Numbers Say — $t = 8$ is not what makes §23.4 work.
The rule above is sufficient, not necessary. Sweeping $t$ downward on the same problem — $N = 15$, $a = 7$, 2048 shots at each setting:
text t 2^t 2^t > r^2 ? outcomes r=4 r=2 r=1 usable 2 4 no 4 1,050 520 478 76.7% 3 8 no 4 1,044 526 478 76.7% 4 16 no 4 1,044 526 478 76.7% 5 32 yes 4 1,044 526 478 76.7% 6 64 yes 4 1,044 526 478 76.7% 8 256 yes 4 1,044 526 478 76.7%Two counting qubits give exactly the same answer as eight. $N = 15$ is the case where the bound is furthest from necessary: $r = 4$ is a power of two, so $k/4$ is exactly representable in two bits and phase estimation is exact at $t = 2$ (Chapter 22 §22.4). The other six qubits resolve a phase with nothing left to resolve.
The circuits are not the same size:
text t = 2 6 qubits depth 40 size 48 ccx 27 t = 8 12 qubits depth 3,297 size 3,368 ccx 2,295A factor of 82 in depth and 70 in size, for an identical distribution. Quote the 12-qubit figure as "the cost of factoring 15" and you are quoting six idle qubits and 2,268 unnecessary Toffolis.
This does not generalize, and that is the part worth carrying: at an $r$ that is not a power of two the peaks spread, the exactness disappears, and $t$ starts to matter in exactly the way the derivation says. §23.4's four sharp peaks are a property of 15.
⚠️ Common Pitfall — verify the period before using it.
Continued fractions returns a candidate. Checking it is one line:
python if pow(a, r, N) != 1: # not the order -- try the next convergent, or measure againThis costs microseconds and is the difference between a correct algorithm and an unreliable one. Shor's is randomized; the classical verification is what makes it certain, and skipping it turns a Las Vegas algorithm into a Monte Carlo one for no benefit.
⚠️ Common Pitfall — the printed idiom silently stops working at 54 bits.
Fraction(s / 2**t)builds aFractionfrom a float. A Python float carries a 53-bit significand, so every bit of $s$ below the 53rd is discarded beforelimit_denominatorever sees it. At $t = 8$ that loses nothing. At a real modulus, §23.3.2's rule puts $t = 2n$ in the thousands.Measured — feed a perfect measurement $s = \lfloor 3\cdot 2^{t}/r\rfloor$ with $t = 2n$ and $r = 2^{\,n-1}-1$, and ask each form to recover $r$:
text n bits in r r float form recovers ok 48 47 140,737,488,355,327 140,737,488,355,327 yes 52 51 2,251,799,813,685,247 2,251,799,813,685,247 yes 54 53 9,007,199,254,740,991 15,011,998,757,901,651 NO 56 55 36,028,797,018,963,967 36,028,797,018,963,968 NO 64 63 9,223,372,036,854,775,807 9,223,372,036,854,775,808 NOThe crossover is exactly 53 bits, as the derivation says it must be. At $n = 54$ the answer is not close — it is a different integer. At $n = 56$ and above it is off by one, which is worse in practice:
pow(a, r, N) != 1rejects it, the caller concludes the measurement was bad, and the loop re-runs the most expensive circuit in computing forever.The fix is the two-argument constructor:
python Fraction(s, 2**t).limit_denominator(N).denominator # exact at any tSame speed, no float in the path, correct at every row of the table above. No measurement in this chapter changes — at $N = 15$ the two forms agree exactly, which is precisely why the bug would survive every test in
vqelab's suite and first appear on the first modulus that was not a toy.
23.4 Factoring 15, End to End
$a = 7$, $t = 8$ counting qubits, 2048 shots:
bits s s/2^t convergent r count
10000000 128 0.500000 1/2 2 526
11000000 192 0.750000 3/4 4 524
01000000 64 0.250000 1/4 4 520
00000000 0 0.000000 0 1 478
Exactly four outcomes, each near 25% — the values $s = k\cdot 2^t/r$ for $k = 0,1,2,3$ with $r = 4$. Phase estimation is exact here because $k/4$ is dyadic (Chapter 22 §22.4), so the distribution is four sharp peaks rather than a spread.
period votes: {4: 1044, 2: 526, 1: 478}
most common r = 4 (the true order of 7 mod 15)
verification: pow(7, 4, 15) = 1 confirmed
a^(r/2) mod N = 7^2 mod 15 = 4
gcd(4 - 1, 15) = 3 gcd(4 + 1, 15) = 5
15 = 3 x 5
23.4.1 Why 25%, Exactly — and What the Wobble Is
The four peaks are not approximately 25%. They are exactly $1/4$, and the derivation says so before any shots are taken.
§23.2.1 established that the work register is an equal superposition of all $r$ eigenvectors, so phase estimation runs on phase $\varphi = s/r$ with probability $1/r$ for each $s$. Here $r = 4$ and $t = 8$:
$$\varphi = \frac{s}{4} = \frac{64\,s}{256} = \frac{64\,s}{2^{t}}$$
Each phase is an exact $t$-bit binary fraction. Chapter 22 §22.4 measured that phase estimation on a dyadic phase is exact — the inverse QFT returns that basis state with amplitude 1 and every other with amplitude 0. So
$$\Pr\big[\text{outcome } 64s\big] = \frac1r = \frac14, \qquad s = 0,1,2,3$$
and each of the other 252 outcomes has probability exactly zero. Four outcomes, 25.000% each, no tail.
Against that prediction, the measurement:
bits count expected deviation z
10000000 526 512 +14 +0.71
11000000 524 512 +12 +0.61
01000000 520 512 +8 +0.41
00000000 478 512 -34 -1.74
with $\sigma = \sqrt{2048 \times 0.25 \times 0.75} = 19.60$. All four sit inside two standard errors, and the 95% interval for a single outcome at these settings runs from 474 to 550.
📊 What the Numbers Say — every headline percentage in this section is a derivable constant.
§23.4 reports the $s = 0$ outcome at 23.3% and calls it "roughly $1/r$". The derivation says it is exactly $1/r = 25\%$, and 478/2048 is one draw sitting 1.74 standard errors low.
The same is true of both policy rates below, which are not empirical either:
text policy outcomes it accepts exact rate measured STRICT s = 64, 192 (r = 4) 2/4 = 50.0% 51.0% z = +0.88 PERMISSIVE everything but s = 0 3/4 = 75.0% 76.7% z = +1.74 the gap s = 128 (r = 2) 1/4 = 25.0% 25.7%The permissive rate is exactly $1 - 1/r$. The strict rate is exactly the fraction of outcomes whose leading convergent is the true order. The gap is exactly one outcome out of four. And the two $z$ values are not independent — the permissive deviation is the $s=0$ deviation with its sign flipped, because they are complements of the same count.
Nothing distinguishes $s = 0$ from the other three. Reading $478 < 520 < 524 < 526$ as an ordering is reading noise: the full spread is 2.4 standard errors, about what four draws from one distribution look like.
This is the book's most-repeated finding arriving in the one chapter that did not need it — a result from one or two samples is a draw from a distribution. Here the correction is not more shots. It is noticing that the exact answer was already available from §23.2.1 and that the shots are only confirming it.
The per-shot success rate depends on how strict you are, and the difference is instructive:
STRICT require pow(a,r,N)==1, then reduce 1044/2048 = 51.0%
PERMISSIVE reduce on any candidate, verify the factor 1570/2048 = 76.7%
Both are correct, because the final factor is checked either way — $f$ divides $N$ or it does not.
The gap is entirely the $s = 128$ outcome, which gives $r = 2$. That fails the order check ($7^2 \bmod 15 = 4$, not 1), so the strict policy discards it — but the reduction still lands: $\gcd(7^1 - 1, 15) = \gcd(6, 15) = 3$. $r = 2$ is a divisor of the true period, and a divisor is often good enough for the gcd to hit.
Discarding it costs 26 percentage points for no benefit. The irreducible failures are the $s = 0$ outcomes — 23.3% here, and roughly $1/r$ of shots in general.
23.4.2 The Same Circuit on a Device That Is Not a Simulator
Every number above came from a noiseless simulator. The circuit is 3,368 instructions and 2,295 Toffolis (§23.2.2), which is a great deal of exposure for a result that depends on four amplitudes interfering to exactly the right places.
📉 Noise Report — the peaks are the first thing to go, and the success rate is the last to notice.
Running the same circuit under a uniform depolarizing model, 4,096 shots at each error rate:
text 2q depol distinct outcomes P(0) P(64) P(128) P(192) 4 peaks usable 0 4 0.2476 0.2498 0.2520 0.2507 1.0000 75.2% 1e-05 38 0.2366 0.2473 0.2529 0.2441 0.9810 75.5% 1e-04 119 0.2109 0.2197 0.2227 0.2114 0.8647 71.8% 1e-03 233 0.0735 0.0811 0.0769 0.0696 0.3010 53.3% 7.5e-03 256 0.0127 0.0156 0.0127 0.0095 0.0505 30.6%The bottom row's error rate is the low end of Chapter 30's measured spread of quoted two-qubit errors on a single chip — 0.00750 to 0.07205. At that rate all 256 outcomes appear and the four peaks hold 5% of the shots, against 1.6% for a uniform distribution over 256 outcomes. The signal is a factor of three above nothing.
And now the column that matters. "Usable" still reads 30.6%, which sounds like a third of a working algorithm. It is not:
text a uniformly random s in 0..255, run through the classical reduction: 63/256 = 24.6%A random 8-bit string factors 15 nearly a quarter of the time, because $N = 15$ is small enough that many wrong periods still land on a good gcd. The metric has a floor at 24.6% that has nothing to do with the circuit. The measured 30.6% is statistically above that floor — about nine standard errors at 4,096 shots — and it is practically uninformative, because it would still read 24.6% for a circuit that had been replaced by a random number generator.
This is the book's other recurring failure, in a chapter that could easily have avoided it: a measurement that cannot detect the thing being asked about. The column that can detect it is
4 peaks, which runs 1.0000 → 0.0505 across the same range. Quote the peak mass, not the success rate.🔬 Honest Assessment — two measurements that sharpen Case Study 1.
Case Study 1 argues that factoring 15 with a hand-built permutation demonstrates phase estimation and says nothing about modular exponentiation — 99.92% of a real circuit. Two of this chapter's measurements sharpen the point.
The demonstration's modular exponentiation is exponential in $t$. §23.2.2 measured 255 repetitions of the multiply-by-7 permutation across the eight blocks, because the code repeats the multiplication rather than exponentiating the constant. The one substitution that makes Shor's algorithm polynomial is the substitution the demonstration does not perform.
And six of the eight counting qubits are unnecessary. §23.3.2 measured $t = 2$ producing the identical distribution at depth 40 instead of 3,297. The 12-qubit circuit is not the smallest circuit that factors 15; it is about seventy times larger than it.
Neither observation is a criticism of the demonstration, which is doing its job — validating the phase estimation, the continued fractions and the reduction, none of which can be checked by inspection and all of which would break if the surrounding logic were wrong. Both are constraints on what the numbers from it can be used for. "Twelve qubits factored 15" is a sentence about a teaching implementation, not about the difficulty of factoring 15.
The test that settles these claims is Case Study 1's: would the circuit still work if the answer were unknown? Here, no —
controlled_mult_mod_15is a table indexed by the six valid values of $a$, written by someone who had already computed the orders.
23.5 Two Levels of Randomization
Shor's algorithm is randomized twice, and implementations often handle only one.
Level 1 — the choice of $a$. Roughly 50–86% of coprime $a$ lead to a factor (§23.1). Failure means odd $r$ or $a^{r/2} \equiv -1$; the response is to pick another $a$.
Level 2 — the measurement. Even with a good $a$, the outcome $s = 0$ is always possible and always useless, and other outcomes may give a divisor of $r$ rather than $r$ itself. Roughly $1/r$ of shots are wasted at best.
The correct structure is a loop with classical verification at every stage:
repeat:
a <- random in [2, N-1]
if gcd(a, N) > 1: return gcd(a, N) # free win
r <- quantum order finding
if pow(a, r, N) != 1: continue # bad convergent
if r is odd: continue # level-1 failure
y <- pow(a, r//2, N)
if y == N-1: continue # level-1 failure
f <- gcd(y-1, N) or gcd(y+1, N)
if 1 < f < N: return f
Every failure is cheap to detect and the expected number of iterations is small. That is what makes Shor's a Las Vegas algorithm: it may take a variable number of attempts, and when it returns an answer the answer is verified correct — you multiply the factors and check.
23.5.1 "Small" Is Two, and Level 2 Never Fires
"The expected number of iterations is small" deserves a number, because it is the entire argument that a Las Vegas algorithm is practical.
Level 1 is a geometric random variable. With success probability $p$ per choice of $a$, the expected number of $a$ values is $1/p$ and the probability of ten consecutive failures is $(1-p)^{10}$. At §23.1's measured rates:
N usable a p E[# of a] P(fail after 10 a)
15 6/7 0.8571 1.167 3.54e-09
21 6/11 0.5455 1.833 3.77e-04
33 10/19 0.5263 1.900 5.69e-04
35 18/23 0.7826 1.278 2.36e-07
77 30/59 0.5085 1.967 8.23e-04
143 90/119 0.7563 1.322 7.39e-07
bound 1/2 0.5000 2.000 9.77e-04
Two attempts in expectation, worst case, and max_attempts=10 holds the failure probability below
one in a thousand even at the theoretical bound. That is why vqelab.shor defaults to 10 and needs no
smarter policy.
Level 2 is not a geometric random variable, because a shot is not an attempt. Each circuit execution returns hundreds of shots and every distinct outcome is an independent constraint. The probability that a 512-shot job contains no usable outcome at all is $0.233^{512}$ — below $10^{-323}$ under the permissive policy, and $10^{-159}$ under the strict one.
So level 2 contributes nothing to the retry count — provided the loop actually reads more than one outcome. The chapter's implementation does:
for bits in ordered: # every distinct outcome, most frequent first
for r in period_candidates(int(bits, 2), t, N): # several convergents from each
An implementation that takes only the most-frequent outcome, and only its first convergent, throws away almost everything it paid for and converts a level-2 non-event into a re-run of the most expensive part of the algorithm. This is the most common structural bug in hand-rolled implementations of Shor, and it is invisible at $N = 15$ because there are only four outcomes and three of them work.
🧪 Run It — three experiments, each of which moves a number in this chapter.
1. Flip the policy and count attempts, not successes. Run
shor(15, strict_order_check=True)againstFalse. §23.4.1 derives the per-shot rates as exactly 1/2 and 3/4, so both should succeed on the first $a$ essentially always — the interesting output isFactorResult.attempts, notsucceeded. If the strict run ever needs a second $a$, your shot count is too low, and the arithmetic above says by how much.2. Test the $2^{1-k}$ bound above $k = 2$.
usable_base_fraction(105)— $105 = 3\times5\times7$ has three distinct odd primes, so §23.1.2's Math Aside predicts at least 75% usable against the semiprimes' 50%. Then $165 = 3\times5\times11$, then $1155 = 3\times5\times7\times11$. The measurements clear the bound comfortably; what is worth seeing is that the integers cryptography uses are the ones nearest to it.3. Cripple
period_candidatesand watch nothing happen. Set itslimitto 1 at $N = 15$ and the success rate will not move, because the leading convergent is right for all four outcomes. That is the trap. The guard that matters is the one your example cannot exercise — which is Chapter 27's argument for testing against a property rather than against a fixture.🧱 Project Checkpoint —
vqelab/shor.py: the whole loop, not just the circuit.
classical_reduction(N, a, r)implements §23.1, returning the factor and the reason when it fails —"odd period","a^(r/2) = -1 mod N","trivial factors"— because the reasons are what drive the retry.
order_finding_circuit(a, N, t)builds the phase-estimation circuit, andperiod_from_measurement(s, t, N)does the continued-fraction step, returning candidate denominators in convergent order so a caller can try more than the first.
shor(N, max_attempts)runs the full loop with verification at every stage, returning aFactorResultcarrying the factors, the $a$ values tried, the failure reason for each, and the shot count — so a run that took six attempts is distinguishable from one that took one.
usable_base_fraction(N)brute-forces §23.1's table for small $N$, which is how you check an implementation's retry rate is what theory predicts rather than what a bug produces.Its tests assert: 15 and 21 factor correctly; the reduction fails with the right reason at $a = 14, N = 15$; the usable-$a$ fraction is at least 50% for several $N$; continued fractions recovers $r = 4$ from $s = 64$ and $s = 192$; an unverified period is rejected; and the returned factors multiply back to $N$.
23.6 Where the Cost Actually Is
Chapter 22 spent a chapter on the QFT. In Shor's algorithm the QFT is a rounding error.
Modular exponentiation is $\mathcal{O}(n^3)$; the QFT is $\mathcal{O}(n^2)$:
n bits QFT gates mod-exp Toffolis ~ 0.3n³ ratio
8 28 153 5x
64 2,016 78,643 39x
256 32,640 5,033,164 154x
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.
🔬 Honest Assessment — optimizing the QFT is optimizing the wrong thing.
Chapter 22 §22.5 measured that the approximate QFT saves 82% of the QFT's gates at $n = 64$. In Shor at 2048 bits, saving 82% of 0.08% of the circuit is 0.07%.
The AQFT still matters, for a different reason: it removes rotations too small for any hardware to apply, so it is about feasibility rather than count. But if you want to make Shor's algorithm cheaper, every hour belongs in modular exponentiation — which is why the serious literature on Shor is almost entirely about reversible modular arithmetic.
This is a general lesson about profiling, arriving in an unusual setting: the interesting part of an algorithm and the expensive part are frequently not the same part.
The full picture, using Chapter 15's estimator:
RSA bits logical q T count physical qubits runtime
15 45 4,076 211,740 24.7 ms
128 385 2,545,942 1,341,446 23.4 s
256 772 20,401,094 2,429,840 3.4 min
512 1,545 163,477,192 5,069,814 29.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 length multiplies the T count by about 8 ($n^3$) while the qubit count only doubles ($3n$). The wall is time, not width.
23.6.1 Reproducing the Headline Numbers
The two figures this chapter rests on — 10.5 billion T gates and 24.9 million physical qubits — come out of a resource model two lines long. Knowing the two lines tells you what the estimate is hostage to.
$$\text{Toffolis} = 0.3\,n^3 + 0.0005\,n^3\log_2 n, \qquad \text{logical qubits} = 3n + 0.002\,n\log_2 n$$
The leading terms are §23.2.2's cost chain — $2n$ controlled multiplications, $n$ modular additions each, $\mathcal{O}(n)$ Toffolis per addition — and $3n$ is the counting register ($2n$, from §23.3.2) plus the work register ($n$). The logarithmic corrections model the adders' carry structure.
📐 Math Aside — the arithmetic in full, at $n = 2048$.
```text 0.3 n^3 2,576,980,377.6 0.0005 n^3 log2 n 47,244,640.3
Toffoli count 2,624,225,017.9
T count = 4 x Toffoli 10,496,900,071 <- section 23.6's table log2(T count) 33.3 <- section 23.7's table logical qubits = 3n + 0.002 n log2 n 6,189 <- section 23.6's table ```
Both headline figures fall out of two lines of arithmetic, which is worth knowing because it tells you which assumptions they depend on.
The
4is a modelling choice. Four T gates per Toffoli is the measurement-assisted construction, which spends a measurement and a classically-controlled correction to save T gates. The textbook Clifford+T decomposition of a Toffoli uses seven. At seven:
text T count = 7 x Toffoli 18,369,575,124 ( x1.75 )A factor of 1.75 on the headline number, from one line of the model — and it changes nothing about §23.7's conclusion, because $1.75 = 2^{0.8}$ and the comparison there is $2^{33}$ against $2^{117}$. That is the useful property of an exponential separation: the constants stop deciding the answer. Chapter 21's Grover has no such margin — a factor of 1.75 on a quadratic speedup's overhead is most of the speedup.
The $0.3$ is also a choice, and a more consequential one, because it multiplies $n^3$. It encodes a particular reversible modular multiplier. Halving it halves both the T count and the runtime — and Case Study 2's observation applies exactly here: the estimate has only ever moved downward, because $0.3$ is the coefficient the literature is optimizing.
💰 Cost and Queue — the QPU time for RSA-2048 is not the expensive part.
Take §23.6's 1.5-day runtime and price it against Chapter 39 §39.4's list rates, which are for hardware that exists:
text runtime 1.5 days = 36 hr = 2,160 min at ~$96/min $207,360Two hundred thousand dollars of metered time to break RSA-2048. Pricing a machine that does not exist against a rate card for one that does is an illustration and not a forecast — but the shape of the answer is robust, and it is the opposite of what the resource table suggests.
The 24.9 million physical qubits are the cost. The 1.5 days is a rounding error. At any plausible amortization the capital dominates the metered time by orders of magnitude, which is why Case Study 2's timeline argument is about when a machine gets built and never about whether an adversary can afford to run it. An adversary who has the machine has already paid.
Chapter 39 §39.4 makes the same point from the other side. Its break-even duration $d^{*} = 60 P_s / P_m$ is a property of two rate cards, and its longest measured circuit is a 10.55 µs QFT-8. A 36-hour circuit is ten orders of magnitude past that. No pricing model in use today has a row for this workload.
🔀 In Another Framework — the component this chapter skips now ships in two of the four toolchains.
Case Study 1's objection is that a general reversible modular multiplier is the algorithm, and that the demonstration replaced it with a lookup table. Until recently that was also a statement about what the libraries contained. Measured, in this book's environment:
```text PennyLane 0.45.1 qml.ModExp YES general modular exponentiation qml.Multiplier YES qml.OutMultiplier YES qml.PhaseAdder YES qml.Adder YES
Qiskit 2.5.1 ModularAdderGate YES qiskit.circuit.library MultiplierGate YES FullAdderGate YES
Cirq 1.7.0 cirq.ModularExp no (in Cirq's Shor example, not the library) cirq.qft YES ```
PennyLane ships the whole stack up to
qml.ModExp, whose action is $|x\rangle|b\rangle \mapsto |x\rangle|\,b\cdot\text{base}^{x} \bmod \text{mod}\rangle$ for a general modulus — precisely the operation §23.2.2 identified as the entire cost of the algorithm. Qiskit ships the primitives one level below it, modular addition and multiplication, but not the exponentiation on top.This does not make Shor's algorithm runnable, and the widths say why:
text ModularAdderGate(4) 8 qubits MultiplierGate(4) 16 qubits ModularAdderGate(8) 16 qubits MultiplierGate(8) 32 qubits ModularAdderGate(2048) 4,096 qubits MultiplierGate(16) 64 qubitsA modular adder for a 2048-bit modulus is a 4,096-qubit gate — consistent with §23.6's $3n$ and its 6,189 logical qubits for the whole algorithm, against roughly a thousand physical and effectively zero error-corrected logical qubits on today's largest devices.
What has changed is that the hard part is now a library call whose cost you can measure, rather than a research project you have to write. That is a genuine improvement in the state of the art, and it moves nothing in §23.7's table.
🗝️ Version Note — the
Shorclass is gone, and so is the module it lived in.Tutorials from the Qiskit 0.x era open with a line that no longer runs:
python from qiskit.algorithms import Shor # ModuleNotFoundError in Qiskit 2.5.1
qiskit.algorithmsdoes not exist in Qiskit 2.5.1 — measured, not remembered — and a search of the installed package finds noShoranywhere in it. This chapter's implementation is hand-built for that reason, not for pedagogy.The QFT moved as well.
qiskit.circuit.library.QFTstill imports, but the object this chapter uses isQFTGate, appended as a gate rather than composed as a circuit:
python qc.append(QFTGate(t).inverse(), range(t)) # Qiskit 2.xThe practical consequence for this chapter is that there is no library Shor to measure against, which is why §23.6's cost table comes from a resource estimator rather than from transpiling a circuit. You cannot transpile a circuit you cannot construct.
23.7 What This Means, Carefully
The classical competition. The best known classical factoring algorithm is the general number field sieve, which is sub-exponential:
$$\exp\left((64/9)^{1/3}(\ln N)^{1/3}(\ln\ln N)^{2/3}\right)$$
RSA bits GNFS ~ 2^x Shor T count ~ 2^x
256 46.7 24.3
512 63.9 27.3
1024 86.8 30.3
2048 116.9 33.3
$2^{117}$ against $2^{33}$. Shor is polynomial where GNFS is sub-exponential, and the crossover in raw operation count was passed long before 2048 bits.
This is a real exponential separation on a problem people genuinely care about, which is exactly what Chapters 20, 21, and 22 each turned out not to have.
🔬 Honest Assessment — what is and is not true about RSA.
True: Shor's algorithm breaks RSA, Diffie–Hellman, and elliptic-curve cryptography completely. Not weakens — breaks. There is no equivalent of Grover's "double the key length," because the algorithm is polynomial in the key length: doubling the key multiplies the attacker's work by 8, which is nothing.
Also true: the machine required is roughly 25 million physical qubits running for a day and a half, against today's largest devices at around a thousand physical qubits with no error correction at scale. That is four to five orders of magnitude, and it is a manufacturing and fidelity problem, not an algorithmic one.
The number has moved, and only downward. Gidney and Ekerå's 20-million-qubit figure was more than an order of magnitude below earlier estimates, achieved entirely through better constructions rather than better hardware (Chapter 15 Case Study 1). Anyone quoting a fixed date is quoting a fixed guess about two independently moving quantities.
And the deadline is earlier than the machine. Encrypted traffic captured today can be stored and decrypted whenever the machine arrives — harvest now, decrypt later. So the migration deadline is set by how long your data must stay secret, not by when the hardware exists. For data with a twenty-year confidentiality requirement, that deadline may already have passed.
What to do: migrate to post-quantum algorithms on the standard timetable, and prioritize by data lifetime rather than by threat proximity. Chapter 38 covers the migration.
23.7.1 The Deadline Has Three Terms, Not Two
The callout above, and Case Study 2, write the migration deadline as
$$\text{deadline} = (\text{arrival of the machine}) - (\text{data confidentiality lifetime})$$
That expression is missing a term, and it is the only one you control. Migrating a real estate of systems is not instantaneous. The standard statement — Mosca's theorem — puts all three quantities together: if $x$ is how long your data must stay secret, $y$ is how long your migration takes, and $z$ is how long until a cryptographically relevant quantum computer exists, then you have a problem whenever
$$x + y > z$$
Worked against Case Study 2's deliberately conservative 2040 arrival, with a five-year migration — optimistic for anything involving embedded devices, hardware security modules, or a certificate hierarchy:
data lifetime x migration y x + y z (from 2026 to 2040) verdict
5 years 5 years 10 yr 14 yr ok
10 years 5 years 15 yr 14 yr late by 1 year
20 years 5 years 25 yr 14 yr late by 11 years
30 years 5 years 35 yr 14 yr late by 21 years
The migration term alone moves the ten-year row from comfortable to late. Case Study 2's table already had the twenty- and thirty-year rows in the past; adding $y$ pulls the ten-year row in with them.
And $y$ is the only one of the three you can act on. $x$ is a property of your data, fixed by statute or by biology. $z$ is a property of the world and is unknown — §23.6's Math Aside showed that a single coefficient in the resource model moves the T count by 1.75×, and Case Study 2 notes that the whole estimate has only ever moved downward. $y$ is a property of your engineering, and shortening it — crypto-agility, algorithm negotiation, firmware that can be re-flashed — is the one intervention that improves the inequality without requiring anyone to predict anything.
23.7.2 What Shor Does Not Break
The list of what Shor breaks is complete: RSA, Diffie–Hellman, elliptic-curve cryptography, and anything else whose security reduces to a hidden-subgroup problem over an abelian group. The complement is more reassuring than the alarm suggests.
Symmetric encryption is untouched by Shor. AES has no periodic structure for order finding to attack. Grover applies and halves the effective key length, which Chapter 21 §21.7 established is answered completely by doubling it. AES-256 requires no migration.
Hash functions are untouched by Shor, for the same reason, with the same Grover caveat and the same response.
And the deployed replacement for the public-key layer is a classical algorithm, not a quantum one. Chapter 38 §38.7 measured its cost:
ML-KEM-768 full exchange 201.7 us public key 1,184 B ciphertext 1,088 B
X25519 full exchange 76.6 us
ML-KEM is 2.6x slower
A 2.6× slowdown and about a kilobyte per handshake is the entire price of being safe from this chapter. No new fibre, no distance limit, no trusted relays — which is exactly what Chapter 38 measured quantum key distribution cannot offer, with the secret key rate reaching zero at 240.4 km and 2,000 km requiring 19 trusted relays.
The honest caveat, which Chapter 38 states at length: ML-KEM's security is conjectured, resting on Module Learning With Errors, and the SIKE precedent shows what surviving a standardization process is and is not worth. The deployed answer is hybrid — a post-quantum exchange running alongside a classical one, so an attacker must break both — which costs a second handshake and removes the strongest practical reason to wait.
So the shape of the answer is this. Shor is the reason to migrate; the migration is classical; the cost is measured in microseconds and kilobytes; and the deadline is set by §23.7.1's inequality rather than by anything in §23.6's resource table. The chapter that contains the exponential speedup is also the chapter whose practical advice is to deploy a lattice-based key exchange and get on with it.
23.8 Summary
Most of Shor's algorithm is classical. To factor $N$: pick random $a$, find the order $r$ with $a^r \equiv 1 \pmod N$, and if $r$ is even and $a^{r/2}\not\equiv-1$ then $\gcd(a^{r/2}\pm1, N)$ is a non-trivial factor. The quantum computer's entire job is finding $r$.
Two classical failure modes and one free win: odd $r$; $a^{r/2}\equiv-1$ (measured at $a=14$, $N=15$); and $\gcd(a,N)>1$, which hands you a factor with no quantum computer at all. At least half of coprime $a$ work — measured 51–86% across $N = 15$ to 143.
Order finding is phase estimation on $U_a|y\rangle = |ay \bmod N\rangle$, whose eigenvalues are $e^{2\pi i s/r}$ — the period is in the denominator of the phase. You never prepare an eigenvector: initializing the work register to $|1\rangle$ gives an equal superposition of all $r$ of them, and phase estimation returns one at random. This is Simon's algorithm over $\mathbb{Z}_N$, with continued fractions in place of Gaussian elimination.
★ Continued fractions recover the period — Fraction(s/2**t).limit_denominator(N).denominator.
Measured at $N=15$, $r=4$, $t=8$: $s = 64 \to 1/4 \to r=4$; $s=192 \to 3/4 \to r=4$;
$s=128 \to 1/2 \to r=2$ (a divisor, and often good enough); $s=0 \to$ useless. Verify with
pow(a, r, N) == 1 — one line, and it turns a Monte Carlo algorithm into a Las Vegas one.
★ Factoring 15 end to end with $a=7$, $t=8$: exactly four outcomes near 25% each (the values $k\cdot2^t/r$), period votes $\{4: 1044, 2: 526, 1: 478\}$, and $\gcd(7^2-1,15)=3$ giving $15 = 3\times5$. Per-shot success: 76.7%.
★★ Randomized on two levels — the choice of $a$ (50–86% usable) and the measurement ($s=0$ always wasted, $\sim1/r$ of shots at best). The correct structure is a retry loop with classical verification at every stage, and every failure is cheap to detect.
★★ The QFT is a rounding error. Modular exponentiation is $\mathcal{O}(n^3)$ against the QFT's $\mathcal{O}(n^2)$ — at 2048 bits, 1,229× more gates, so the QFT is 0.08% of the circuit. Chapter 22's AQFT saves 82% of that 0.08%. If you want Shor cheaper, every hour belongs in reversible modular arithmetic. The interesting part of an algorithm and the expensive part are frequently not the same part.
The full cost: RSA-2048 needs 10.5 billion T gates, 24.9 million physical qubits, 1.5 days. Doubling the key multiplies T count by 8 and qubit count by 2 — the wall is time, not width.
★★★ And the separation is real. GNFS is sub-exponential; Shor is polynomial. At 2048 bits: $2^{117}$ classical operations against $2^{33}$ quantum T gates. The gap to a working attack is hardware — four to five orders of magnitude in qubit count — not algorithms.
Shor breaks RSA, ECC, and Diffie–Hellman completely — no key-doubling defence exists, because the algorithm is polynomial in key length. And the migration deadline precedes the machine, because traffic captured today can be decrypted later. Prioritize by data lifetime.
Next: Chapter 24 — variational algorithms, and a deliberate change of register. Shor needs a fault-tolerant machine nobody has. VQE and QAOA are designed for the hardware that exists, which means Chapter 16's barren plateaus, Chapter 13's mitigation stack, and Chapter 12's layout scoring all arrive at once — and the honest question of whether any of it beats a classical computer yet.