Shor's Algorithm: Period Finding

Factoring N = 15 with base a = 7 is four steps, and only one of them is quantum.

Classical. Check gcd(7, 15) = 1. If that had come out above 1 you would already have a factor and could stop — no quantum computer needed. It did not, so continue.

Quantum. Put the counting register into an equal superposition of all 256 values of x, compute 7^x mod 15 into a second register, and measure that second register. The counting register collapses onto exactly the x that produce the residue you saw — an evenly spaced comb whose spacing is the period. Then apply the quantum Fourier transform, which turns a comb of spacing r into a comb of spacing 2ⁿ/r, and measure.

Classical. The measured c is close to s·2ⁿ/r for some integer s you do not know. Expand c/2ⁿ as a continued fraction and read off the denominator: that is r, which is 4 here.

Classical. If r is even and a^r/2 ≢ −1 (mod N), then gcd(a^r/2 ± 1, N) splits N. For this base: 4, giving 3 × 5 = 15.

Notice what the quantum step returned: a number that is near a multiple of 2ⁿ/r. Not the factors. Not even the period. The famous speedup is entirely in finding a period exponentially faster than you could by evaluating a^x mod N one x at a time.

If r divided 2ⁿ exactly, the QFT of the surviving comb would be exactly r spikes and nothing else. It almost never does. Here 2^8 = 256 and r = 4, so the ideal peaks sit at 0, 64, 128, 192 — which are integers, so the comb is sharp for this pair.

That smearing is the reason for the continued-fraction step, and the reason n is chosen so that 2ⁿ ≥ N². With that much resolution the true s/r is the only fraction with denominator below N anywhere near c/2ⁿ, so the expansion cannot pick the wrong one. Use fewer counting qubits and the algorithm still runs, still produces peaks, and quietly stops being correct.

The counting register here is a real statevector: 256 complex amplitudes, transformed by an actual Hadamard-and-controlled-phase QFT circuit. The work register is not expanded into gates — the joint state Σ_x|x⟩|a^x mod N⟩ is written down exactly from the classical table of a^x mod N, and the measurement of the work register is applied to it with the Born rule. That is exact, but it does skip the compilation of modular exponentiation into adders, which is where a real machine spends nearly all its qubits and nearly all its gates.

Simulated properly, N = 15 needs 8 + 4 = 12 qubits, which is 4,096 amplitudes before a single ancilla. A 2048-bit RSA modulus needs roughly 4096 counting qubits and a work register to match. That is 2⁶⁰⁰⁰-ish amplitudes. There are about 2²⁷⁰ atoms in the observable universe. This is not a matter of buying a bigger laptop, and the fact that a quantum computer would not have to store any of it is the entire point of the field.

A machine that ran this on a 2048-bit number would break RSA. Nobody has one. The largest numbers factored on real quantum hardware by an unassisted Shor run are two digits, and several widely publicised “records” were compiled using knowledge of the answer, which makes the circuit smaller and the result meaningless.

The reason the field takes it seriously anyway is that encrypted traffic can be recorded now and decrypted later. That is why post-quantum key exchange is being deployed today, years ahead of any machine that could threaten what it replaces.