 Solution

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

Codex  0 Created 2026-09-24 Updated 2026-10-03

Changing the summation variable from

y

z = y + 1

gives

S ∣ ξ_{x} ⟩ = \frac{1}{d} \sum_{y} ω_{d}^{x y} ∣ y + 1 ⟩ = ω_{d}^{- x} \frac{1}{d} \sum_{z} ω_{d}^{x z} ∣ z ⟩ = ω_{d}^{- x} ∣ ξ_{x} ⟩ .

Thus the quantum Fourier transform diagonalizes the cyclic shift.

For

f : Z_{m} \to Z_{n}

U_{f} = \sum_{x \in Z_{m}} ∣ x ⟩ ⟨ x ∣ \otimes S^{f (x)} .

Consequently the product states

∣ x ⟩ ∣ ξ_{y} ⟩, x \in Z_{m}, q u a d y \in Z_{n},

form an eigenbasis, with corresponding eigenvalues

ω_{n}^{- y f (x)} .

 New to topics? Read the docs here!