Skip to content

Lesson 18: The Quantum Fourier Transform

18.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Define the QFT and relate it to the classical DFT.
  2. Prove that the QFT is unitary.
  3. Derive the product (tensor-factored) form of the QFT.
  4. Construct the \(O(n^2)\) QFT circuit from Hadamard and controlled-phase gates.
  5. Explain honestly why QFT does not speed up ordinary signal processing.

18.2 From DFT to QFT

The classical DFT

Given a vector \((x_0,\dots,x_{N-1})\), the Discrete Fourier Transform is

\[ y_k = \frac{1}{\sqrt N}\sum_{j=0}^{N-1} x_j\, e^{2\pi i jk/N}, \qquad k = 0,\dots,N-1. \]

Naively \(O(N^2)\); the Fast Fourier Transform does it in \(O(N\log N)\).

The QFT

Take \(N = 2^n\). The Quantum Fourier Transform is the linear operator acting on basis states as

\[ \boxed{\ \mathrm{QFT}_N\,|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\,|k\rangle\ } \]

and extended linearly. On a general state:

\[ \mathrm{QFT}\left(\sum_j x_j|j\rangle\right) = \sum_k y_k|k\rangle, \qquad y_k = \frac{1}{\sqrt N}\sum_j x_j e^{2\pi i jk/N} . \]

It is the same transform, applied to the amplitude vector instead of a data array.

Matrix form

Let \(\omega = e^{2\pi i/N}\) (a primitive \(N\)-th root of unity). Then

\[ \mathrm{QFT}_N = \frac{1}{\sqrt N}\begin{pmatrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \omega & \omega^2 & \cdots & \omega^{N-1}\\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)}\\ \vdots & & & \ddots & \vdots\\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots & \omega^{(N-1)^2}\end{pmatrix}, \qquad (\mathrm{QFT})_{kj} = \frac{\omega^{jk}}{\sqrt N} . \]

Special case \(N = 2\): \(\omega = e^{i\pi} = -1\), so

\[ \mathrm{QFT}_2 = \frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} = H . \]

The Hadamard gate is the single-qubit QFT. This is why \(H^{\otimes n}\) served as the "Fourier transform" in Deutsch–Jozsa, Bernstein–Vazirani and Simon — those algorithms work over \((\mathbb{Z}_2)^n\), whose Fourier transform is exactly \(H^{\otimes n}\).

Unitarity

\[ \big(\mathrm{QFT}^\dagger \mathrm{QFT}\big)_{jl} = \sum_k \overline{(\mathrm{QFT})_{kj}}\,(\mathrm{QFT})_{kl} = \frac{1}{N}\sum_{k=0}^{N-1}\omega^{-jk}\omega^{kl} = \frac{1}{N}\sum_{k=0}^{N-1}\omega^{k(l-j)} \]

This is a geometric series. If \(l = j\) every term is 1, giving \(\frac{N}{N} = 1\). If \(l\ne j\), put \(d = l-j \not\equiv 0 \pmod N\):

\[ \sum_{k=0}^{N-1}\omega^{kd} = \frac{\omega^{Nd}-1}{\omega^{d}-1} = \frac{1-1}{\omega^d-1} = 0 \]

since \(\omega^N = 1\). Hence \(\mathrm{QFT}^\dagger\mathrm{QFT} = I\): the QFT is unitary and can be implemented as a quantum circuit. \(\blacksquare\)

The inverse is

\[ \mathrm{QFT}^{-1}|j\rangle = \frac{1}{\sqrt N}\sum_k e^{-2\pi ijk/N}|k\rangle . \]

18.3 The Product Form

This is the derivation that turns an \(N\times N\) matrix into an \(O(n^2)\)-gate circuit.

Binary notation. Write \(k = k_1k_2\cdots k_n\) in binary, so \(k = \sum_{l=1}^{n}k_l\,2^{n-l}\). Define the binary fraction

