Key Takeaways: Chapter 14 — The Quantum Fourier Transform — The Mathematical Engine Inside the Most Important Quantum Algorithms
-
The QFT is the quantum analog of the Discrete Fourier Transform, mapping $\sum_j x_j |j\rangle$ to $\sum_k y_k |k\rangle$ where $y_k$ is the DFT of $x_j$. It is a unitary transformation on $n$ qubits.
-
The QFT circuit uses $O(n^2)$ gates (Hadamard + controlled phase rotations), compared to $O(n 2^n)$ for the classical FFT. However, the output amplitudes cannot be efficiently read out — the QFT must be embedded in a larger algorithm.
-
The product representation $\text{QFT}_n|j\rangle = \frac{1}{\sqrt{2^n}} \bigotimes_{\ell=1}^n (|0\rangle + e^{2\pi i \cdot 0.j_\ell \ldots j_n}|1\rangle)$ is the key to constructing the QFT circuit and understanding its structure.
-
The QFT reveals periodicity: a state with period $r$ is transformed by the QFT into a state whose amplitudes concentrate near multiples of $N/r$. This is the engine behind Shor's algorithm and phase estimation.
-
The inverse QFT is the Hermitian conjugate, implemented by reversing the QFT circuit and negating all phase rotations. It converts phase-encoded information back into the computational basis.
-
The QFT is not a standalone speedup — it is a subroutine. Its exponential compactness (representing $2^n$ Fourier coefficients in $n$ qubits) is harnessed by algorithms that extract global properties (period, phase, eigenvalue) from the Fourier-transformed state.
-
The approximate QFT with $O(n \log n)$ gates achieves fidelity $1 - O(1/\text{poly}(n))$ by dropping small-angle controlled rotations. This is sufficient for all known quantum algorithms.
-
The Hadamard transform $H^{\otimes n}$ is the QFT over $\mathbb{Z}_2^n$, while the full QFT is over $\mathbb{Z}_{2^n}$. The additional controlled phase rotations in the full QFT enable it to detect periods that the Hadamard transform cannot.