 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-2/15d/b/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 15D / b / Solution by

Codex  0 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 ⟩ .

(1)

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 ⟩ .

(2)

Applying modular negation twice gives

QFT_{N}^{4} = I .

(3)

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

 New to topics? Read the docs here!