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">A register of <b>N = 32</b> states is filled with equal spikes every <b>r</b> steps — a periodic quantum state. The blue bars are the raw amplitudes. Press <b>Apply QFT</b> and the same data becomes a few sharp spikes at multiples of <b>N / r</b> — the frequency that reveals the hidden period.</p>
<div class="controls">
  <label>Hidden period r:
    <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">Showing the raw periodic state.</div>
<div class="btns">
  <button id="qft" type="button">Apply QFT</button>
  <button id="reset" type="button" class="ghost">Show raw state</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Period finding with the (quantum) Fourier transform.
// We build a periodic state |x> that is nonzero only at x = 0, r, 2r, ...
// (equal amplitudes), then apply the discrete Fourier transform — exactly
// what the Quantum Fourier Transform computes on a register. The result
// concentrates into spikes at frequencies k that are multiples of N/r.
const N = 32;

// Build the raw periodic amplitudes: 1 at every multiple of r, else 0, normalised.
function rawState(r){
  const a = new Array(N).fill(0);
  let count = 0;
  for(let x = 0; x < N; x += r){ a[x] = 1; count++; }
  const norm = Math.sqrt(count);
  return a.map(v => v / norm); // probability amplitudes; sum of squares = 1
}

// Discrete Fourier transform; return the magnitude (|amplitude|) per frequency k.
// The QFT applies the same unitary; here we compute it directly to visualise it.
function dftMagnitudes(amp){
  const mags = new Array(N).fill(0);
  for(let k = 0; k < N; k++){
    let re = 0, im = 0;
    for(let x = 0; x < N; x++){
      const ang = 2 * Math.PI * k * x / N;
      re += amp[x] * Math.cos(ang);
      im += amp[x] * Math.sin(ang);
    }
    re /= Math.sqrt(N); im /= Math.sqrt(N); // QFT normalisation
    mags[k] = Math.sqrt(re*re + im*im);
  }
  return mags;
}

let mode = 'raw';

function currentR(){ return parseInt(document.getElementById('period').value, 10); }

function draw(values, isQft){
  const chart = document.getElementById('chart');
  chart.innerHTML = '';
  const max = Math.max(...values, 1e-9);
  for(let i = 0; i < N; i++){
    const d = document.createElement('div');
    d.className = 'bar' + (isQft ? ' qft' : '');
    d.style.height = Math.max(1, (values[i] / max) * 210) + 'px';
    d.title = (isQft ? 'frequency k=' : 'state x=') + i;
    chart.appendChild(d);
  }
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }

function showRaw(){
  mode = 'raw';
  draw(rawState(currentR()), false);
  setStatus('Raw periodic state: a flat comb, period buried in plain sight.', '');
}

function showQft(){
  mode = 'qft';
  const r = currentR();
  const mags = dftMagnitudes(rawState(r));
  draw(mags, true);
  const spacing = N / r; // peaks land at k = 0, N/r, 2N/r, ...
  setStatus(fmt('Spikes at k = 0, %spacing%, %v%, … — spacing N/r = %spacing% reveals r = %r%.', { spacing: spacing, v: 2*spacing, r: r }), 'ok');
}

document.getElementById('qft').addEventListener('click', showQft);
document.getElementById('reset').addEventListener('click', showRaw);
document.getElementById('period').addEventListener('change', () => { mode === 'qft' ? showQft() : showRaw(); });
showRaw();

<p class="hint">A register of <b>N = 32</b> states is filled with equal spikes every <b>r</b> steps — a periodic quantum state. The blue bars are the raw amplitudes. Press <b>Apply QFT</b> and the same data becomes a few sharp spikes at multiples of <b>N / r</b> — the frequency that reveals the hidden period.</p>
<div class="controls">
  <label>Hidden period r:
    <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">Showing the raw periodic state.</div>
<div class="btns">
  <button id="qft" type="button">Apply QFT</button>
  <button id="reset" type="button" class="ghost">Show raw state</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Period finding with the (quantum) Fourier transform.
// We build a periodic state |x> that is nonzero only at x = 0, r, 2r, ...
// (equal amplitudes), then apply the discrete Fourier transform — exactly
// what the Quantum Fourier Transform computes on a register. The result
// concentrates into spikes at frequencies k that are multiples of N/r.
const N = 32;

// Build the raw periodic amplitudes: 1 at every multiple of r, else 0, normalised.
function rawState(r){
  const a = new Array(N).fill(0);
  let count = 0;
  for(let x = 0; x < N; x += r){ a[x] = 1; count++; }
  const norm = Math.sqrt(count);
  return a.map(v => v / norm); // probability amplitudes; sum of squares = 1
}

// Discrete Fourier transform; return the magnitude (|amplitude|) per frequency k.
// The QFT applies the same unitary; here we compute it directly to visualise it.
function dftMagnitudes(amp){
  const mags = new Array(N).fill(0);
  for(let k = 0; k < N; k++){
    let re = 0, im = 0;
    for(let x = 0; x < N; x++){
      const ang = 2 * Math.PI * k * x / N;
      re += amp[x] * Math.cos(ang);
      im += amp[x] * Math.sin(ang);
    }
    re /= Math.sqrt(N); im /= Math.sqrt(N); // QFT normalisation
    mags[k] = Math.sqrt(re*re + im*im);
  }
  return mags;
}

let mode = 'raw';

function currentR(){ return parseInt(document.getElementById('period').value, 10); }

function draw(values, isQft){
  const chart = document.getElementById('chart');
  chart.innerHTML = '';
  const max = Math.max(...values, 1e-9);
  for(let i = 0; i < N; i++){
    const d = document.createElement('div');
    d.className = 'bar' + (isQft ? ' qft' : '');
    d.style.height = Math.max(1, (values[i] / max) * 210) + 'px';
    d.title = (isQft ? 'frequency k=' : 'state x=') + i;
    chart.appendChild(d);
  }
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls || ''); }

function showRaw(){
  mode = 'raw';
  draw(rawState(currentR()), false);
  setStatus('Raw periodic state: a flat comb, period buried in plain sight.', '');
}

function showQft(){
  mode = 'qft';
  const r = currentR();
  const mags = dftMagnitudes(rawState(r));
  draw(mags, true);
  const spacing = N / r; // peaks land at k = 0, N/r, 2N/r, ...
  setStatus(fmt('Spikes at k = 0, %spacing%, %v%, … — spacing N/r = %spacing% reveals r = %r%.', { spacing: spacing, v: 2*spacing, r: r }), 'ok');
}

document.getElementById('qft').addEventListener('click', showQft);
document.getElementById('reset').addEventListener('click', showRaw);
document.getElementById('period').addEventListener('change', () => { mode === 'qft' ? showQft() : showRaw(); });
showRaw();

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.