Before jumping into the quantum version, we need to understand the classical Discrete Fourier Transform. The DFT maps a vector of \(N\) complex numbers to another vector of \(N\) complex numbers:
$$y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \, \omega_N^{jk}$$
where \(\omega_N = e^{2\pi i/N}\) is the primitive \(N\)-th root of unity. Note the key property: \(\omega_N^N = 1\), so the roots of unity cycle.
The DFT can be written as matrix multiplication \(\vec{y} = F_N \vec{x}\), where the DFT matrix \(F_N\) has entries:
$$(F_N)_{jk} = \frac{1}{\sqrt{N}} \omega_N^{jk}$$
\(F_N F_N^\dagger = I\). This is what makes the DFT a valid quantum gate — unitarity is the only requirement for a quantum operation. The inverse DFT is simply \(F_N^\dagger\), which has entries \(\frac{1}{\sqrt{N}} \omega_N^{-jk}\).
For \(N = 2\), we have \(\omega_2 = e^{2\pi i/2} = e^{i\pi} = -1\). The DFT matrix is:
$$F_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = H$$
The single-qubit QFT is the Hadamard gate. This is not a coincidence — the Hadamard was always "secretly" a Fourier transform over \(\mathbb{Z}_2\).
For \(N = 4\), we have \(\omega_4 = e^{2\pi i/4} = e^{i\pi/2} = i\). The DFT matrix is:
$$F_4 = \frac{1}{2}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix}$$
Verify: each row is orthogonal to every other row (take the inner product and check it equals zero). Each row has norm 1 (with the \(\frac{1}{2}\) prefactor). So \(F_4\) is indeed unitary.
The Quantum Fourier Transform applies the DFT matrix to the amplitudes of a quantum state. If a state is written in the computational basis as \(\ket{\psi} = \sum_x \alpha_x \ket{x}\), then:
$$\text{QFT}\ket{\psi} = \sum_y \beta_y \ket{y} \quad \text{where} \quad \beta_y = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \alpha_x \, \omega_N^{xy}$$
On a single computational basis state:
$$\text{QFT}\ket{x} = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \omega_N^{xy} \ket{y} = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2\pi i xy/N} \ket{y}$$
We now work with \(N = 2^n\) (since we have \(n\) qubits). The QFT on computational basis states is:
$$\text{QFT}\ket{x} = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} e^{2\pi i xy/2^n} \ket{y}$$
The magic of the QFT circuit comes from rewriting this sum as a tensor product. Write \(x\) in binary as \(x = x_1 x_2 \ldots x_n\) (where \(x_1\) is the most significant bit), and use the binary fraction notation:
$$0.x_\ell x_{\ell+1} \ldots x_m = \frac{x_\ell}{2} + \frac{x_{\ell+1}}{4} + \cdots + \frac{x_m}{2^{m-\ell+1}}$$
Through algebraic manipulation (splitting the sum over \(y = y_1 y_2 \ldots y_n\) into \(n\) independent sums over each bit \(y_k\)), we arrive at the product representation:
$$\text{QFT}\ket{x_1 x_2 \ldots x_n} = \frac{1}{\sqrt{2^n}} \bigotimes_{k=1}^{n} \left(\ket{0} + e^{2\pi i \, 0.x_{n-k+1} \ldots x_n}\ket{1}\right)$$
Written out explicitly for each qubit:
$$\text{QFT}\ket{x} = \frac{1}{\sqrt{2^n}} \left(\ket{0} + e^{2\pi i \, 0.x_n}\ket{1}\right) \otimes \left(\ket{0} + e^{2\pi i \, 0.x_{n-1}x_n}\ket{1}\right) \otimes \cdots \otimes \left(\ket{0} + e^{2\pi i \, 0.x_1 x_2 \ldots x_n}\ket{1}\right)$$
Each output qubit's state depends on the input \(x\) only through a phase rotation. The \(k\)-th output qubit gets a phase of \(e^{2\pi i \, x/2^k}\). Since each qubit can be prepared independently (up to controlled rotations from other qubits that determine the binary fraction), we can build the QFT with a circuit that acts qubit-by-qubit.
Without the product form, implementing the QFT would require a single \(2^n \times 2^n\) unitary — exponentially large. The product form reduces it to \(O(n^2)\) individual gates.
Start from the definition and write \(y\) in binary \(y = y_1 y_2 \ldots y_n\), so \(y = \sum_{k=1}^n y_k 2^{n-k}\):
$$\text{QFT}\ket{x} = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1} e^{2\pi i xy/2^n} \ket{y}$$
Substitute \(y = \sum_k y_k 2^{n-k}\):
$$= \frac{1}{\sqrt{2^n}} \sum_{y_1=0}^{1} \cdots \sum_{y_n=0}^{1} e^{2\pi i x \sum_k y_k 2^{n-k}/2^n} \ket{y_1 \ldots y_n}$$
The exponent factors: \(e^{2\pi i x \sum_k y_k / 2^k} = \prod_k e^{2\pi i x y_k / 2^k}\). And \(\ket{y_1 \ldots y_n} = \ket{y_1} \otimes \cdots \otimes \ket{y_n}\). So the whole sum factors into a tensor product:
$$= \frac{1}{\sqrt{2^n}} \bigotimes_{k=1}^{n} \left( \sum_{y_k=0}^{1} e^{2\pi i x y_k / 2^k} \ket{y_k} \right) = \frac{1}{\sqrt{2^n}} \bigotimes_{k=1}^{n} \left(\ket{0} + e^{2\pi i x/2^k}\ket{1}\right)$$
Finally, note that \(e^{2\pi i x/2^k}\) only depends on the last \(k\) bits of \(x\) (since \(e^{2\pi i \cdot \text{integer}} = 1\)), which gives us the binary fraction form \(0.x_{n-k+1}\ldots x_n\).
Think of the Fourier basis representation as a clock analogy:
This is like clock hands: the "seconds hand" (least significant Fourier qubit) moves slowly, while the "milliseconds hand" (most significant Fourier qubit) spins rapidly. The state \(\ket{0} + e^{2\pi i \cdot 0.x_n}\ket{1}\) only cares about the last bit of \(x\) — it flips between \(\ket{+}\) and \(\ket{-}\) with each increment. The deeper qubits encode finer and finer phase information.
The product representation tells us exactly how to build the circuit. We need two types of gates:
Notable special cases: \(R_1 = Z\), \(R_2 = S\) (phase gate), \(R_3 = T\) (\(\pi/8\) gate).
The circuit processes qubits from top to bottom. For an \(n\)-qubit input \(\ket{x_1 x_2 \ldots x_n}\):
For \(n = 3\), the circuit (before SWAPs) looks like:
&ket;x₁⟩ ─── H ── R₂ ── R₃ ──────────────────── ×
│ │ │
&ket;x₂⟩ ──────── •──── │──── H ── R₂ ────────── │
│ │ │
&ket;x₃⟩ ───────────── •──────── •──── H ──── ×
Let's walk through what each gate does:
The total state (after SWAP) is:
$$\frac{1}{\sqrt{8}} \left(\ket{0} + e^{2\pi i \cdot 0.x_3}\ket{1}\right) \otimes \left(\ket{0} + e^{2\pi i \cdot 0.x_2 x_3}\ket{1}\right) \otimes \left(\ket{0} + e^{2\pi i \cdot 0.x_1 x_2 x_3}\ket{1}\right)$$
which matches the product representation of the QFT.
Total: \(n + (n-1) + \cdots + 1 + \lfloor n/2 \rfloor = \frac{n(n+1)}{2} + \lfloor n/2 \rfloor = O(n^2)\) gates.
Compare to the classical Fast Fourier Transform (FFT): \(O(N \log N) = O(n \cdot 2^n)\) operations. The QFT is exponentially faster.
The QFT is exponentially faster, but you can't read out the full Fourier-transformed amplitudes. Measuring gives you one sample from the output distribution. The power of the QFT comes from using it as a subroutine inside larger algorithms (like QPE or Shor's), where that single measurement reveals exactly the information you need.
The simplest case: \(\text{QFT}\ket{0} = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{0} \ket{y} = \frac{1}{\sqrt{N}} \sum_y \ket{y} = \ket{+}^{\otimes n}\).
The QFT of \(\ket{0}\) is the uniform superposition. This makes sense: in the Fourier basis, the "zero frequency" component is the uniform (DC) signal.
Suppose we have a state that is an equal superposition over evenly spaced computational basis states with spacing \(r\) (assuming \(r\) divides \(N\)):
$$\ket{\psi_{\text{periodic}}} = \sqrt{\frac{r}{N}} \sum_{j=0}^{N/r-1} \ket{j \cdot r}$$
The QFT maps this to another periodic state with spacing \(N/r\):
$$\text{QFT}\ket{\psi_{\text{periodic}}} = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \ket{k \cdot N/r}$$
This is the quantum version of the classical fact that the Fourier transform of a periodic signal with period \(r\) has peaks at multiples of the fundamental frequency \(N/r\). Measuring the output gives a random multiple of \(N/r\), from which you can extract \(r\). This is exactly how Shor's algorithm finds the period of modular exponentiation.
Apply the QFT definition:
$$\text{QFT}\left(\sqrt{\frac{r}{N}} \sum_{j=0}^{N/r-1} \ket{jr}\right) = \sqrt{\frac{r}{N}} \cdot \frac{1}{\sqrt{N}} \sum_{j=0}^{N/r-1} \sum_{y=0}^{N-1} e^{2\pi i \cdot jr \cdot y/N} \ket{y}$$
Swap the sums and examine the inner sum over \(j\):
$$\sum_{j=0}^{N/r-1} e^{2\pi i \cdot jr \cdot y/N} = \sum_{j=0}^{N/r-1} \left(e^{2\pi i r y/N}\right)^j$$
This is a geometric series. It equals \(N/r\) when \(e^{2\pi i ry/N} = 1\) (i.e., when \(y\) is a multiple of \(N/r\)), and equals 0 otherwise (the terms cancel). So only the values \(y = k \cdot N/r\) for \(k = 0, 1, \ldots, r-1\) survive, each contributing \(N/r\). The overall coefficient becomes \(\sqrt{r/N} \cdot (1/\sqrt{N}) \cdot (N/r) = 1/\sqrt{r}\).
Since \(F_N\) is unitary, its inverse is its conjugate transpose \(F_N^\dagger = F_N^{-1}\):
$$\text{QFT}^{-1}\ket{y} = \text{QFT}^\dagger\ket{y} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} e^{-2\pi i xy/N} \ket{x}$$
The only difference from the forward QFT is the sign of the exponent (minus instead of plus).
To get the inverse QFT circuit:
Equivalently: SWAPs first, then process qubits in reverse order (\(n\) to 1), with each rotation using \(-2\pi/2^k\) instead of \(+2\pi/2^k\).
In quantum algorithms, the QFT is typically used in its inverse form. The forward QFT encodes information into phases (done implicitly by the algorithm structure). The inverse QFT decodes those phases back into computational basis states that can be measured. Think of it as: the algorithm creates a state that "looks like" \(\text{QFT}\ket{\text{answer}}\), and then \(\text{QFT}^\dagger\) recovers \(\ket{\text{answer}}\).
QPE is arguably the most important subroutine in quantum computing. It underlies Shor's factoring algorithm, quantum simulation, and many other applications.
Given: A unitary operator \(U\) and one of its eigenstates \(\ket{\psi}\) satisfying \(U\ket{\psi} = e^{2\pi i\theta}\ket{\psi}\).
Find: The eigenvalue phase \(\theta \in [0, 1)\).
We have access to controlled-\(U^{2^j}\) operations (controlled versions of \(U\) raised to powers of 2), and we use \(t\) "counting qubits" to store the estimate.
The circuit has two registers:
&ket;0⟩ ─── H ────────────────── ● ────────────── QFT† ─── Measure
&ket;0⟩ ─── H ──────────── ● ──── │ ────────────── QFT† ─── Measure
&ket;0⟩ ─── H ────── ● ──── │ ──── │ ────────────── QFT† ─── Measure
│ │ │
&ket;ψ⟩ ──────────── U¹ ── U² ── U⁴ ──────────────────────────────
The steps are:
Step 1: Hadamard on counting register
$$\ket{0}^{\otimes t}\ket{\psi} \xrightarrow{H^{\otimes t}} \frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} \ket{k} \ket{\psi}$$
Step 2: Controlled-\(U\) operations
The controlled-\(U^{2^j}\) gate, controlled by counting qubit \(j\), acts as:
$$\ket{0}_j\ket{\psi} \to \ket{0}_j\ket{\psi} \qquad \ket{1}_j\ket{\psi} \to \ket{1}_j U^{2^j}\ket{\psi} = e^{2\pi i \theta \cdot 2^j} \ket{1}_j\ket{\psi}$$
Because \(\ket{\psi}\) is an eigenstate, \(U^{2^j}\ket{\psi} = (e^{2\pi i\theta})^{2^j}\ket{\psi} = e^{2\pi i \theta \cdot 2^j}\ket{\psi}\). The eigenstate is unchanged — all the information goes into the phase of the counting qubit. This is phase kickback again.
After all \(t\) controlled operations, counting qubit \(j\) has picked up phase \(e^{2\pi i \theta \cdot 2^j}\) on its \(\ket{1}\) component. The combined state is:
$$\frac{1}{\sqrt{2^t}} \sum_{k=0}^{2^t-1} e^{2\pi i \theta k} \ket{k} \ket{\psi}$$
The counting register is now in the state \(\frac{1}{\sqrt{2^t}} \sum_k e^{2\pi i \theta k} \ket{k}\). Compare with the QFT definition: \(\text{QFT}\ket{x} = \frac{1}{\sqrt{2^t}} \sum_k e^{2\pi i xk/2^t} \ket{k}\). These match when \(\theta = x/2^t\), i.e., when \(x = 2^t\theta\). So the counting register is in the state \(\text{QFT}\ket{2^t\theta}\)!
Step 3: Apply QFT\(^\dagger\) to the counting register
$$\text{QFT}^\dagger \left(\text{QFT}\ket{2^t\theta}\right) = \ket{2^t\theta}$$
The inverse QFT undoes the QFT, leaving us with the state \(\ket{2^t\theta}\) in the counting register.
Step 4: Measure the counting register
We measure and obtain the integer \(m = 2^t\theta\). Therefore:
$$\theta = \frac{m}{2^t}$$
If \(\theta\) can be written exactly as \(\theta = m/2^t\) for some integer \(m\), then the measurement gives \(m\) with probability 1. The QFT perfectly encodes and the QFT\(^\dagger\) perfectly decodes.
In general, \(2^t\theta\) may not be an integer. Then the state after QFT\(^\dagger\) is a superposition peaked around the nearest integer(s) to \(2^t\theta\):
Each additional counting qubit doubles the precision. With \(t\) counting qubits, you can resolve \(\theta\) to accuracy \(1/2^t\). But the circuit depth grows too: you need controlled-\(U^{2^{t-1}}\), which may require \(2^{t-1}\) applications of \(U\). So the total number of \(U\) applications is \(\sum_{j=0}^{t-1} 2^j = 2^t - 1\).
Let's work through a concrete example. Take \(U = T\) (the \(\pi/8\) gate) and \(\ket{\psi} = \ket{1}\).
$$T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}$$
The eigenvalues of \(T\): \(\ket{0}\) has eigenvalue 1 (i.e., \(\theta_0 = 0\)) and \(\ket{1}\) has eigenvalue \(e^{i\pi/4} = e^{2\pi i/8}\) (i.e., \(\theta_1 = 1/8\)).
Using \(t = 3\) counting qubits and \(\ket{\psi} = \ket{1}\):
\(\theta = 1/8 = 1/2^3\), which is exactly representable with 3 bits. With fewer counting qubits, we'd get a less precise estimate. With 2 qubits: \(2^2 \cdot 1/8 = 0.5\) — not an integer, so we'd get a probabilistic result (measuring either \(\ket{00}\) or \(\ket{01}\) with varying probabilities). With 1 qubit: \(2^1 \cdot 1/8 = 0.25\) — even worse.
At first glance, QPE seems circular: "we need to know the eigenstate \(\ket{\psi}\) and be able to implement controlled-\(U\), so don't we already know everything?" Not quite.
This is a common misconception. You don't need to know \(\theta\) to build controlled-\(U\). You need to be able to implement \(U\) as a circuit, which is a completely different thing. Examples:
Shor's algorithm for factoring \(N\):
QPE finds \(r\) by estimating the eigenvalues of the unitary \(U: \ket{y} \mapsto \ket{ay \bmod N}\). The eigenvalues are \(e^{2\pi i s/r}\) for \(s = 0, 1, \ldots, r-1\), so measuring gives an estimate of \(s/r\), from which \(r\) can be extracted using continued fractions.
The structure of Deutsch-Jozsa and Bernstein-Vazirani was:
\(H^{\otimes n} \;\to\; \text{Oracle} \;\to\; H^{\otimes n} \;\to\; \text{Measure}\)
QPE generalizes this to:
\(H^{\otimes t} \;\to\; \text{Controlled-}U^{2^j} \;\to\; \text{QFT}^\dagger \;\to\; \text{Measure}\)
The Hadamard gate \(H\) was the "baby QFT" — it's \(F_2\), the Fourier transform over two elements. In DJ/BV, the second \(H^{\otimes n}\) acted as the decoder. Now we use the full \(\text{QFT}^\dagger\) as the decoder. Same fundamental principle: encode information in phases, then decode with the (inverse) Fourier transform.
The progression of algorithms in this course follows a clear arc:
| Algorithm | Encoder | Phase Source | Decoder |
|---|---|---|---|
| Deutsch-Jozsa | \(H^{\otimes n}\) | Phase oracle \((-1)^{f(x)}\) | \(H^{\otimes n}\) |
| Bernstein-Vazirani | \(H^{\otimes n}\) | Phase oracle \((-1)^{s \cdot x}\) | \(H^{\otimes n}\) |
| Simon's | \(H^{\otimes n}\) | Boolean oracle + measurement | \(H^{\otimes n}\) |
| QPE / Shor's | \(H^{\otimes t}\) | Controlled-\(U^{2^j}\) (eigenvalue phases) | \(\text{QFT}^\dagger\) |
The key evolution: the first three algorithms use \(H^{\otimes n}\) as both encoder and decoder (because \(H = H^\dagger\), the Hadamard is its own inverse). QPE upgrades the decoder to the full inverse QFT, which can handle the richer phase structure of eigenvalue problems.