= Solution
Applying the transform twice gives
$$
\operatorname{QFT}_N^2|x\rangle
=\frac1N\sum_{z=0}^{N-1}
\left(\sum_{y=0}^{N-1}\omega_N^{y(x+z)}\right)|z\rangle.
$$
The <root-of-unity filter> makes the inner sum equal to $N$ exactly when $z\equiv-x\pmod N$ and zero otherwise. Hence
$$
\boxed{\operatorname{QFT}_N^2|x\rangle=|-x\bmod N\rangle}.
$$
Applying modular negation twice gives
$$
\boxed{\operatorname{QFT}_N^4=I}.
$$
\b[Therefore $\operatorname{QFT}_N^2$ is an involution. Every one of its <eigenvalues> $\lambda$ satisfies $\lambda^2=1$, so its spectrum is contained in $\{1,-1\}$, as summarized by the <square of the quantum Fourier transform>.]
Back to article page
