Quiz: Shor's Algorithm

Answers with explanations at the end.

1. What problem does the quantum part of Shor's algorithm actually solve, and what does the rest of the algorithm do with the answer?

2. State the reduction from factoring to order finding, including both conditions on $r$.

3. Name the two failure modes of the classical reduction and the one case where you get a factor for free.

4. For $N = 15$, $a = 14$: the order is 2. Why does the reduction fail?

5. What fraction of coprime bases $a$ lead to a factor? Give the theoretical bound and two measured values.

6. Write the unitary whose phase estimation gives the order, and say where the period appears.

7. Phase estimation requires an eigenvector of $U$. You do not know the eigenvectors of $U_a$ because they depend on $r$. How is this resolved?

8. Which earlier algorithm has the same structure as Shor's, and what are the two corresponding post-processing steps?

9. A measurement gives $s$. Write the one-line Python that turns it into a candidate period.

10. At $N = 15$, $r = 4$, $t = 8$: what do $s = 0, 64, 128, 192$ each give, and which are usable?

11. Why should you verify a candidate period, and what is the check?

12. Order finding for $N = 15$, $a = 7$ gives exactly four outcomes, each near 25%. Explain both the count and the sharpness.

13. The strict policy gives 51.0% per-shot success and the permissive policy 76.7%. What is the difference between them, and why are both correct?

14. Shor's algorithm is randomized on two levels. Name them and say what each costs.

15. At 2048 bits, how do the QFT and modular exponentiation compare in gate count? What percentage of the circuit is the QFT?

16. Chapter 22's approximate QFT saves 82% of the QFT's gates. What does that save in a 2048-bit Shor circuit, and is the AQFT therefore pointless?

17. Give the resource estimate for RSA-2048, and say which of qubit count or runtime is the binding constraint as key size grows.

18. Compare Shor against the best classical factoring algorithm at 2048 bits, as powers of two. What does the comparison say about where the remaining difficulty lies?

19. Why is there no equivalent of "double the key length" against Shor, as there is against Grover?

20. A security team concludes "the machine does not exist, revisit in five years." What question did they answer, what question should they have answered, and what is the resulting formula?

Answers

1. The quantum part solves order finding: given $a$ and $N$, find the smallest $r$ with $a^r \equiv 1 \pmod N$. Everything else — choosing $a$, checking $\gcd$, applying the reduction, verifying the factors — is elementary classical number theory and runs on a laptop.

2. If $r$ is even and $a^{r/2}\not\equiv-1 \pmod N$, then $(a^{r/2}-1)(a^{r/2}+1) = a^r - 1 \equiv 0 \pmod N$, so $N$ divides the product without dividing either factor, and $\gcd(a^{r/2}\pm1, N)$ is a non-trivial factor.

3. Failure modes: $r$ is odd; and $a^{r/2}\equiv-1 \pmod N$, which makes $\gcd(a^{r/2}+1, N) = N$ and the other gcd 1. Free win: $\gcd(a, N) > 1$, where Euclid hands you a factor with no quantum computation at all — which is why it is always checked first.

4. $14^{1} \bmod 15 = 14 = N - 1 \equiv -1$. So $\gcd(14-1, 15) = \gcd(13,15) = 1$ and $\gcd(14+1,15) = \gcd(15,15) = 15$ — both trivial. Pick a different $a$.

5. At least half, for $N$ with at least two distinct odd prime factors. Measured: $N = 15$ gives 6/7 (86%); $N = 77$ gives 30/59 (51%).

6. $U_a|y\rangle = |ay \bmod N\rangle$, whose eigenvalues are $e^{2\pi i s/r}$ for $s = 0,\dots,r-1$. The period appears in the denominator of the phase, so estimating the phase estimates the period.

7. You do not need one. Initializing the work register to $|1\rangle$ gives an equal superposition of all $r$ eigenvectors, $|1\rangle = \frac{1}{\sqrt r}\sum_s|u_s\rangle$, and phase estimation on a superposition returns one of their phases chosen at random — which is exactly what the algorithm needs.

