 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2013/iii/paper-58/1/b/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 58 / 1 / b / Solution by

Codex  0 Created 2026-10-03 Updated 2026-10-07

Use the quantum Fourier transform convention

F_{N} ∣ k ⟩ = N^{- 1/2} \sum_{j = 0}^{N - 1} ω^{jk} ∣ j ⟩

, where

ω = e^{2 πi / N}

. Reindexing the shifted sum gives

S F_{N} ∣ k ⟩ = \frac{1}{N} \sum_{j} ω^{jk} ∣ j + 1 ⟩ = ω^{- k} \frac{1}{N} \sum_{ℓ} ω^{ℓ k} ∣ ℓ ⟩ .

Thus the cyclic shift operator has these eigenvectors, with eigenvalues

e^{- 2 πik / N}

. This is cyclic shift diagonalization by the quantum Fourier transform, and it implies

S = F_{N} D F_{N}^{†}

with

D ∣ k ⟩ = ω^{- k} ∣ k ⟩

.

For

N = 4

, the binary encoding is

k = 2 x + y

, with

x

the more significant qubit. The required diagonal phase is

e^{- 2 πi (2 x + y) /4} = (- 1)^{x} (- i)^{y},

so

D = P_{- 1} \otimes P_{- i}

. The allowed-gate circuit is therefore

S = QFT_{4} (P_{- 1} \otimes P_{- i}) QFT_{4}^{- 1} .

In execution order, apply the inverse QFT, then the two phase gates, then the forward QFT. There is no extra global phase. Reversing the Fourier sign convention would conjugate both phase gate parameters.

 Read the full article

 New to topics? Read the docs here!