The Quantum Fourier Transform and Shor's Algorithm

Corresponds to Chapters 6.4–8.1. Generalizes Simon’s Fourier transform over $\mathbb F_2^n$ to the Fourier transform over $\mathbb Z_N$, built from the $N$-th roots of unity $\omega_N$ and the resulting character functions $\chi_s$ — and shows this transform has an efficient ($O(\log^2 N)$-gate) quantum circuit implementation, worked out concretely for $N=16$. Period-finding — given a periodic function, find its period — is solved by the same superposition-then-QFT template as Simon’s algorithm, and Shor’s algorithm reduces integer factoring to period-finding of a specific modular exponentiation function, which is what breaks RSA and the discrete-log/Diffie-Hellman assumptions of number-theory-for-cryptography given a large enough quantum computer — the single result most directly responsible for the field of post-quantum (lattice-based, e.g. LWE-based) cryptography this course builds toward. The hidden subgroup problem is the unifying abstraction: Simon’s algorithm, Shor’s algorithm, and several other quantum speedups are all instances of efficiently finding a hidden subgroup of a group given query access to a function constant on (and only on) its cosets.

Outline (TODO — flesh out each)

• The Fourier transform over $\mathbb Z_N$ — roots of unity, characters
• Implementing the QFT over $\mathbb Z_N$ (worked for $N=16$)
• Period-finding
• Shor’s algorithm
• The hidden subgroup problem