Quantum Fourier transform

How does Shor's algorithm factor a number without trying factors? It finds a repeating loop, and the Quantum Fourier Transform is what finds that loop.

What this Short covers:

1. Shor's algorithm turns factoring into period finding: keep multiplying a number and the remainders repeat.
2. Example: 7^x mod 15 gives 7, 4, 13, 1, 7… a loop of length 4.
3. Knowing the loop length gives the factors: gcd(7² − 1, 15) = 3 and gcd(7² + 1, 15) = 5, so 15 = 3 × 5.
4. For large numbers, finding the loop is hard for classical computers. The Quantum Fourier Transform does it by making the repeats interfere until the period stands out.
5. The QFT does not speed up ordinary Fourier transforms: measurement cannot read out all its outputs, so its advantage shows up inside algorithms like Shor's.

Fine print for the algorithms crowd: the "loop" is the period r of a^x mod N (here 7^x mod 15 = 7, 4, 13, 1, so r = 4). With an even period, gcd(a^(r/2) ± 1, N) gives the factors: gcd(48, 15) = 3 and gcd(50, 15) = 5. This works for most choices of a, not every one. "Hard part" means hard for a classical computer; in gate count the QFT is cheap and modular exponentiation is the costly quantum step. "Read that beat": one measurement gives a clue to r, a short classical step (continued fractions) finishes it, and sometimes you rerun. The music-app line is an analogy: beat trackers use Fourier-style analysis of the audio, not a QFT.

1. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer" (1995)arxiv.org
2. Quantum Fourier transformen.wikipedia.org
3. Shor's algorithmen.wikipedia.org
4. Cambridge DAMTP, Quantum Information and Computation notes, Shor's algorithmqi.damtp.cam.ac.uk
5. resources.mpi-inf.mpg.de
6. musicinformationretrieval.com
7. arxiv.org