Interactive Notes · Note 05

Quantum Fourier Transform

From the classical Discrete Fourier Transform to its quantum analogue: how the QFT maps amplitudes, how to implement it with H and controlled-phase gates, and why it is exponentially faster than the FFT.

6 sections 12 exercises Interactive circuit visualizer

Contents

Section 01

Recalling the Classical Discrete Fourier Transform

Before diving into the quantum version, we need to understand what the Fourier transform does and why it is so useful. The central idea is simple: any signal that oscillates in time can be decomposed into a sum of pure sinusoids at different frequencies. The Fourier transform performs exactly this decomposition.

What is the DFT?

Suppose we have a list of N complex numbers x = (x₀, x₁, …, x_N−1). Think of these as samples of a signal at N equally spaced moments in time. The Discrete Fourier Transform (DFT) converts this time-domain list into a frequency-domain list X = (X₀, X₁, …, X_N−1) via:

Definition — DFT

Forward DFT: X q = 1/\sqrtN Σ k=0 N-1 x k \cdot e j2πkq/N = 1/\sqrtN Σ k=0 N-1 x k \cdot ω N kq Inverse DFT: x k = 1/\sqrtN Σ q=0 N-1 X q \cdot e -j2πkq/N = 1/\sqrtN Σ q=0 N-1 X q \cdot ω N -kq Root of unity: ω N = e j2π/N (a complex number of modulus 1)

Why ω_N? The number ω_N = e^j2π/N is a complex number sitting on the unit circle at angle 2π/N. Raising it to the power k rotates by k steps of angle 2π/N. For N=2: ω₂ = e^jπ = −1. For N=4: ω₄ = e^jπ/2 = j. These specific values make the math beautiful.

Matrix form of the DFT

The DFT is a linear transformation, so it can be written as a matrix multiplication. Writing ω = ω_N for brevity:

X₀ X₁ ⋮ X N-1 = 1/\sqrtN 111 \dots 1 1 ω ω² \dots ω N-1 ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω N-1 ω 2(N-1) \dots ω (N-1)² x₀ x₁ ⋮ x N-1 Compact form: X = F N \cdot x

F_N is a unitary matrix! This is why the DFT can be directly implemented as a quantum gate — unitary matrices are exactly what quantum gates are. The entry at row q, column k is (F_N)_qk = ω_N^kq/√N.

Basis vector notation

Adopting the standard basis vectors u₀ = (1,0,…,0)ᵀ, u₁ = (0,1,0,…)ᵀ, …, u_N−1 = (0,…,0,1)ᵀ, any vector x can be written as:

Decomposition: x = Σ k=0 N-1 x k u k and X = Σ q=0 N-1 X q u q

This notation anticipates the quantum version where u_k will become the ket |k⟩.

Ex 1.1Computing ω₄

For N = 4, compute ω₄ = e^j2π/4 = e^jπ/2. Using Euler's formula e^jθ = cos θ + j sin θ, what is the value? (Enter as "a+bj")

ω₄ =

e^jπ/2 = cos(π/2) + j·sin(π/2) = 0 + j·1 = j

Ex 1.2DFT matrix for N=2

For N = 2 we have ω₂ = e^jπ = −1. Write out the 2×2 DFT matrix F₂ = (1/√2)·((1, 1),(1, ω₂)). What famous quantum gate does F₂ equal?

F₂ =

F₂ = (1/√2)·((1,1),(1,−1)) = H (Hadamard). The 2-point DFT is exactly the Hadamard gate!

Section 02

The Quantum Fourier Transform

The quantum analogue of the DFT acts on quantum states instead of classical vectors. The key idea is that a quantum state |ψ⟩ is itself a vector of amplitudes — so the DFT matrix F_N can be applied to it directly as a unitary gate.

Definition — Quantum Fourier Transform

Input state: |x⟩ = Σ k=0 N-1 x k |k⟩ (amplitudes form the vector x) QFT action: QFT N |x⟩ = |X⟩ = Σ q=0 N-1 X q |q⟩ where X = F N x Compact form: QFT N |ψ⟩ = F N |ψ⟩

The QFT acts on an n-qubit system with N = 2ⁿ.

The circuit representation is:

|ψ⟩ QFT N |φ⟩ = F N |ψ⟩ n qubits in, n qubits out, N = 2 n

Why is this powerful?

Classical DFT: Given a vector of N numbers, the FFT (Fast Fourier Transform) computes the DFT in O(N log N) operations. For N = 2ⁿ this is O(n·2ⁿ) — exponential in the number of bits.

QFT: Computes the same transform using only O(n²) = O((log N)²) quantum gates — a double-exponential improvement in terms of the number of bits.

