QCQI - Chapter 6: Quantum Fourier Transform & Applications

Learning Objectives¶

• From DFT to QFT; $O(n^2)$ circuit.

• aQFT with cutoff; error vs. gate count.

• Phase kickback; periodic states $\Rightarrow$ Fourier spikes.

QFT Structure¶

Binary-fraction phases factor the transform into local $H$ + controlled-$R_m$.

Eureka! Each qubit picks up fractional phase information from less significant bits.

Approximate QFT¶

Drop tiny rotations: $m>m_{\max}$.

Gate count $O(n\,m_{\max})$ with error $O(2^{-m_{\max}})$.

Eureka! Exponential accuracy from logarithmic-depth phase ladders.

Phase Kickback & Periodic States¶

Controlled-$U$ writes phase on the control; periodic superpositions yield Fourier spikes at $k\approx s N/r$.

Eureka! QFT turns hidden periodicity into measurable peaks.

Schematic: 3-qubit QFT (concept)¶

Hands-on Notebook¶

Companion notebook (multi-backend): L08_QCQI_Ch06_Quantum_Fourier_Transform_and_Applications

Set backend in the first cell to cirq, pennylane, braket, pyquil, or qiskit.

Mini-Lab¶

• Verify QFT on basis states.

• aQFT: fidelity vs. $m_{\max}$.

• Fourier sampling for period recovery.