\[ 0.k_lk_{l+1}\cdots k_n \;=\; \frac{k_l}{2} + \frac{k_{l+1}}{4} + \cdots + \frac{k_n}{2^{n-l+1}} . \]

Derivation. Start from the definition with \(N = 2^n\):

\[ \mathrm{QFT}|j\rangle = \frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1} e^{2\pi i jk/2^n}|k\rangle \]

Substitute \(k/2^n = \sum_{l=1}^n k_l 2^{-l}\):

\[ = \frac{1}{2^{n/2}}\sum_{k_1=0}^{1}\cdots\sum_{k_n=0}^{1} \ \bigotimes_{l=1}^{n} e^{2\pi i j k_l 2^{-l}}|k_l\rangle \]

The sum over each \(k_l\) is independent, so the whole thing factorises:

\[ = \frac{1}{2^{n/2}}\bigotimes_{l=1}^{n}\left(\sum_{k_l\in\{0,1\}} e^{2\pi ijk_l2^{-l}}|k_l\rangle\right) = \bigotimes_{l=1}^{n}\ \frac{|0\rangle + e^{2\pi i j/2^{l}}|1\rangle}{\sqrt2} \]

Finally, \(e^{2\pi ij/2^l}\) depends only on the fractional part of \(j/2^l\), which is \(0.j_{n-l+1}\cdots j_n\). Writing it out:

\[ \boxed{\ \mathrm{QFT}|j_1j_2\cdots j_n\rangle = \frac{\big(|0\rangle + e^{2\pi i\,0.j_n}|1\rangle\big) \big(|0\rangle + e^{2\pi i\,0.j_{n-1}j_n}|1\rangle\big)\cdots \big(|0\rangle + e^{2\pi i\,0.j_1j_2\cdots j_n}|1\rangle\big)}{2^{n/2}}\ } \]

Read this carefully — it is remarkable. The QFT of any computational basis state is a product state: no entanglement is created. Each output qubit is on the equator of the Bloch sphere, at an azimuthal angle given by successively finer binary fractions of \(j\).

Note also that qubit 1 of the output depends on \(j_n\) alone, while qubit \(n\) depends on all of \(j\) — so the output emerges in reversed order, which is why the circuit ends with SWAPs.

18.4 The Circuit

Gates required

  • Hadamard \(H\).
  • Controlled phase \(CR_m\), where
\[ R_m = \begin{pmatrix}1 & 0\\ 0 & e^{2\pi i/2^{m}}\end{pmatrix} . \]

Note \(R_1 = Z\), \(R_2 = S\), \(R_3 = T\).

The construction

j1 --[H]--[R2]--[R3]-- ... --[Rn]------------------------------ x
            |     |            |
j2 ---------*-----|------------|----[H]--[R2]-- ... --[R(n-1)]-- x
                  |            |          |               |
j3 ---------------*------------|----------*---------------|-----
                               |                          |
jn ----------------------------*--------------------------*-----
                                                            then SWAPs

Algorithm.

for l = 1 to n:
    apply H to qubit l
    for m = 2 to n-l+1:
        apply controlled-R_m  (control = qubit l+m-1, target = qubit l)
reverse the qubit order with floor(n/2) SWAP gates

Why it works. \(H\) on qubit \(l\) produces \(\frac{1}{\sqrt2}(|0\rangle + e^{2\pi i\,0.j_l}|1\rangle)\) — it writes the first binary digit into the phase. Each subsequent controlled-\(R_m\) adds the next digit \(j_{l+m-1}/2^m\), building up the binary fraction \(0.j_lj_{l+1}\cdots j_n\) one bit at a time.

Gate count

\[ n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2} = O(n^2) \ \text{gates}, \ \ \text{plus } \lfloor n/2\rfloor \text{ SWAPs.} \]
Classical FFT QFT
Input size \(N = 2^n\) numbers \(n\) qubits
Operations \(O(N\log N) = O(2^n n)\) \(O(n^2)\)
Output all \(N\) coefficients, readable a quantum state; one sample only

