Quantum Fourier Transform

A Fourier transform answers one question: what frequencies are hiding inside a signal? Feed it a sound and it tells you the notes; feed it a list of numbers that repeats every few steps and it tells you the period. The classical Fast Fourier Transform (FFT) does this brilliantly, but it has to touch all N numbers — its cost grows like N log N.

The Quantum Fourier Transform (QFT) does the same job on a quantum state. The catch is that the quantum state can hold a superposition of all N inputs at once, encoded in just $\log_{2}$ N qubits. The QFT then rearranges the amplitudes of that state so that, when you measure, the hidden period shows up as a spike at the matching frequency.

That single trick — turn a repeating pattern into one sharp peak — is the beating heart of Shor's algorithm, the routine that would let a quantum computer factor huge numbers and break much of today's encryption.

Below is a register of N = 32 basis states. Choose a hidden period r; the state is filled with equal "spikes" every r steps — exactly the kind of periodic state period-finding produces. The blue bars show the raw amplitudes: flat and uninformative, the period buried in plain sight.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{label_period}}
    <select id="period">
      <option value="2">2</option>
      <option value="4" selected>4</option>
      <option value="8">8</option>
    </select>
  </label>
</div>
<div class="chart" id="chart"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="qft" type="button">{{btn_apply_qft}}</button>
  <button id="reset" type="button" class="ghost">{{btn_show_raw}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { margin: .4rem 0 .6rem; font-size: .92rem; }
select { font: inherit; padding: .2rem .4rem; border-radius: 6px; border: 1px solid #adb1b8; }
.chart { display: flex; align-items: flex-end; gap: 2px; height: 220px;
         border-bottom: 2px solid #1d3557; padding-top: 4px; }
.bar { flex: 1; background: #4d7ea8; border-radius: 3px 3px 0 0; transition: height .25s, background .25s; min-height: 1px; }
.bar.qft { background: #e08a1e; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Now press Apply QFT. The orange bars show the transformed amplitudes. The flat comb collapses into a handful of sharp spikes, and they land at multiples of N⁄r — the frequency that reveals the period. Reading off a peak gives you r in essentially one shot. A classical computer would have to inspect the whole list to find the same rhythm.

How much faster is the quantum version, really?

• Classical FFT: to transform a list of N = $2^{n}$ numbers it uses on the order of N log N arithmetic operations. That is already optimal for reading every entry — and reading every entry is unavoidable classically.
• Quantum QFT: it acts on n = $\log_{2}$ N qubits and needs only about $n^{2}$ ≈ (log N)² elementary gates (Hadamards and controlled phase rotations). The number of operations drops from N log N to roughly (log N)² — an exponential reduction.
• The honest caveat. You cannot just read out all N transformed amplitudes — one measurement gives a single outcome, sampled with the probabilities the QFT produced. So the QFT is not a free FFT. It is decisive precisely when the answer you want is a single feature of the spectrum, like the location of a spike, which is exactly the period-finding case.
• Status: this is proven and solved — Coppersmith described the efficient QFT circuit in 1994 and Peter Shor built period-finding on top of it the same year, giving a polynomial-time quantum factoring algorithm. It is not conjecture; it is the textbook construction.

That last point is the whole game. Factoring large numbers is believed to be hard classically — hard enough that we trust factoring to protect our secrets. The QFT does not make factoring "easy" everywhere; it makes the one sub-question Shor needs — find the period of a modular function — answerable fast, and that is enough to crack the lock.

The QFT is less a destination than a universal tool. Most of the famous quantum speedups route through it:

• Breaking RSA: Shor's algorithm uses the QFT to find the period of a modular exponential, and from that period it recovers the factors of a number. This is the threat that drives post-quantum cryptography.
• Phase estimation: the QFT lets you read the eigenvalue (a phase) of a quantum operation, the engine behind quantum chemistry simulations and many linear-algebra speedups.
• The hidden subgroup problem: discrete logarithms and several group-theory problems are all "find the hidden period" in disguise, and the QFT solves the abelian cases.
• Signal-style problems: anywhere a periodic structure is buried in exponentially much data, the QFT can expose it without scanning the whole space.

If you understand the QFT you have met the workhorse behind nearly every quantum algorithm with an exponential edge — far more central than the better-known Grover search, which only manages a quadratic speedup.

The quantum Fourier transform does something deceptively simple: it takes a state that secretly repeats and concentrates its amplitude into a few sharp spikes at the period's frequency. The same job the classical FFT does in N log N steps, the QFT does in about (log N)² gates — exponentially fewer operations on exponentially compressed data.

The price is that you only get to measure once, so the magic appears only when one feature — a spike — is all you need. That happens to be exactly the case for period finding, and period finding is exactly what Shor's algorithm needs to factor numbers. Behind a small comb of orange bars sits the most consequential subroutine in quantum computing, and the reason much of modern factoring-based cryptography is living on borrowed time.