Quantum Fourier Transform (QFT)

What You'll Learn: How the quantum analog of the Fourier transform works — the key subroutine behind Shor's algorithm, phase estimation, and most quantum speedups.

Level: Intermediate | Time: 20 minutes | Qubits: 3 | Framework: Qiskit

Prerequisites: Bell State (superposition and controlled gates)

The Idea

Imagine you hear a chord on a piano. Your ear doesn't perceive it as a single complex sound wave — it decomposes the chord into individual notes (frequencies). That's exactly what a Fourier transform does: it takes a signal in the "time domain" and breaks it into its frequency components.

The Quantum Fourier Transform does the same thing, but on quantum states. It takes a state described in the computational basis (like |101>) and re-expresses it in the frequency basis — revealing periodic structure hidden in the amplitudes.

Why does this matter? Because many hard computational problems — factoring large numbers, finding hidden periodicities, estimating eigenvalues — become easy once you can detect periodicity. The QFT is the tool that exposes it.

The remarkable part: while the best classical algorithm (the Fast Fourier Transform) needs O(N log N) operations on N numbers, the QFT achieves the same transformation using only O(n^2) quantum gates on n qubits — where N = 2^n. That's an exponential speedup in gate count.

How It Works

The Circuit (3-qubit QFT)

CODECopy
     ┌───┐ ┌────────┐ ┌────────┐ ╳
q_0: ┤ H ├─┤ P(pi/2)├─┤ P(pi/4)├─╳───
     └───┘ └───┬────┘ └───┬────┘ │
     ┌───┐     │    ┌─────┴────┐ │
q_1: ┤   ├─────■────┤  P(pi/2) ├─╳───
     │   │          └────┬─────┘
     │   │   ┌───┐       │
q_2: ┤   ├───┤ H ├───────■───────────
     └───┘   └───┘

Step 1: Hadamard on qubit 0

PYTHONCopy
qc.h(0)  # |0> -> (|0> + |1>) / sqrt(2)

The Hadamard gate creates a superposition, splitting qubit 0 into equal parts |0> and |1>. This is the "coarsest" frequency component — it distinguishes even from odd.

Step 2: Controlled-phase rotations on qubit 0

PYTHONCopy
qc.cp(pi/2, 1, 0)  # Phase of pi/2 on q0, controlled by q1
qc.cp(pi/4, 2, 0)  # Phase of pi/4 on q0, controlled by q2

Each controlled-phase gate adds a relative phase to qubit 0 that depends on the state of a "higher" qubit. The angles halve with each step: pi/2, pi/4, pi/8, ... These encode progressively finer frequency information, like going from octaves to semitones to cents in music.

Step 3: Repeat for remaining qubits

PYTHONCopy
qc.h(1)             # Hadamard on qubit 1
qc.cp(pi/2, 2, 1)   # Controlled-phase from qubit 2 to qubit 1
qc.h(2)             # Hadamard on qubit 2

Each qubit gets the same treatment: a Hadamard followed by controlled-phase rotations from all higher qubits. Qubit 1 gets one controlled-phase (from q2). Qubit 2 gets only its Hadamard (no higher qubits remain).

Step 4: SWAP to reverse bit order

PYTHONCopy
qc.swap(0, 2)  # Reverse the qubit ordering

The QFT naturally produces its output in reversed bit order. The final SWAP gates correct this so that qubit 0 holds the most significant bit of the frequency representation. For n qubits, you need floor(n/2) SWAPs.

The Math

QFT Definition

For an n-qubit computational basis state |j>, the QFT maps:

QFT|j> = (1/sqrt(N)) * sum_{k=0}^{N-1} exp(2*pi*i*j*k / N) |k>

where N = 2^n. This is identical to the classical DFT formula, but applied to quantum basis states rather than classical arrays.

Product Representation

The QFT has an elegant product form that directly maps to the circuit:

QFT|j> = (1/sqrt(N)) * tensor_{l=1}^{n} ( |0> + exp(2*pi*i*j / 2^l) |1> )

Each qubit l in the output depends on the last l bits of j. This factored structure is why the QFT can be implemented with only O(n^2) gates — each qubit interacts with at most n-1 others.

Matrix for 2-qubit QFT

CODECopy
QFT_2 = (1/2) * [ 1    1    1    1  ]
                 [ 1    i   -1   -i  ]
                 [ 1   -1    1   -1  ]
                 [ 1   -i   -1    i  ]

The (j,k) entry is omega^(jk) where omega = exp(2pii / N) is the N-th root of unity.

Complexity

The QFT is exponentially faster in gate count. However, the output is a quantum state — you cannot read all 2^n amplitudes directly. This is why the QFT is used as a subroutine within larger algorithms (phase estimation, Shor's) that extract the relevant information through clever measurement schemes.

QFT vs Classical FFT

Expected Output

When you apply QFT to |000> and measure 1024 times, you expect a uniform distribution — all 8 states with roughly equal probability:

This is because QFT|000> = (1/sqrt(8)) * (|000> + |001> + ... + |111>), the equal superposition. The QFT on the all-zeros state is equivalent to applying H to every qubit — but the QFT becomes distinct from parallel Hadamards when applied to non-zero inputs.

Verification: The verify_qft() function also checks the round-trip property: applying QFT then inverse QFT to |000> should recover |000> with probability >95% (it's 100% in theory, limited only by floating-point precision in the simulator).

Running the Circuit

PYTHONCopy
from circuit import run_circuit, verify_qft, create_qft_circuit

# Basic execution — QFT on |000>, returns measurement counts
counts = run_circuit(shots=1024)
print(counts)  # All 8 states with ~128 counts each

# Verification — checks uniform distribution + round-trip
result = verify_qft(shots=8192)
print(result["passed"])  # True
for check in result["checks"]:
    print(f"  {check['name']}: {check['detail']}")

# Create a custom-size QFT
qc = create_qft_circuit(n_qubits=5)

Try It Yourself

1. Non-trivial input: Prepare |001> (apply X to qubit 0) before the QFT. The output should no longer be uniform — you'll see a periodic pattern in the measurement probabilities. Can you predict which states get amplified?

2. Round-trip test: Build a circuit that applies QFT then inverse QFT. Verify that you get back the original state with near-100% probability. Try it with different input states.

3. Scale up: Create a 5-qubit QFT. Count the gates: you should see 5 Hadamards, 10 controlled-phase rotations, and 2 SWAPs. How does the gate count grow as you increase n?

4. Approximate QFT: Remove the smallest-angle controlled-phase gates (e.g., anything smaller than pi/16). Run the circuit and compare the output distribution to the exact QFT. How much error does the approximation introduce? (This is the basis of Coppersmith's "approximate QFT" paper.)

What's Next

• Phase Estimation — Use the QFT to estimate eigenvalues of unitary operators — the gateway to quantum chemistry and optimization algorithms
• Shor's Algorithm — Combine QFT with modular exponentiation to factor large integers in polynomial time (the "killer app" of quantum computing)

References

• Coppersmith, D. (1994). "An approximate Fourier transform useful in quantum computing." arXiv:quant-ph/0201067
• Nielsen, M.A. & Chuang, I.L. Quantum Computation and Quantum Information, Chapter 5: The quantum Fourier transform and its applications.
• Shor, P.W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings of FOCS 1994, pp. 124-134.
• IBM Quantum Learning: Quantum Fourier Transform
• Qiskit Textbook: QFT