Exercises: The Quantum Fourier Transform
All of these run on a simulator. Solutions to starred exercises are in Answers to Selected Exercises.
Warm-up
22.1 ★ Build the DFT matrix for $n = 3$ in NumPy and compare it against Operator(QFTGate(3)).
Report the maximum elementwise difference.
22.2 Decompose a 4-qubit QFTGate into h, cp, and swap. Count each. Confirm the counts match
$n$, $n(n-1)/2$, and $\lfloor n/2 \rfloor$.
22.3 ★ List the controlled-phase angles appearing in a 6-qubit QFT. Confirm they halve, and give the smallest as a fraction of $2\pi$.
22.4 Apply the QFT to $|0\rangle^{\otimes n}$. What state results, and why?
22.5 ★ Apply the QFT to a single basis state $|j\rangle$ for a few $j$, and verify the output amplitudes match $e^{2\pi i jk/N}/\sqrt N$.
The convention trap
22.6 ★ Implement all four conventions from §22.1 and report each one's fidelity against
QFTGate(4). Identify the correct one.
22.7 ★★ Write verify_against_dft(n) comparing your construction to the DFT matrix. Explain why
this is a stronger check than comparing against QFTGate.
22.8 ★★ Take a wrong convention and trace what it does to a single basis state. Where exactly does the discrepancy enter — the Hadamards, the rotations, or the swaps?
22.9 ★★ Feed a wrong-convention QFT into the phase-estimation circuit from §22.4. Does it produce obviously wrong output, or a plausible wrong number? What does that imply for debugging?
The readout problem
22.10 ★ Prepare a pure frequency-$f$ signal on 3 qubits, apply the QFT, and print the output amplitudes and probabilities. Confirm the measurement returns $f$.
22.11 ★ Now prepare a signal that is a sum of two frequencies. What do the measurement probabilities show, and what information has been lost?
22.12 ★★ Estimate how many shots you would need to resolve all $2^n$ output probabilities to within 1% for $n = 4, 8, 12$. Compare with the FFT's operation count at the same sizes.
22.13 ★★ Full reconstruction needs the phases too. Look up state tomography's scaling and tabulate the measurement count for $n = 2, 4, 6$. At what $n$ does it exceed the classical FFT cost?
22.14 ★★ Time QuantumCircuit.initialize() with a random state vector for $n = 4 \dots 12$ and fit
the scaling. Does it match $\mathcal{O}(2^n)$?
22.15 ★★★ Construct a signal that can be prepared efficiently (in $\mathcal{O}(\text{poly}(n))$ gates) — for instance one with a closed-form amplitude pattern. Does the QFT give an advantage for this signal? What does that tell you about when the readout objection can be dodged?
Phase estimation
22.16 ★ Implement phase estimation for $\varphi = 0.25$ with 3, 4, and 5 counting qubits. Confirm the answer is exact and the success probability is 1.
22.17 ★ Repeat for $\varphi = 1/3$ at $t = 3 \dots 10$. Tabulate the error and confirm it halves.
22.18 ★★ Write is_dyadic(phase, t) and use it to predict, before running, which phases will be
estimated exactly. Verify against measurement.
22.19 ★★ For $\varphi = 1/3$ at $t = 6$, plot the full outcome distribution rather than just the most likely value. What shape is it, and where does the probability go?
22.20 ★★ Implement counting_qubits_for(m, confidence) from the formula in §22.4. Verify
empirically that the resulting register achieves $m$ correct bits at the stated rate, over many runs
with random phases.
22.21 ★★★ Phase estimation assumes you can prepare an eigenvector of $U$. What happens if you feed it a superposition of two eigenvectors? Run it and interpret the outcome distribution.
22.22 ★★★ Implement quantum counting: phase estimation on the Grover operator from Chapter 21,
recovering $M$ from the eigenvalue phase via $\sin^2\theta = M/N$. Test it for $M = 1, 2, 3$ at
$N = 16$ and compare with Chapter 21's heuristic estimate_marked_count.
The approximate QFT
22.23 ★ Implement the AQFT with a cutoff and reproduce §22.5's fidelity table for $n = 6$ and $n = 8$.
22.24 ★ Confirm the AQFT reaches fidelity exactly 1.0 at cutoff $n-1$. Why is this a good test of your convention as well as your cutoff logic?
22.25 ★★ For $n = 8$, find the smallest cutoff achieving fidelity above 0.99, 0.999, and 0.9999. How does the required cutoff scale?
22.26 ★★ Tabulate the gate saving from the $c = \lceil\log_2 n\rceil$ rule for $n = 8, 16, 32, 64, 128, 256$. Does the saving approach a limit?
22.27 ★★ Run phase estimation using an AQFT instead of the exact inverse QFT. At what cutoff does the estimate degrade measurably? Compare with the fidelity at the same cutoff.
22.28 ★★★ The AQFT's error is usually stated as bounded by the sum of the dropped rotation angles. Compute that bound for $n = 8$ at each cutoff and compare with the measured infidelity. Is the bound tight?
Cost
22.29 ★★ Using Chapter 15's estimator with rotationDepth set, price the full QFT and the AQFT at
$n = 16$ and $n = 32$. Report physical qubits and runtime.
22.30 ★★ Reproduce §22.6's non-monotonicity: sweep rotationCount with rotationDepth at 0 and
find the point where the qubit count decreases. Explain what the estimator is trading.
Project
22.31 ★★ (Project Checkpoint) Build vqelab/qft.py with qft_circuit(n, cutoff),
verify_against_dft, aqft_fidelity, phase_estimation_circuit, estimate_phase returning a
PhaseEstimate, counting_qubits_for, and qft_cost. Write tests asserting:
- The construction matches
QFTGateto $10^{-9}$ for $n = 2 \dots 5$. - It matches the DFT matrix.
- The three wrong conventions have fidelity below 0.5.
- Gate counts are $n$ Hadamards and $n(n-1)/2$ controlled phases.
- Invalid requests raise.
- Dyadic phases are estimated with zero error and probability > 0.999.
- Non-dyadic error decreases monotonically with $t$ and falls by more than 20× from $t=3$ to $t=8$.
- Estimates stay within $2^{-t}$.
- The counting-qubit overhead is constant in $m$.
- AQFT fidelity increases monotonically and reaches exactly 1.0.
- AQFT at cutoff 3 exceeds 0.95 fidelity; at cutoff 4, 0.99.
- Cost is monotonic in rotation count — which fails if
rotationDepthis unset.
Tests 3, 10, and 12 encode this chapter's traps.
22.32 ★★★ Extend qft.py with qft_from_scratch_verified(n) that builds the QFT, checks it
against the DFT matrix, and raises if the check fails — so a convention error is caught at
construction rather than downstream. Then deliberately break the convention and confirm it raises.
Going further
22.33 ★★★ The QFT over $(\mathbb{Z}_2)^n$ is exactly $H^{\otimes n}$. Prove it, then verify numerically. Explain how this connects Chapter 20's three-step pattern to phase estimation.
22.34 ★★★ Read about the semiclassical (Kitaev) QFT, which replaces controlled rotations with mid-circuit measurement and classically-conditioned single-qubit rotations. Implement it using Chapter 9's dynamic circuits and compare the two-qubit gate count against the standard QFT.