Quantum Fourier transform

Remarks

$F_N$ is unitary: the inner product of two columns is $\frac1N \sum_y \omega^{(x' - x)y}$, which is $1$ if $x = x'$ and $0$ otherwise. On amplitudes, $F_N$ maps $\sum_x a_x \lvert x \rangle$ to $\sum_y b_y \lvert y \rangle$ with $b_y = N^{-1/2} \sum_x \omega^{xy} a_x$, a normalised discrete Fourier transform with the sign convention $e^{+2\pi i/N}$.

Example: for $N = 2$, $\omega = -1$ and $F_2 = \frac{1}{\sqrt2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$, the Hadamard gate.

Non-example: the map $\lvert x \rangle \mapsto \sum_y \omega^{xy} \lvert y \rangle$ without the factor $N^{-1/2}$ is not unitary, since it sends the unit vector $\lvert 0 \rangle$ to a vector of norm $\sqrt N$.

For $N = 2^n$, writing $x = x_1 \cdots x_n$ in binary, $F_N \lvert x \rangle$ is the product state $\bigotimes_{k=1}^{n} \frac{1}{\sqrt2}\left(\lvert 0 \rangle + e^{2\pi i\, x / 2^k} \lvert 1 \rangle\right)$. This product form gives a circuit of $n$ Hadamard gates, $n(n-1)/2$ controlled phase gates and a reversal of the order of the qubits.