QCQI – Chapter 6 Detailed Summary: Quantum Fourier Transform & Applications

Learning Objectives¶

Define the discrete Fourier transform (DFT) and the quantum Fourier transform (QFT) on $\mathbb{Z}_{2^n}$ .
Derive the $O(n^2)$ QFT circuit using $H$ and controlled phase rotations, including the bit-reversal.
Understand approximate QFT (aQFT): angle cutoff, error bounds, and asymptotic gate count.
Apply QFT to periodic states and phase kickback; connect to order-finding and phase estimation.
Implement the semiclassical inverse QFT (Griffiths–Niu) with adaptive single-qubit rotations.

From DFT to QFT¶

Classical DFT on $N=2^n$ points uses $\omega=e^{2\pi i/N}$ :

\begin{aligned} \mathcal{F}_N: \ |x\rangle\ \mapsto\ \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega^{xk}|k\rangle. \end{aligned}

(1)

The QFT is the unitary implementing $\mathcal{F}_N$ on the computational basis and linearly extending to superpositions.

Eureka! The QFT is just a change of basis from computational states $|x\rangle$ to “phase states” $|\tilde{k}\rangle$ .

Binary Expansion & Circuit Construction¶

Write $k$ in binary as $k.k_{n-1}\dots k_0$ and $x$ as $x_{n-1}\dots x_0$ . Using the binary fraction $0.k_jk_{j-1}\cdots k_0=\sum_{\ell=0}^{j}k_{\ell}2^{-(\ell+1)}$ , the QFT factorizes:

\begin{aligned} |x\rangle\mapsto \bigotimes_{j=0}^{n-1}\frac{|0\rangle+e^{2\pi i\,0.x_jx_{j-1}\cdots x_0}|1\rangle}{\sqrt{2}}. \end{aligned}

(2)

This yields a circuit with, for each qubit $j$ (from MSB to LSB): a Hadamard $H$ and controlled- $R_k$ rotations from lower-order bits, where $R_m=\mathrm{diag}(1, e^{2\pi i/2^m})$ . A final bit-reversal (sequence of SWAPs) restores natural order.

Eureka! Each qubit picks up a fractional phase from less significant bits via controlled rotations. The final state is a product state in the phase basis.

Complexity and Approximation¶

The exact circuit uses $\tfrac12n(n-1)$ controlled rotations $\Rightarrow O(n^2)$ gates. For the approximate QFT (aQFT), drop $R_m$ with $m>m_{\max}$ (small angles). For $m_{\max}=O(\log n)$ , the operator-norm error is $O(1/\mathrm{poly}(n))$ and the gate count drops to $O(n\log n)$ .

Eureka! Tiny phase rotations contribute little: trimming them yields near-exact transforms with exponentially small error.

Phase Kickback¶

If $U|u\rangle=e^{2\pi i \phi}|u\rangle$ , then a controlled- $U$ from a control qubit in $|+\rangle$ kicks the eigenphase to the control:

\begin{aligned} \frac{|0\rangle|u\rangle+|1\rangle|u\rangle}{\sqrt2}\xrightarrow{\mathrm{c}U}\frac{|0\rangle|u\rangle+e^{2\pi i \phi}|1\rangle|u\rangle}{\sqrt2}. \end{aligned}

(3)

Applying an inverse QFT to a register of such phase-kicked qubits reveals binary digits of $\phi$ (core of phase estimation).

Eureka! Controlled unitaries turn global eigenphases into observable relative phases on controls.

Periodic States & Fourier Sampling¶

Given a state uniform on a period- $r$ coset,

\begin{aligned} |\psi\rangle=\frac{1}{\sqrt{M}}\sum_{t=0}^{M-1}|x_0+tr\rangle \quad (\mathrm{mod}\ N), \end{aligned}

(4)

the QFT produces peaks near integer multiples of $N/r$ . Sampling yields $k \approx s\cdot \frac{N}{r}$ and hence information about $r$ via continued fractions.

Eureka! QFT converts periodicity in $x$ -space into spikes in $k$ -space.

Semiclassical Inverse QFT (Griffiths–Niu)¶

Measure qubits one-by-one from least significant to most, feed forward classically controlled $R_z$ rotations to cancel known phases before each $H$ , and continue. This replaces multi-qubit entangling rotations with adaptive single-qubit gates and measurements.

Eureka! Measurement + classical feed-forward can substitute for many entangling gates in $\mathrm{QFT}^{-1}$ .

Worked Nuggets¶

3-qubit QFT. $H$ on MSB; apply $\mathrm{CR}_2$ from middle, $\mathrm{CR}_3$ from LSB; repeat pattern for remaining qubits; final SWAP $(0,2)$ .

aQFT error. Dropping all rotations with angle $<2\pi/2^{m_{\max}}$ incurs operator-norm error $<\sum_{m>m_{\max}}2^{-m}=2^{-m_{\max}}$ (coarse bound).

Fourier adder (idea). Addition by phases: QFT $\to$ phase rotations encoding addend $\to$ inverse QFT.

Pseudo-code Aids¶

Pseudocode — QFT on $n$ qubits (exact)

Input: $n$ qubits ordered MSB..LSB for $j$ from 0 to $n-1$ : apply $H$ to qubit $j$ for $k=j+1$ to $n-1$ : apply controlled- $R_{k-j+1}$ with control $k$ target $j$ finally: reverse bit order using SWAPs

Pseudocode — Approximate QFT (angle cutoff $m_{\max}$ )

Input: $n$ , cutoff $m_{\max}$ for each controlled- $R_m$ in QFT: if $m>m_{\max}$ , omit it Gate count $O(n\,m_{\max})$ , operator error $O(2^{-m_{\max}})$

Pseudocode — Semiclassical $\mathrm{QFT}^{-1}$ (LSB-first)

Input: $n$ -qubit register for $j$ from $n-1$ down to 0: apply $R_z(-\phi_j)$ depending on previously measured bits apply $H$ ; measure qubit $j$ ; update phases $\{\phi_{j-1},\dots\}$

Schematics¶

3-Qubit QFT (concept)¶

Phase Kickback¶

Hands-on Notebook (Multi-Backend)¶

Run: L08_QCQI_Ch06_Quantum_Fourier_Transform_and_Applications

In the first cell set backend to one of: cirq, pennylane, braket, pyquil, or qiskit.

Mini-Lab Ideas¶

Verify QFT on basis states: compare statevector phases to analytic DFT.
Implement aQFT with various $m_{\max}$ ; plot fidelity vs. gate count.
Prepare a period- $r$ state and recover $r$ from QFT samples using continued fractions.