Exercises: Chapter 14 — The Quantum Fourier Transform — The Mathematical Engine Inside the Most Important Quantum Algorithms

Exercise 14.1 — QFT Matrix. Write out the full $8 \times 8$ QFT matrix for $n = 3$. Verify that it is unitary by checking $F^\dagger F = I$. Compute the QFT of the state $|3\rangle$ (binary $|011\rangle$) by matrix multiplication.

Exercise 14.2 — Circuit Construction. Draw the complete QFT circuit for $n = 4$, labeling all controlled phase gates with their rotation angles. Count the total number of Hadamard gates, controlled phase gates, and SWAP gates.

Exercise 14.3 — Product Representation. Derive the product representation of the QFT for $n = 3$ starting from the definition $\text{QFT}_3|j\rangle = \frac{1}{\sqrt{8}} \sum_{k=0}^{7} e^{2\pi i j k / 8} |k\rangle$. Show each algebraic step.

Exercise 14.4 — Period Finding Simulation. Create a Qiskit circuit that prepares the periodic state $|\psi\rangle = \frac{1}{2}(|1\rangle + |5\rangle + |9\rangle + |13\rangle)$ (period $r = 4$ on 4 qubits), applies the QFT, and measures. Show that the measurement outcomes concentrate on multiples of $N/r = 4$.

Exercise 14.5 — Approximate QFT Fidelity. Implement both the exact QFT and the approximate QFT (keeping only $O(\log n)$ rotations per qubit) for $n = 8$. Compute the fidelity $|\langle \psi_{\text{exact}} | \psi_{\text{approx}} \rangle|^2$ using the statevector simulator. How does the fidelity change as you vary the precision parameter?

Exercise 14.6 — QFT of Computational Basis States. Compute $\text{QFT}_3|j\rangle$ for $j = 0, 1, 2, \ldots, 7$ using the product representation. Verify that each output has equal magnitude $1/\sqrt{8}$ and that the phases are $e^{2\pi i j k / 8}$.

Exercise 14.7 — Inverse QFT Circuit. Construct the inverse QFT circuit for $n = 3$ by reversing the QFT circuit and negating all phase rotations. Verify that $\text{QFT}_3 \cdot \text{IQFT}_3 = I$ using the statevector simulator.

Exercise 14.8 — Connection to Hadamard Transform. Show that $\text{QFT}_1 = H$ (the single-qubit QFT is the Hadamard gate). Compute $\text{QFT}_2$ and show that it reduces to $H^{\otimes 2}$ when all phase rotations are $R_2 = e^{2\pi i/4} = e^{i\pi/2} = i$. Under what conditions does the QFT reduce to the Hadamard transform?

Exercise 14.9 — Period Finding with Noise. Simulate the QFT-based period-finding algorithm for $N = 16$ with period $r = 4$. Add depolarizing noise to the circuit and measure how the success probability degrades as the noise level increases. At what noise level does the algorithm fail?

Exercise 14.10 — QFT Gate Count. For the exact QFT on $n$ qubits, count the total number of: (a) Hadamard gates, (b) controlled phase rotations $R_k$ for each $k$, (c) SWAP gates, and (d) total two-qubit gates after decomposing SWAPs into CNOTs. Express the total as a function of $n$ and verify that it is $O(n^2)$.