The Quantum Fourier Transform, Gate by Gate

Same transform, a completely different machine

The Quantum Fourier Transform (QFT) computes exactly the discrete Fourier transform you already know from signal processing - it maps a vector of N = 2ⁿ complex amplitudes to another vector of N amplitudes related by the same complex exponential kernel as the classical DFT. What changes is where those amplitudes live. A classical FFT holds N numbers in an array; the QFT acts on N amplitudes encoded implicitly across the superposition of just n qubits, and it does so using a circuit with only O(n²) elementary gates - polynomial in the number of qubits, exponentially fewer than the N log N = n·2ⁿ operations an FFT needs to touch every amplitude explicitly.

The definition

Given a basis state |j⟩ with j between 0 and N-1, the QFT produces a specific superposition over every basis state |k⟩, weighted by a complex phase that depends on the product jk:

QFT |j⟩  =  (1/√N)  Σ_{k=0}^{N-1}  e^(2πi·jk/N)  |k⟩

N = 2^n,  j and k are n-bit integers 0 .. N-1
every output amplitude has EQUAL magnitude 1/√N - only the phase varies

Notice every output amplitude has the same magnitude - all the information the transform carries is packed entirely into the phases, not the probabilities of a naive measurement. That is both the QFT's power and its limitation: reading out the transformed state by direct measurement throws almost all of that phase information away, which is why the QFT is never used as a standalone "read the spectrum" tool - it is always one stage inside a larger algorithm that manipulates those phases further before anything is measured.

Building it from Hadamards and controlled phases

The circuit that implements the QFT on n qubits is a tight, repeating pattern: for each qubit, apply a Hadamard gate, then a cascade of controlled phase rotations R_k = diag(1, e^(2πi/2^k)) controlled by every qubit still to come, with the rotation angle halving each time you move one qubit further away:

for qubit q = 0 .. n-1:
    apply H to qubit q
    for each qubit q' after q (distance d = q'-q):
        apply controlled-R_{d+1} from qubit q' onto qubit q
            (adds a phase of 2π / 2^(d+1) conditioned on q' being 1)
finally: reverse the qubit order with SWAP gates

Each qubit's Hadamard puts it into superposition; the controlled rotations that follow correct that superposition's phase using the state of every remaining qubit, exactly encoding the binary expansion of the input j into a cascading pattern of phase angles. Counting gates: qubit 0 needs one Hadamard and n-1 controlled rotations, qubit 1 needs one Hadamard and n-2, and so on down to the last qubit's single Hadamard - a triangular sum that totals O(n²) gates, plus the ⌊n/2⌋ swaps at the end to put the qubits back in standard order.

Where the speed comes from, and where it stops

The exponential gap between O(n²) and O(n·2ⁿ) looks like a free lunch, but it comes with two conditions that quietly restore the balance for ordinary applications. First, you need the N input amplitudes already loaded into a quantum state - if you have to encode N classical numbers qubit by qubit, that loading step alone typically costs O(N), erasing the advantage before the QFT even runs. Second, and more subtly, you cannot read the N output amplitudes back out: a measurement collapses the superposition to one single outcome, sampled with probability equal to that outcome's squared amplitude. The QFT is therefore only a net win when a problem is structured so that a single, or a few, measurements of the transformed state reveal exactly the answer you need - typically a periodicity or an eigenphase - without ever requiring the full spectrum in classical memory.

Inside Shor's algorithm and phase estimation

The textbook example is Shor's factoring algorithm. Its hard step is finding the period r of the modular exponential function a^x mod N; a quantum register is loaded with a superposition of the function's outputs for every x, and the QFT is applied to the exponent register. Because the state's amplitude pattern repeats with period r, the QFT concentrates the resulting probability onto outcomes near multiples of the register size divided by r - measure once, run a classical continued-fraction algorithm on the result, and r drops out with high probability. The same mechanism, generalized, is called quantum phase estimation: given a unitary operator and one of its eigenstates, phase estimation uses a QFT to read the corresponding eigenphase to n bits of precision, and it underlies not just Shor's algorithm but quantum chemistry simulation and several linear-algebra quantum algorithms as well.

Frequently asked questions

Try it live

Everything above runs in your browser - open Quantum Fourier Transform and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.