The QFT is exponentially faster than the FFT — \(O(n^2)\) versus \(O(2^nn)\).

The honest caveat

The QFT does not speed up signal processing. Two reasons:

  1. You cannot read the output. Measuring gives one \(k\) sampled from \(|y_k|^2\). Extracting all \(N\) coefficients needs \(\Omega(N)\) repetitions, wiping out the advantage.
  2. You cannot load the input efficiently. Preparing \(\sum_j x_j|j\rangle\) from classical data generally costs \(O(N)\) operations.

The QFT is useful precisely when the answer is a single global feature of the spectrum — such as the period — that can be read from one sample. That is exactly the situation in phase estimation and Shor's algorithm.

Approximate QFT

Phases \(e^{2\pi i/2^m}\) for large \(m\) are exponentially small rotations, indistinguishable from identity on noisy hardware. Dropping all \(R_m\) with \(m > \log_2(n/\epsilon)\) gives the approximate QFT with error \(\epsilon\), using only \(O(n\log n)\) gates. In practice this is what is implemented, and it also improves accuracy on NISQ devices by removing gates that contribute more noise than signal.

18.5 Solved Problems

Problem 1 — QFT on 2 qubits, matrix and action

Write \(\mathrm{QFT}_4\) explicitly and compute \(\mathrm{QFT}_4|2\rangle\).

Solution. \(N = 4\), \(\omega = e^{2\pi i/4} = i\).

\[ \mathrm{QFT}_4 = \frac12\begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & i\end{pmatrix} \]

(using \(i^2=-1\), \(i^3=-i\), \(i^4=1\), \(i^6 = -1\), \(i^9 = i\)).

\(\mathrm{QFT}_4|2\rangle\) is the third column:

\[ \mathrm{QFT}_4|2\rangle = \frac12\big(|0\rangle - |1\rangle + |2\rangle - |3\rangle\big) \]

Verify with the product form. \(j = 2 = 10_2\), so \(j_1 = 1, j_2 = 0\).

\[ \mathrm{QFT}|10\rangle = \frac{\big(|0\rangle + e^{2\pi i\,0.j_2}|1\rangle\big) \big(|0\rangle + e^{2\pi i\,0.j_1j_2}|1\rangle\big)}{2} \]

\(0.j_2 = 0.0 = 0\), so the first factor is \(|0\rangle + |1\rangle\). \(0.j_1j_2 = 0.10_2 = \frac12\), so \(e^{2\pi i\cdot\frac12} = e^{i\pi} = -1\), and the second factor is \(|0\rangle - |1\rangle\).

\[ = \frac12\big(|0\rangle+|1\rangle\big)\big(|0\rangle - |1\rangle\big) = \frac12\big(|00\rangle - |01\rangle + |10\rangle - |11\rangle\big) \ \checkmark \]

which matches (with \(|00\rangle=|0\rangle\), \(|01\rangle=|1\rangle\), etc.).

Problem 2 — The QFT of a periodic state

Let \(N = 8\) and \(|\psi\rangle = \frac12\big(|0\rangle+|2\rangle+|4\rangle+|6\rangle\big)\) (period 2). Compute \(\mathrm{QFT}_8|\psi\rangle\) and interpret.

Solution. \(\omega = e^{2\pi i/8} = e^{i\pi/4}\).

\[ \mathrm{QFT}_8|\psi\rangle = \frac12\cdot\frac{1}{\sqrt8}\sum_{k=0}^{7} \left[\sum_{j\in\{0,2,4,6\}}\omega^{jk}\right]|k\rangle \]

Inner sum, with \(\omega^{2k} = e^{i\pi k/2} = i^{k}\):

\[ S_k = \sum_{m=0}^{3} \left(i^{k}\right)^{m} = 1 + i^k + i^{2k} + i^{3k} \]

