The Exercise

A quantum system has a state space of dimension $N$ with orthonormal basis $|0\rangle, |1\rangle, \dots, |N-1\rangle$. The quantum Fourier transform on this space is the linear map that takes the basis state $|j\rangle$ to the superposition $\tfrac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk/N} |k\rangle$ of all of them.^✦ The exercise is to show that this map is unitary, so that it is an allowed evolution of the system.

The Quantum Fourier Transform

For a positive integer $N$, the quantum Fourier transform $F_N$ is the $N \times N$ complex matrix, with rows and columns labelled by the integers modulo $N$, whose entries are $$(F_N)_{jk} = \frac{1}{\sqrt{N}}\, e^{2\pi i jk/N} .$$(1)^✦ The map of the exercise has $F_N$ as its matrix in the basis $|0\rangle, \dots, |N-1\rangle$.

The Claim

What Is Checked

The claim is stated over one construction, the matrix $F_N$ of (1), for every dimension $N \ge 1$. What the library proves about it is (2): $F_N$ belongs to the group of $N \times N$ unitary matrices.^✦