12.8 Quantum Fourier transform

Source: Ideas from Computational Physics (Landau, Páez, Bordeianu), §12.8. Original wording — no textbook Qiskit listing dumps. Continues 12.7b. Labs: 12.8b.

Chapter 9’s DFT maps a length-$N$ signal $y_k$ to coefficients $Y_n$ with powers of $Z_N=e^{-2\pi i/N}$. The quantum Fourier transform does the same job on an $N=2^n$-dimensional Hilbert space. Pick the QFT definition and the $\mathrm{QFT}_4$ matrix among lookalikes.

(Qiskit / CS indexing from $0$; no extra $\sqrt{2\pi}$ factors.) Basis labels: $|0\rangle=|00\rangle$, $|1\rangle=|01\rangle$, $|2\rangle=|10\rangle$, $|3\rangle=|11\rangle$.

Gate factorization (2 qubits)

With Hadamard $H$ and phase $P(\theta)=\mathrm{diag}(1,e^{i\theta})$, and $Z\equiv Z_4=-i$,

$$\begin{align*} \mathrm{QFT}_4|00\rangle&=H|0\rangle\otimes H|0\rangle,\\ \mathrm{QFT}_4|01\rangle&=H|1\rangle\otimes P(\pi/2)H|0\rangle,\\ \mathrm{QFT}_4|10\rangle&=H|0\rangle\otimes H|1\rangle,\\ \mathrm{QFT}_4|11\rangle&=H|1\rangle\otimes P(\pi/2)H|1\rangle. \end{align*}$$

Compactly (then SWAP the two output lines to match textbook wire order):

$$\mathrm{QFT}_4|q_1 q_0\rangle \;\widehat=\; H|q_0\rangle\otimes P^{q_0}(\pi/2)\,H|q_1\rangle \quad\text{(+ SWAP)}.$$

Lab: wire QFT₄

Connect q-reg → H / controlled-P → H → SWAP → out (schema-style).

Sampling exercise (idea)

Take four samples of $y(t)=3\cos(\omega t)+2\cos(3\omega t)$, apply $\mathrm{QFT}_4$, read frequency bins, and check that the inverse (or direct sum of components) rebuilds $y$. Labs lock $Z_4=-i$ and the $(0,0)$ entry $1/2$.

$n$-qubit QFT

With $n$ qubits, $N=2^n$ components live in an $N$-D Hilbert space (tensor-product basis). The circuit generalizes: layered Hadamards and controlled phase rotations $R_k=P(2\pi/2^k)$, then bit-reversal SWAPs — still $O(n^2)$ gates vs classical $O(N\log N)$ on explicitly stored vectors.

Takeaway

Classical DFT	QFT
$Z_N^{nk}$ on arrays	same phases on amplitudes
$O(N\log N)$ FFT	$O(n^2)$ gates, $N=2^n$
QFT₄	$H$, controlled-$P(\pi/2)$, SWAP

Quiz

QFT

1 / 3

Z₄ = e^{−iπ/2} equals…

Pick an answer to see if you are right.

Next: 12.8b QFT labs.