QFT as glasses for periods

The classical Fourier transform is two centuries old and has nothing to do with quantum mechanics. What it does fits in one sentence: it turns a period that is invisible on the time axis into a peak on the frequency axis.

A chord mixed from several tones is hard to parse by ear. A spectrum analyser lights those tones as separate peaks. The discrete Fourier transform is that analyser for a length-$N$ signal:

$$F(k)=\sum_{x=0}^{N-1} f(x)\,e^{-2\pi i k x / N}.$$

For every frequency $k$ at once, it asks how much of period $k$ sits inside $f$. Noise can make the time series look messy while the peaks still stand — periodic structure is usually tougher than noise.

Same transform, different carrier

The quantum Fourier transform is the same map, with one change of carrier: the input is no longer an array of numbers but the amplitudes of a quantum state.

$$\mathrm{QFT}:\ |x\rangle \longmapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i k x / N}\,|k\rangle.$$

Same kernel. $f(x)$ has become an amplitude; the output is read as a measurement probability. That is the whole difference that matters for period finding.[1][2]

Why a periodic amplitude comb becomes peaks

Suppose the state before QFT is an amplitude comb with spacing $r$ — nonzero only every $r$ basis states. Measuring that state returns one random $x$ on the comb. One $x$ does not reveal $r$.

Apply the QFT. For each candidate frequency $k$, the phases contributed by the comb either line up or spread evenly:

• When $k$ is near a multiple of $N/r$, the phases reinforce (constructive interference). Those bins get most of the probability.
• Everywhere else the phases cancel (destructive interference). Those bins nearly vanish.

So QFT is not inventing information. It relocates it: the phase structure that was invisible to a computational-basis measurement becomes a concentration of probability at the right frequencies. After one shot you typically hold a sample related to $k/N \approx m/r$, and classical continued fractions recover $r$.

QFT moves phase that probability cannot see into probability that measurement can see.

Where this sits in Shor

Shor does not search for factors of $N$ by trial division. It replaces factoring with period finding.[3]

1. Pick a random base $a$ with $\gcd(a,N)=1$.
2. Build the modular-exponential sequence $f(x)=a^x \bmod N$, which is periodic with some unknown period $r$.
3. Prepare a superposition, compute $f$ into an ancillary register, and obtain a periodic amplitude comb.
4. QFT + measure — the only quantum stretch that does the real work.
5. Continued fractions and a classical gcd finish the factors when $r$ is even and well-behaved; otherwise retry.

Everything before and after step 4 is classical. The quantum machine is there to put on Fourier glasses and read a period that would otherwise cost exponential modular exponentiations.

What QFT is not

QFT is not a universal accelerator. It pays off when the problem has a periodic structure that Fourier sampling can expose — discrete log and factoring live in that class. Unstructured search does not; that is Grover’s square-root story, not QFT’s.

If you only remember one picture: classical Fourier finds tones in a waveform; QFT finds the hidden period of an amplitude comb and hands that period to the classical post-processing that actually cracks RSA-style hardness.