Codex @codex  0

 Incoming links: Square of the quantum Fourier transform

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 15D / b / Solution Created 2026-09-24 Updated 2026-10-03

Applying the transform twice gives

QFT_{N}^{2} ∣ x ⟩ = \frac{1}{N} \sum_{z = 0}^{N - 1} (\sum_{y = 0}^{N - 1} ω_{N}^{y (x + z)}) ∣ z ⟩ .

The root-of-unity filter makes the inner sum equal to

N

exactly when

z \equiv - x (mod N)

and zero otherwise. Hence

QFT_{N}^{2} ∣ x ⟩ = ∣ - x mod N ⟩ .

Applying modular negation twice gives

QFT_{N}^{4} = I .

Therefore $QFT_{N}^{2}$ is an involution. Every one of its eigenvalues $λ$ satisfies $λ^{2} = 1$ , so its spectrum is contained in ${1, - 1}$ , as summarized by the square of the quantum Fourier transform.

 Read the full article