The catch: The QFT computes the DFT of the amplitude vector, but we cannot directly read out all N amplitudes after the QFT — measuring collapses the state to a single outcome. The power of the QFT emerges when combined cleverly with other operations (like in Shor's algorithm). The QFT is a subroutine, not a standalone tool.

Visualization: a periodic amplitude pattern (left) and its QFT (right). The QFT concentrates amplitude at the frequency of the pattern.

Period P = 4

Ex 2.1Size of QFT

The QFT_N acts on n qubits where N = 2ⁿ. If we use n = 3 qubits, what is N?

N =

Ex 2.2Is QFT unitary?

For the QFT to be a valid quantum gate it must be unitary: F_N^†F_N = I. Given that the rows of F_N form an orthonormal set (because different Fourier basis vectors are orthogonal), does this guarantee unitarity? (yes/no)

Yes. A matrix whose rows form an orthonormal set is unitary by definition. The Fourier basis vectors {e^j2πkq/N/√N} are orthonormal in ℂ^N.

Section 03

QFT on Computational Basis States

To understand how to implement the QFT as a circuit, we first compute what it does to a computational basis state |k⟩. By linearity, once we know this, we know what the QFT does to any state.

Key strategy: It suffices to work out QFT|k⟩ for a generic basis state |k⟩. By linearity of quantum mechanics, QFT(Σ x_k|k⟩) = Σ x_k QFT|k⟩. So understanding basis states gives us everything.

Computing QFT|k⟩

The basis state |k⟩ is a vector with a single 1 at position k. Its DFT amplitudes are X_q = (1/√N) · ω_N^qk, so:

Step 1: QFT|k⟩ = 1/\sqrtN Σ q=0 N-1 ω N qk |q⟩ Step 2: = 1/\sqrtN (|0⟩ + ω N k |1⟩ + ω N 2k |2⟩ + \dots + ω N (N-1)k |N-1⟩)

Product form: Writing k in binary as |k⟩ = |k_n−1…k₁k₀⟩ and using the binary expansion k = k₀ + 2k₁ + … + 2ⁿ⁻¹k_n−1, the QFT output factors into a tensor product of single-qubit states. This is the crucial insight that makes circuit implementation possible!

Binary representation

Write k in binary: k = k₀ + 2k₁ + 4k₂ + … + 2ⁿ⁻¹k_n−1, and represent |k⟩ = |k_n−1…k₁k₀⟩ (MSB first). Then:

Product form: QFT|k⟩ \propto (|0⟩ + ω N k |1⟩) \otimes (|0⟩ + ω N 2k |1⟩) \otimes \dots \otimes (|0⟩ + ω N 2 n-1 k |1⟩) Why factors? Each factor (|0⟩ + ω 2 j k |1⟩) only depends on a few bits of k because ω 2 j k = e j2π\cdot2 j k/N and higher powers of 2 above N wrap around to 1.

Example: N=16, n=4

For a 4-qubit system N=16, the QFT on |k⟩ = |k₃k₂k₁k₀⟩ gives:

QFT|k⟩ \propto (|0⟩ + ω₁₆ 8k |1⟩) \otimes (|0⟩ + ω₁₆ 4k |1⟩) \otimes (|0⟩ + ω₁₆ 2k |1⟩) \otimes (|0⟩ + ω₁₆ k |1⟩) q₃ q₂ q₁ q₀ Key insight: ω₁₆ 8k = e jπk = (-1) k = (-1) k₀ (only depends on the last bit!) This is because 8k/16 = k/2, so only the parity of k matters, which is k₀ mod 2 = k₀.

Fractional binary notation: Define 0.k_ℓk_ℓ+1…k_n−1 = k_ℓ/2 + k_ℓ+1/4 + … Then ω_N^{2^jk} = e^{j2π·0.k_jk_j+1…k_n−1}. The j-th qubit factor only depends on bits k_j through k_n−1 — crucially, NOT on the more significant bits!

Ex 3.1Evaluating ω₈

For N = 8, ω₈ = e^j2π/8 = e^jπ/4. Using cos(π/4) = sin(π/4) = 1/√2, write ω₈ in rectangular form a + bj.

ω₈ =

ω₈ = cos(π/4) + j·sin(π/4) = 1/√2 + j/√2 = (1+j)/√2 ≈ 0.707 + 0.707j

Ex 3.2Bit parity and ω

For N = 8, compute ω₈^4k. Recall ω₈ = e^jπ/4 so ω₈⁴ = e^jπ = −1. Therefore ω₈^4k = (−1)^k. In binary k = k₀ + 2k₁ + 4k₂, which single bit determines (−1)^k?

The bit is:

(−1)^k = (−1)^{k₀+2k₁+4k₂} = (−1)^k₀·((−1)²)^k₁·((−1)⁴)^k₂ = (−1)^k₀·1·1. Only k₀ (the least significant bit) matters!

Section 04

QFT Circuit for N = 4 (2 qubits)

Now we build the actual circuit. For N = 4, n = 2 qubits, and k = k₀ + 2k₁, we have |k⟩ = |k₁k₀⟩. The QFT output factors as:

QFT|k⟩ \propto (|0⟩ + ω₄ 2k |1⟩) \otimes (|0⟩ + ω₄ k |1⟩) Step A: ω₄ 2k = (e j2π/4) 2k = e jπk = (-1) k = (-1) k₀ \cdot((-1) 2) k₁ = (-1) k₀ Only depends on k₀! Step B: k = k₀ + 2k₁, so ω₄ k = ω₄ k₀ \cdotω₄ 2k₁ = ω₄ k₀ \cdot (-1) k₁ Depends on both k₀ and k₁. So QFT|k⟩ \propto (|0⟩ + (-1) k₀ |1⟩) \otimes (|0⟩ + ω₄ k₀ (-1) k₁ |1⟩) = q₁ \otimes q₀

Identifying the gates

Qubit q₁: (|0⟩ + (-1) k₀ |1⟩) \to this is exactly H|k₀⟩! Hadamard maps |0⟩ \to (|0⟩+|1⟩)/\sqrt2 and |1⟩ \to (|0⟩-|1⟩)/\sqrt2. Qubit q₀: After H on |k₁⟩ we get (|0⟩ + (-1) k₁ |1⟩). We then want to multiply the |1⟩ component by ω₄ k₀ = j k₀ — but only when k₀ = 1 . This is a controlled-phase gate!

Definition — Controlled-Phase Gate Ω_N

Ω N = 10 0 ω N Ω N |0⟩ = |0⟩, Ω N |1⟩ = ω N |1⟩

When controlled (applied only when the control qubit is |1⟩), it multiplies the |1⟩ amplitude by ω_N — and does nothing if the control is |0⟩.

Special case: Ω₄ = S gate (phase gate, adds phase j to |1⟩). Ω₂ = Z gate. In general, Ω_2^k is a controlled rotation of angle 2π/2^k around the Z axis.

The N=4 QFT circuit

|k₀⟩ ● H |q₁⟩ |k₁⟩ H Ω₄ |q₀⟩ Note: The Ω₄ gate on wire |k₁⟩ is controlled by |k₀⟩ (the dot ● above). The output is in reverse order : swap gates are needed if you want |q₀⟩ on top.

Step-by-step walkthrough for |k⟩ = |1,1⟩ = |11⟩ (k=3)

Initial: |k₀=1⟩|k₁=1⟩ = |1⟩|1⟩ H on k₁: |1⟩ \otimes H|1⟩ = |1⟩ \otimes (|0⟩-|1⟩)/\sqrt2 Ctrl-Ω₄: Since k₀ = 1, apply Ω₄ to target: |1⟩ \otimes (|0⟩ - j|1⟩)/\sqrt2 (Ω₄ multiplies |1⟩ by j, leaving |0⟩ unchanged) H on k₀: H|1⟩ \otimes (|0⟩ - j|1⟩)/\sqrt2 = (|0⟩-|1⟩)/\sqrt2 \otimes (|0⟩ - j|1⟩)/\sqrt2 Output (q₁,q₀): = |q₁⟩|q₀⟩ as expected (reversed order — swap to fix)

Interactive N=4 QFT circuit. Select an input basis state to trace the signal through each gate.

Input |k⟩ =

Ex 4.1QFT on |00⟩ for N=4

For k=0 (|k⟩ = |00⟩), apply the QFT formula. What should be the probability of each basis state |00⟩, |01⟩, |10⟩, |11⟩?

P(each state) =

QFT|0⟩ = (1/√4)(|0⟩+|1⟩+|2⟩+|3⟩) — uniform superposition. Each amplitude is 1/√4 = 1/2, so each probability is |1/2|² = 1/4.

Section 05

QFT Circuit for N = 8 (3 qubits)

Extending to 3 qubits shows the recursive structure of the QFT. With k = k₀ + 2k₁ + 4k₂ we write |k⟩ = |k₂k₁k₀⟩ and factor:

QFT|k⟩ \propto (|0⟩ + ω₈ 4k |1⟩) \otimes (|0⟩ + ω₈ 2k |1⟩) \otimes (|0⟩ + ω₈ k |1⟩) Simplify ω₈ 4k : ω₈ 4k = e jπk = (-1) k = (-1) k₀ (only k₀ matters) Simplify ω₈ 2k : ω₈ 2k = ω₄ k = ω₄ k₀ \cdot(-1) k₁ (depends on k₀ and k₁) Simplify ω₈ k : ω₈ k = ω₈ k₀ \cdotω₄ k₁ \cdot(-1) k₂ (depends on k₀, k₁, k₂)

So the full factored form is:

QFT|k⟩ \propto (|0⟩ + (-1) k₀ |1⟩) \otimes (|0⟩ + ω₄ k₀ (-1) k₁ |1⟩) \otimes (|0⟩ + ω₈ k₀ ω₄ k₁ (-1) k₂ |1⟩)

Circuit structure

|k₀⟩ ● ● H |q₂⟩ |k₁⟩ ● H Ω₄ |q₁⟩ |k₂⟩ H Ω₄ Ω₈ |q₀⟩ The ● symbols indicate control wires coming from above. Ω₄ = S (phase by j), Ω₈ = T (phase by e jπ/4). Output in reverse order.

Recursive structure: Notice that QFT₈ contains QFT₄ as a sub-circuit! The bottom two wires (|k₁⟩, |k₂⟩) form a QFT₄ structure, and then |k₀⟩ adds one more stage. In general, QFT_2ⁿ contains QFT_2ⁿ⁻¹ — this is why the algorithm is efficient.

General pattern for n qubits

For an n-qubit QFT with input |k_n−1…k₁k₀⟩:

Wire j (from top): receives H, then controlled-Ω 4, Ω 8, \dots, Ω 2 j+1 gates controlled by wires above (k₀ is the topmost control wire) Phase gates: Ω N where N = 2 m means a phase of ω 2 m = e j2π/2 m applied to |1⟩

Ex 5.1Identifying Ω₄ = S gate

The gate Ω₄ applies phase ω₄ = j to |1⟩. What standard single-qubit gate has matrix diag(1, j) and therefore equals Ω₄?

Gate =

The S gate (phase gate) has matrix diag(1, j) = diag(1, ω₄). So Ω₄ = S.

Ex 5.2Identifying Ω₈ = T gate

Similarly, Ω₈ applies phase ω₈ = e^jπ/4 to |1⟩. What standard gate equals Ω₈? (Hint: look at the T (π/8) gate from the earlier notes.)

Gate =

The T gate (π/8 gate) has matrix diag(1, e^jπ/4) = diag(1, ω₈). So Ω₈ = T.

Section 06

Complexity of the QFT

The QFT's exponential speedup over the classical FFT is one of the most striking results in quantum computing. Let us count the gates precisely.

Gate count

# Hadamard gates: n (one per qubit, applied once) # Controlled-Ω gates: Wire 0 (|k₂⟩): 1 controlled gate (Ω₄) Wire 1 (|k₁⟩): 2 controlled gates (Ω₄, Ω₈) Wire j: j controlled gates Total: 1 + 2 + \dots + (n-1) = n(n-1)/2 Total gates: n + n(n-1)/2 = n(n+1)/2 \approx n²/2 (quadratic in n!)

Complexity comparison

QFT N : O(n²) = O((log₂ N)²) gates with n = log₂ N qubits Classical FFT N : O(N log₂ N) = O(n \cdot 2 n) operations (exponential in n) Speedup: n \cdot 2 n vs n² \to exponential speedup! For n = 1000 (an RSA-like problem): 1000 \times 2¹⁰⁰⁰ vs 10⁶ gates

Complexity comparison: QFT gates (blue, n²) vs FFT operations (red, n·2ⁿ). Drag the slider to see the gap grow.

n (qubits) = 5

Important caveat: Despite its O(n²) gate complexity, the QFT does not directly give exponential speedup over FFT for all tasks. Why? Because after the QFT, measuring the state gives only a single random sample from the output distribution — not all N amplitudes simultaneously. The QFT only provides a speedup when used as a subroutine in a cleverly designed algorithm (like Shor's period-finding) where a single sample is enough.

Ex 6.1Gate count for n=4

For n = 4 qubits (N = 16), how many total gates (H + controlled-Ω) does the QFT require?

Total gates =

n = 4. H gates: 4. Controlled-Ω gates: 1+2+3 = 6. Total: 4 + 6 = 10. Formula: n(n+1)/2 = 4·5/2 = 10.

Ex 6.2Classical vs quantum for n=10

For n = 10 (N = 1024): how many operations does the classical FFT need (≈ N log₂ N)? How many gates for QFT (≈ n²)? Compute the ratio FFT/QFT.

FFT ops ≈ QFT gates =

FFT: N log₂N = 1024 × 10 = 10240. QFT: n² = 100. Ratio: 102.4 — QFT uses ~100x fewer operations even for small n!