8. Simon's algorithm (Chapter 20), over $\mathbb{Z}_N$ instead of $(\mathbb{Z}_2)^n$. Simon's post-processing is Gaussian elimination over $\mathbb{F}_2$; Shor's is continued fractions. In both, the quantum subroutine produces constraints and classical computation turns constraints into answers.

9. Fraction(s, 2**t).limit_denominator(N).denominator

10. $s=0 \to$ convergent 0, $r = 1$, useless. $s=64 \to 1/4$, $r = 4$, correct. $s=128 \to 1/2$, $r = 2$, a divisor of the true period — often still good enough. $s=192 \to 3/4$, $r = 4$, correct.

11. Because continued fractions returns a candidate, not a guarantee — it may return a divisor of $r$, or nothing useful. The check is pow(a, r, N) == 1, one line and microseconds, and it is what makes Shor's a Las Vegas algorithm (variable time, certain answer) rather than a Monte Carlo one.

12. Four outcomes because the measurable values are $s = k \cdot 2^t/r$ for $k = 0,\dots,r-1$ with $r = 4$. Sharp because $k/4$ is a dyadic rational, exactly representable in $t = 8$ bits — so phase estimation is exact (Chapter 22 §22.4) and the distribution is four delta peaks rather than a spread.

13. The strict policy requires pow(a, r, N) == 1 before applying the reduction; the permissive policy applies the reduction to any candidate and verifies the resulting factor. Both are correct because the final factor is checked either way — $f$ divides $N$ or it does not. The 26-point gap is entirely the $s = 128 \to r = 2$ outcome, which fails the order check but still reduces successfully ($\gcd(6,15)=3$).

14. Level 1 — the choice of $a$: 50–86% of coprime $a$ lead to a factor; failure means odd $r$ or $a^{r/2}\equiv-1$, and costs one full quantum run. Level 2 — the measurement: $s = 0$ is always possible and always useless, and other outcomes may give a divisor rather than $r$; roughly $1/r$ of shots are wasted at best.

15. QFT: 2,096,128 gates. Modular exponentiation: 2,576,980,377 Toffolis — a factor of 1,229. The QFT is 0.08% of the circuit.

16. It saves 82% of 0.08%, or 0.07% of the circuit — negligible. The AQFT is not pointless: it removes rotations smaller than any hardware can reliably apply, so it is about feasibility rather than gate count. But to make Shor cheaper, every hour belongs in reversible modular arithmetic.

17. 10.5 billion T gates, 24.9 million physical qubits, 1.5 days. As key size grows, T count scales as $n^3$ (doubling the key multiplies it by 8) while qubit count scales as $n$ (doubling doubles it) — so the wall is time, not width.

18. GNFS needs roughly $2^{117}$ operations; Shor needs roughly $2^{33}$ T gates — a gap of about $2^{84}$. GNFS is sub-exponential and Shor is polynomial, so the separation is genuine and grows. The remaining difficulty is entirely hardware — four to five orders of magnitude in physical qubit count — not algorithms.

19. Because Shor is polynomial in the key length. Doubling an RSA modulus from 1024 to 2048 bits multiplies the attacker's work by about 8 ($n^3$), which is nothing. Grover, by contrast, gives only a square-root improvement, so doubling a symmetric key exactly restores the original security margin. Shor breaks public-key cryptography; Grover weakens symmetric cryptography.

20. They answered "when will a quantum computer break our encryption?" They should have answered "how long does data we transmit today need to stay secret?" — because ciphertext captured now can be decrypted later ("harvest now, decrypt later"). The formula:

$$\text{migration deadline} = (\text{arrival of the machine}) - (\text{data confidentiality lifetime})$$

For data with a 20-year lifetime and a 2040 arrival, the deadline was 2020 — already past. Prioritize by data lifetime, not threat proximity, and deploy hybrid to hedge the maturity of the new algorithms.