algorithmsLab
18 min read
Shor's Algorithm
Every piece from the last three lessons, QPE, the order-finding reduction, and the modular-exponentiation oracle, combined into the complete factoring algorithm.
Suggested before this lesson
Every ingredient is on the table: Quantum Phase Estimation reads out a unitary's eigenvalue; 's eigenvalues encode the order of mod ; and (once you have it) classically reduces to a factorization of . One piece is still missing, and it's the one that makes the whole thing actually runnable: QPE's circuit needs an eigenstate of to start from, but which eigenstate depends on , the very thing you don't know yet.
Recall 's eigenstates from last lesson: for . These form a complete orthonormal basis for the -dimensional subspace acts on, which means any state in that subspace, including , is some combination of them. Summing the definition above over every collapses every term except (a standard geometric-series cancellation) and gives, after normalizing:
is an equal-weighted superposition of every eigenstate, and it needs zero special preparation, it's just the computational basis state you get by doing nothing. Run QPE with the eigenstate register starting at instead of a genuine single , and each run effectively estimates the phase of a uniformly random , returning . That randomness is fine, even useful: any coprime to (a majority of them, for typical ) reveals exactly once you feed through continued fractions, the classical algorithm that recovers the smallest-denominator fraction close to a given decimal. If a particular run's happens to share a factor with , continued fractions returns a divisor of instead of itself; the fix is simply to run the whole algorithm again with a fresh random .
Given composite (not prime, not a prime power, both checkable classically first):
Steps 1, 3, 4, 5 are all classical and efficient (polynomial-time). Step 2 is the only quantum piece, and it's exactly the QPE circuit from two lessons ago, with 's controlled powers standing in for the toy used there to demonstrate the mechanism.
. Every step above, order 4, the even/not- check, both gcds, exactly matches the order-finding lesson's worked classical example; the only new piece this lesson adds is how the quantum subroutine produced in the first place, without ever needing to already know it.
Some choices of give an odd , or an where lands on , exactly the retry case step 4 of the algorithm handles. Try a few values and see which ones would actually hand you 15's factors.
Powers of a, mod N
4
Switch and watch the sequence of remainders repeat with a different period every time. That period is exactly the number Quantum Phase Estimation is used to extract: the sequence is periodic with period for any coprime to 15r$, the classical post-processing in the next lesson turns it into 15's factors.
Factoring a large is believed to be classically hard, no known classical algorithm factors an -digit number in time polynomial in ; the best known classical methods scale worse than exponentially in the digit count. Shor's algorithm factors it in polynomial time, using nothing exotic beyond gates this course has already built: , , controlled-phase (for QFT/QPE), and a modular-multiplication oracle (whose internal gate-by-gate construction, for realistic , is its own substantial reversible-arithmetic circuit, out of scope here, the same way basics-oracles deliberately scoped its own oracle construction down to just the linear case rather than every possible ). This is the algorithm that put post-quantum cryptography on the map: RSA's security rests entirely on factoring being classically hard, and this course has now built, gate by gate, every non-black-box piece of the algorithm that breaks that assumption.