Shor's Quantum Step

Simulate the circuit that finds the period for N up to 63. The Fourier transform turns a comb into peaks, and continued fractions turn a peak into r.

Quantum algorithmsFactoringdemo

Objectives

Size the input register so that Q = 2^q is at least N^2.
Explain why the measured y lands near a multiple of Q/r.
Recover r from y/Q with continued fractions, and explain why a few runs are enough.

20%

Simulate the circuit that finds the period: a superposition, the modular exponentiation, and the quantum Fourier transform.

Q = 2^q ≥ N^2 measured y ≈ j·Q/r y/Q ≈ j/r → r

Two registers of qubits

The circuit has an input register of q qubits and an output register big enough to hold a number below N. The input register holds Q = 2^q values, and Q must be at least N^2 so that the result pins down r. The circuit does three things:

1. H on every input qubit: an equal superposition of x = 0, 1, …, Q − 1 2. Compute a^x mod N into the output register, for all x at once 3. Apply the quantum Fourier transform (QFT) to the input register, then measure it

modulus N (up to 63, so the simulation stays small)

base a (only bases with gcd(a, N) = 1)

input qubits q

Q = 2^q (at least N^2)

256 ≥ 225

output qubits

total qubits

After a^x mod N: the inputs fall into classes

After step 2 every x sits next to its output a^x mod N. The outputs repeat with period r = 4, so the inputs fall into r classes: the x values that share one output are spaced exactly r apart. The circuit never prints this table. The period is hidden in the spacing, and the QFT is what turns a spacing into something a measurement can see.

The first 12 inputs x, their outputs 7^x mod 15, and their class x mod 4.
Class (x mod r)	Output	Inputs x in the class (first values)
0	1	0, 4, 8, 12, …
1	7	1, 5, 9, 13, …
2	4	2, 6, 10, 14, …
3	13	3, 7, 11, 15, …

Each class is a comb of teeth r = 4 apart, about Q/r = 64.0 teeth long.

After the QFT: peaks at multiples of Q/r

The Fourier transform turns a comb with spacing r into peaks at spacing Q/r. Paths to values between the peaks cancel, the way the two paths cancelled on the qubit page. The chart shows the probability of each measurement result y from 0 to 255.

The peaks: j times Q over r, the nearest whole y, and its probability.
j	j·Q/r	nearest y	P(y)
0	0	0	25.0%
1	64	64	25.0%
2	128	128	25.0%
3	192	192	25.0%

Here r = 4 divides Q = 256, so every peak is exact and nothing else is possible.

Measure, then recover r with continued fractions

A measurement gives one y. It is close to j·Q/r for some j, so y/Q is close to j/r. The continued fraction expansion of y/Q lists the best fractions with small denominators; the classical computer tries each denominator d below N and keeps the first with a^d mod N = 1.

A failed run costs one more run of the circuit. A few runs are enough, which is why the algorithm counts as efficient.

From 15 to RSA-2048

For an n-bit N, the textbook circuit uses about 2n input qubits and n output qubits: about 6,144 logical qubits for RSA-2048. Beauregard (2003) reduced it to 2n + 3 = 4,099. The expensive part is step 2, the modular exponentiation, whose gate count grows roughly as n^3 with schoolbook arithmetic.

Logical qubits must be built from many error-prone physical qubits. The 2025 estimate by Gidney is under one million physical qubits running for under a week, at 0.1% error per operation. That is an engineering estimate, not an experiment. As of 2025 no quantum computer had factored even 21 by running Shor's algorithm in full.

step 1/5

CPE 645 / CS 685

Shor's Quantum Step

Factoring from a Period

Grover's Search