This geometric series equals \(4\) when \(i^k = 1\) (i.e. \(k \equiv 0 \bmod 4\)) and \(0\) otherwise:

\(k\) \(i^k\) \(S_k\)
0 1 4
1 \(i\) 0
2 \(-1\) 0
3 \(-i\) 0
4 1 4
5,6,7 — 0
\[ \mathrm{QFT}_8|\psi\rangle = \frac{1}{2\sqrt8}\big(4|0\rangle + 4|4\rangle\big) = \frac{1}{\sqrt2}\big(|0\rangle + |4\rangle\big) \]

Interpretation. The input had period \(p = 2\) in the "time" domain; the output is supported on multiples of \(N/p = 8/2 = 4\). Measuring returns \(0\) or \(4\), each with probability \(\frac12\), and \(4 = N/p\) reveals \(p = 8/4 = 2\).

This is the entire mechanism of Shor's algorithm: period in → multiples of \(N/p\) out.

Problem 3 — Building the 3-qubit QFT circuit

List the exact gate sequence for \(\mathrm{QFT}_8\) and count the gates.

Solution.

qubit 1: H, then CR2 (control q2), then CR3 (control q3)
qubit 2: H, then CR2 (control q3)
qubit 3: H
finally: SWAP(q1, q3)

Explicitly, in order:

# Gate Target Control Phase applied
1 \(H\) \(q_1\) — —
2 \(CR_2\) \(q_1\) \(q_2\) \(e^{2\pi i/4} = i\)
3 \(CR_3\) \(q_1\) \(q_3\) \(e^{2\pi i/8}\)
4 \(H\) \(q_2\) — —
5 \(CR_2\) \(q_2\) \(q_3\) \(i\)
6 \(H\) \(q_3\) — —
7 SWAP \(q_1, q_3\) — —

Count: \(3 + 3 = 6\) gates (3 Hadamards + 3 controlled-phases) plus 1 SWAP.

Check against the formula: \(\frac{n(n+1)}{2} = \frac{3\times4}{2} = 6\) ✓, and \(\lfloor 3/2 \rfloor = 1\) SWAP ✓.

Compare: the classical FFT on 8 points needs \(8\log_2 8 = 24\) complex operations. The QFT needs 6 gates. The gap grows explosively: for \(n = 20\) (\(N = 10^6\)), the FFT needs \(2\times10^{7}\) operations while the QFT needs 210 gates.

Problem 4 — QFT of a shifted state (the shift theorem)

Show that \(\mathrm{QFT}_N|j_0\rangle\) and \(\mathrm{QFT}_N|j_0 + s\rangle\) (mod \(N\)) differ only by phases, so that measurement statistics are identical. Explain the consequence for Shor's algorithm.

Solution.

\[ \mathrm{QFT}|j_0+s\rangle = \frac{1}{\sqrt N}\sum_k e^{2\pi i(j_0+s)k/N}|k\rangle = \frac{1}{\sqrt N}\sum_k e^{2\pi ij_0k/N}\,e^{2\pi isk/N}|k\rangle \]

Each amplitude is multiplied by \(e^{2\pi isk/N}\), which has modulus 1. Therefore

\[ \big|\langle k|\mathrm{QFT}|j_0+s\rangle\big|^2 = \frac{1}{N} = \big|\langle k|\mathrm{QFT}|j_0\rangle\big|^2 . \]

Statistics are identical. A shift in the input becomes a phase ramp in the output, invisible to measurement.

Consequence for Shor. After measuring the output register in Shor's algorithm, the input register is in a state like

\[ \frac{1}{\sqrt m}\sum_{t=0}^{m-1}|x_0 + tr\rangle \]

— a periodic comb with period \(r\) but an unknown random offset \(x_0\). This theorem shows that \(x_0\) affects only phases, never probabilities. That is exactly why Shor's algorithm can afford to throw away the measurement of the output register. (It is also the same mechanism that let Simon's algorithm work despite the random \(x_0\) — see L15 §3.2.)

