Shor's Algorithm and the Quantum Fourier Transform

The reduction

Factoring N reduces to finding the period r of f(x) = a^x mod N for a random a. Once r is known, gcd(a^(r/2) ± 1, N) yields a factor with good probability. The number theory is classical and cheap. The hard step is finding r. See RSA and the Factoring ProblemNoteGrowingRSA and the Factoring ProblemHow RSA turns the difficulty of factoring into a lock, why the lock has a hidden period, and a worked example with small numbers. Originally Appendix A of The Resolution of Reality..

The quantum step

1. Prepare a register in a uniform superposition over inputs x from 0 to some Q ≫ N².
2. Compute f(x) into a second register, so the state is a superposition of pairs (x, a^x mod N).
3. Apply the Quantum Fourier Transform to the first register.
4. Measure. The outcome is, with high probability, close to a multiple of Q/r. A few repetitions and a continued-fraction step recover r.

The reason step 3 works is exactly the reason the classical Fourier TransformNoteSeedFourier TransformAny physically realistic signal is a sum of sines and cosines; the transform recovers which ones and how strongly. Built to solve the heat equation, it is also the engine of Shor's algorithm. works: a periodic signal has a spectrum concentrated at multiples of its fundamental frequency. Amplitudes at other frequencies cancel. Quantum interference performs the whole transform in one pass over 2^n amplitudes, which no classical machine can do.

Why this note is the bridge

The mathematics essay From Smooth to JaggedEssayFrom Smooth to JaggedHow mathematics grew a new tool each time reality posed a problem the existing math could not solve, from Taylor series to the Fourier transform, stochastic calculus, fractal geometry, and rough paths, ending with a personal encounter with Benoit Mandelbrot and its bearing on reading markets. presents the Fourier transform as the tool Joseph Fourier built to solve the heat equation. The quantum primer The Resolution of RealityEssayThe Resolution of RealityA primer on quantum computing: how physical law replaces brute-force search, why the advantage depends on how native the problem is to the machine, and where hybrid classical-quantum architectures fit. presents Shor's algorithm as the lens that focuses a superposition onto the correct period. They are the same operation. A reader who understands one has most of the other.

What this note does not yet cover

• The circuit for the QFT and why it costs O(n²) gates rather than the classical O(n 2^n).
• Why Q must be much larger than N² (resolution of the period).
• The continued-fraction post-processing.

Review log

• 2026-09-08: seeded to fix an ambiguity in Section VII of the primer, where the RSA lens and the molecule lens were described with one mechanism.