Shor's Algorithm Capstone

Simulate period-finding, the quantum heart of factoring.

Shor's Algorithm Capstone

This is the project where the most famous claim in quantum computing stops being a slogan. You will build the period-finding circuit at the heart of Shor's algorithm, run it, watch the interference pattern appear, and use it to factor 15 into 3 x 5. Every stage is one you implement and verify yourself.

Why Period Finding Factors Numbers

Compute the powers of 7 modulo 15 by hand: 7, then 49 mod 15 = 4, then 28 mod 15 = 13, then 91 mod 15 = 1, and the sequence repeats. The function $f (x) = 7^{x} mod 15$ has period $r = 4$ . That single number unlocks the factorization: since r is even, compute $x = 7^{r /2} mod 15 = 4$ , and then gcd(4 - 1, 15) = 3 and gcd(4 + 1, 15) = 5. Both factors fall out of two greatest-common-divisor calls, which are classically cheap.

Every step in that recipe is easy for a classical computer except one: for a large modulus N, finding the period r takes exponential time classically. The quantum circuit's only job is to find r. Everything before and after is ordinary arithmetic, and in this capstone you implement both sides.

The Circuit at a Glance

Seven qubits, two registers:

•Counting register, q0..q2. Three qubits holding the exponent x = q0 + 2q1 + 4q2, queried in superposition over all eight values at once.
•Work register, q3..q6. Four qubits holding the value $7^{x} mod 15$ , with q3 the least significant bit. It must start at the value 1, because $7^{0} = 1$ .

Three stages, one per quantum checkpoint:

1.Prepare: H on each counting qubit, X on q3. The circuit now queries every exponent simultaneously against a work register holding 1.
2.Controlled modular multiplication: counting qubit j controls a multiplication of the work register by $7^{2^{j}} mod 15$ . Since $7^{1} = 7$ , $7^{2} = 4$ , and $7^{4} = 1$ , the controls multiply by 7, by 4, and by nothing at all. This repeated-squaring structure is why the circuit needs only one multiplier per counting qubit instead of one per exponent value.
3.Inverse QFT: interference converts the hidden period of the entangled state into sharp peaks in the counting register.

This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.

How this lesson works

A multi-step project that combines several concepts into one larger build, checked checkpoint by checkpoint as you go.

Part of: Quantum Algorithms

Learn the algorithms that make quantum computers powerful.

Previous lessonShor's Algorithm Overview Next lessonThe HHL Algorithm

This lesson is part of Pro

Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.

Create account Try the Playground