Play a chord and your ear separates it into individual notes. That is what a Fourier transform does: it takes something that wobbles and tells you which rhythms are in it.
The quantum version does the same job, and it is astonishingly fast at it.
Fast, with one enormous catch
To do this on a million values, an ordinary computer takes a few tens of millions of steps. The quantum version takes a few hundred.
That looks like an outrageous win, and here is the catch that keeps it honest:
So this is useless for editing audio. It is perfect when a single sample tells you what you need — and for finding one repeating pattern, it does.
What it does to a repeating signal
Feed it something that repeats every r steps. The cancelling from Fundamentals does the rest: every wrong guess about the rhythm wipes itself out, and the right one survives.
Look, and you get a number closely related to r. Run it a couple of times, do a bit of ordinary arithmetic on the results, and you have r exactly.
What it is built from
Hadamards and small turn-by-an-angle gates, in a neat triangular pattern. Nothing you have not already met.
In practice, engineers throw away the very tiniest turns — they are smaller than the machine's own wobble, so they change nothing. That cuts the circuit down a lot for free.
Phase estimation
The job this tool is really doing, and the name you will see everywhere. Give it a repeating process, and it tells you the rhythm. Shor's codebreaking is this. So is working out a molecule's energy.
Worth remembering
- A Fourier transform finds the rhythms hidden in something that repeats.
- The quantum version is enormously faster — but you can only sample one rhythm, never read them all.
- That is exactly enough when you only need to find one repeating pattern.
- It is built from Hadamards and small turns, and it underpins the next lesson.