Problem 5 — QFT of a single basis state versus a superposition

Compute \(\mathrm{QFT}_4|0\rangle\) and \(\mathrm{QFT}_4\big(\frac{1}{2}\sum_j|j\rangle\big)\), and explain the duality.

Solution.

(a) From the first column of the matrix:

\[ \mathrm{QFT}_4|0\rangle = \frac12\big(|0\rangle+|1\rangle+|2\rangle+|3\rangle\big) \]

A perfectly localised input gives a perfectly uniform output.

(b) Now the uniform input \(|\psi\rangle = \frac12\sum_{j=0}^{3}|j\rangle\):

\[ \mathrm{QFT}|\psi\rangle = \frac12\cdot\frac12\sum_k\left[\sum_{j=0}^{3}i^{jk}\right]|k\rangle \]

The bracket is \(\sum_{j}i^{jk}\), a geometric series equal to 4 when \(k = 0\) and 0 otherwise (same argument as in §1.4):

\[ \mathrm{QFT}|\psi\rangle = \frac{4}{4}|0\rangle = |0\rangle \]

Duality. Delta function ↔ uniform; uniform ↔ delta function. This is the discrete uncertainty principle: a state cannot be sharply localised in both the computational basis and the Fourier basis. The product of the two "widths" is bounded below.

Connection to earlier lessons. For \(n=1\) this is just \(H|0\rangle = |+\rangle\) and \(H|+\rangle = |0\rangle\) — the QFT generalises the Hadamard's amplitude↔phase exchange to \(\mathbb{Z}_N\).

18.6 Practice Problems

  1. Write out \(\mathrm{QFT}_8\)'s first two rows explicitly using \(\omega = e^{i\pi/4}\).
  2. Compute \(\mathrm{QFT}_4|1\rangle\) using both the matrix and the product form.
  3. Compute the QFT of \(\frac{1}{\sqrt2}(|0\rangle + |4\rangle)\) for \(N=8\). [Ans: supported on even \(k\)]
  4. How many gates does \(\mathrm{QFT}_{1024}\) need? [Ans: \(n=10\), so 55 gates + 5 SWAPs]
  5. Verify that \(R_2 = S\) and \(R_3 = T\).
  6. Prove that \(\mathrm{QFT}^4 = I\) up to a permutation (the classical DFT has period 4).
  7. Explain in two sentences why the QFT cannot accelerate JPEG compression.

18.7 Summary

  • \(\mathrm{QFT}_N|j\rangle = \frac{1}{\sqrt N}\sum_k e^{2\pi ijk/N}|k\rangle\); it is the DFT applied to amplitudes, and it is unitary (proved by the geometric-series/root-of-unity argument).
  • \(\mathrm{QFT}_2 = H\), which is why \(H^{\otimes n}\) served as the Fourier transform in Deutsch–Jozsa, Bernstein–Vazirani and Simon.
  • Product form: the QFT of any basis state factorises into \(n\) single-qubit states with phases given by binary fractions of \(j\) — no entanglement, and output in reversed qubit order.
  • Circuit: \(H\) + controlled-\(R_m\) in a triangular pattern, \(O(n^2)\) gates versus the FFT's \(O(2^nn)\); the approximate QFT needs only \(O(n\log n)\).
  • QFT does not accelerate signal processing — you cannot read all outputs or load all inputs. It is useful only when a single global feature (the period) is wanted.
  • Period \(p\) in ⟶ support on multiples of \(N/p\) out. A shift in the input becomes a phase ramp, invisible to measurement — this is what makes Shor robust to the unknown offset.

Next lesson: L19 — Quantum phase estimation.

Practise now: unit2-algorithms-lab.html → QFT Explorer: enter any amplitude vector or set a period, apply the QFT, and see the magnitude and phase spectra side by side.