You are reading without signing in. Sign in or continue as guest to take quizzes and climb the ranks.
Shor's algorithm: the overview
Factoring reduces to period finding; period finding is phase estimation. What is quantum, what is classical, what it costs.
- 01State the classical reduction from factoring to finding the period of aˣ mod N.
- 02Identify the quantum step and its cost.
- 03Explain why no current machine threatens RSA-2048.
- Pick a random a < N. If gcd(a, N) > 1 you are done.
- Find the period r of f(x) = aˣ mod N: the smallest r with aʳ ≡ 1. This is the quantum step.
- If r is even and a^{r/2} ≠ −1 mod N, then gcd(a^{r/2} ± 1, N) are factors. Otherwise try another a (a few tries suffice).
Period finding is phase estimation on the unitary that multiplies by a modulo N: its eigenphases are multiples of 1/r, so the counting register reads k/r and a continued-fraction step recovers r. Everything hard sits in the modular multiplication circuits, which need thousands of logical qubits and millions of gates for a 2048-bit N.
| Step | Classical or quantum | Cost |
|---|---|---|
| Choose a, gcd | classical | trivial |
| Period of aˣ mod N | quantum (QPE) | O((log N)³) gates, 2·log N + extra qubits |
| Continued fractions, factors | classical | trivial |
Record demonstrations factor 15 and 21 with heavily simplified circuits. Breaking RSA-2048 needs roughly 20 million noisy physical qubits running for hours by current estimates, against machines of a few hundred to a thousand qubits today. The threat is real but not imminent, and migration to post-quantum cryptography is already under way.
Period finding for 15 with a = 4
A tiny, honest version of the quantum step on four qubits. Two counting qubits run phase estimation on 'multiply by 4 mod 15'. Starting from |1⟩ = 0001, multiplying by 4 gives 0100 and multiplying again gives 0001 back, so only work bits 0 and 2 ever change and the multiplication is a single controlled swap; the two work bits that stay 0 are left out (real compiled demonstrations do the same). Simulate: the counting register reads 0 or 2 (out of 4), 50% each. 2/4 = 1/2 gives the period r = 2, so 4^(2/2) = 4 and gcd(4 − 1, 15) = 3, gcd(4 + 1, 15) = 5. Reading 0 tells you nothing, so you would run again. Real circuits for large N need the full modular arithmetic and many more counting qubits, which is where the cost lies.
OPENQASM 3.0;
include "stdgates.inc";
qubit[4] q;
bit[2] c;
x q[2];
h q[0];
h q[1];
// controlled ×4 mod 15: on |1⟩ only work bits 0 and 2 change, so ×4 is one swap
cswap q[0], q[2], q[3];
// controlled ×16 mod 15 = ×1: q[1] needs no gate
// inverse QFT on the counting register
swap q[0], q[1];
h q[0];
cp(-pi/2) q[1], q[0];
h q[1];
c[0] = measure q[0];
c[1] = measure q[1];
2 questions · one try each counts
Which part of Shor's algorithm is quantum?
Sign in to answer and climb the ranks; you will come back to this lesson.
Why does Shor's algorithm not break symmetric ciphers like AES?
Sign in to answer and climb the ranks; you will come back to this lesson.