Exercises: Shor's Algorithm

The classical exercises need no quantum computer at all — which is §23.1's point. Solutions to starred exercises are in Answers to Selected Exercises.

The classical half

23.1 ★ Implement brute_force_order(a, N) and tabulate the order of every $a$ coprime to 15, 21, and 33.

23.2 ★ Implement classical_reduction(N, a, r) returning (factor, reason). Verify it returns "a^(r/2) = -1 mod N" for $N = 15$, $a = 14$.

23.3 ★ Reproduce §23.1's table for $N = 15$: every $a$, its order, $a^{r/2} \bmod N$, and the resulting factor or failure reason.

23.4 ★ Compute the fraction of usable $a$ for $N = 15, 21, 33, 35, 77, 143$. Confirm all exceed 50%.

23.5 ★★ Find an $N$ where the usable fraction is exactly 50%, or argue why the bound is tight. What property of $N$ makes it worst-case?

23.6 ★★ Prove that if $r$ is even and $a^{r/2}\not\equiv\pm1 \pmod N$, then $\gcd(a^{r/2}-1, N)$ is a non-trivial factor. Where is each hypothesis used?

23.7 ★★ For $N = p^k$ (a prime power), the reduction never works. Show why, and explain why real implementations check for prime powers classically before doing anything quantum.

Continued fractions

23.8 ★ Implement period_candidates(s, t, N) returning denominators in convergent order. Test it on $s = 64, 128, 192$ at $t = 8$, $N = 15$.

23.9 ★ Show that $s = 0$ yields no usable candidate, and explain why it is always a possible measurement.

23.10 ★★ Take $\varphi = 5/13$ and compute its continued-fraction convergents by hand. At what $t$ does phase estimation resolve enough bits for limit_denominator to recover 13?

23.11 ★★ For $N = 21$ with true period $r = 6$, work out which measured $s$ values at $t = 9$ give $r = 6$, which give a divisor, and which are useless.

23.12 ★★ Write verify_period(a, r, N) and measure how often the first convergent is the true order for $N = 15$ and $N = 21$. How many convergents do you need to try?

The quantum half

23.13 ★ Run the order-finding circuit for $N = 15$, $a = 7$, $t = 8$. Confirm exactly four outcomes, each near 25%.

23.14 ★ Repeat for every $a$ coprime to 15. Which $a$ give two outcomes rather than four, and why?

23.15 ★★ Vary $t$ from 3 to 10 for $a = 7$. At what $t$ do the peaks become sharp, and why is $t = 8$ enough here?

23.16 ★★ Reproduce §23.4's strict-versus-permissive success rates. Explain why both policies are correct.

23.17 ★★ Add depolarizing noise (Chapter 11) at $p = 0.001, 0.01, 0.05$ and measure how the success rate degrades. At what error rate does the algorithm stop working?

23.18 ★★★ The $N = 15$ modular multiplication is a hand-built lookup. Write out what a general reversible modular multiplier would need — adders, comparators, conditional subtraction — and estimate its Toffoli count for $n$-bit inputs.

Where the cost is

23.19 ★ Tabulate QFT gates against modular-exponentiation Toffolis for $n = 8, 64, 256, 1024, 2048$. Report the ratio and the QFT's percentage of the circuit at 2048 bits.

23.20 ★★ Chapter 22's AQFT saves 82% of the QFT's gates at $n = 64$. Compute what that saves in a 2048-bit Shor circuit, as a percentage of the whole. Then argue why the AQFT is still worth using.

23.21 ★★ Using Chapter 15's estimator, price Shor at 128, 256, 512, 1024, and 2048 bits. Confirm the T count scales as $n^3$ and the qubit count as $n$.

23.22 ★★ Compute GNFS's operation count and Shor's T count as powers of two for the same key sizes. At what key size does the gap first exceed $2^{20}$?

23.23 ★★★ Gidney and Ekerå reduced the RSA-2048 estimate by more than an order of magnitude through better constructions. Read their paper and identify the two or three optimizations responsible. Which parts of the circuit did they attack?

The security argument

23.24 ★ Compute the migration deadline for data with 5-, 10-, 20-, and 30-year confidentiality requirements, assuming the machine arrives in 2035, 2040, and 2045. Present as a table.

23.25 ★★ Grover halves symmetric key strength; Shor breaks public-key cryptography outright. Explain why doubling the key length answers one and not the other, in terms of the algorithms' complexity in the key length.

23.26 ★★ Explain "hybrid" post-quantum deployment and what specific risk it mitigates. What does it cost?

23.27 ★★★ Build a data inventory template sorted by confidentiality lifetime, and apply it to a system you know. Which classes are already past their deadline under a 2040 assumption?

Project

23.28 ★★ (Project Checkpoint) Build vqelab/shor.py with classical_reduction (returning the reason), brute_force_order, usable_base_fraction, period_candidates, order_finding_circuit, measure_phases, and shor() returning a FactorResult. Write tests asserting:

  1. The reduction finds a factor for a good base.
  2. It fails with reason "a^(r/2) = -1 mod N" at $N=15$, $a=14$.
  3. It rejects an odd period.
  4. brute_force_order(7, 15) == 4.
  5. At least half of coprime bases are usable for $N = 15, 21, 33, 35, 77$.
  6. Continued fractions recovers $r = 4$ from $s = 64$ and $s = 192$.
  7. $s = 0$ yields no candidate.
  8. $s = 128$ offers $r = 2$, a divisor.
  9. Order finding gives exactly four outcomes, each near 25%.
  10. Every nonzero outcome yields a usable period.
  11. An unsupported modulus raises with a message naming what is missing.
  12. shor(15) returns $3 \times 5$, verified, under both policies.
  13. Even $N$ is handled classically with zero shots.
  14. Every returned factorization multiplies back to $N$.

Tests 11 and 14 are the ones that matter: the first keeps the implementation honest about what it does not do, the second is the Las Vegas guarantee.

23.29 ★★★ Extend shor.py with factor_report(N) producing a full account: every $a$ tried, why each failed, how many shots each consumed, and the final verified factorization. Run it 100 times with different seeds and report the distribution of attempts needed.

Going further

23.30 ★★★ Shor's algorithm also solves discrete logarithm, which breaks Diffie–Hellman and ECC. Read the construction and explain what changes: what is the period, and what does the classical post-processing become?

23.31 ★★★ Case Study 1 argues that a demonstration using a hand-built permutation for modular multiplication does not demonstrate Shor's algorithm. Find a published factoring demonstration, read its circuit construction, and determine whether the modular arithmetic is general or compiled. State your evidence.

23.32 ★★★ All of Chapter 20's algorithms, Chapter 21's Grover, and Shor are instances of the hidden subgroup problem. State Shor's hidden subgroup, and explain why the non-abelian case — which contains graph isomorphism — has resisted a quantum algorithm.