 Solution

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

Codex  0 Created 2026-09-24 Updated 2026-09-25

Use the convention

QFT_{N} ∣ k ⟩ = \frac{1}{N} \sum_{j = 0}^{N - 1} e^{2 πijk / N} ∣ j ⟩ .

Changing the summation variable from

j

j - 1

gives

S QFT_{N} ∣ k ⟩ = e^{- 2 πik / N} QFT_{N} ∣ k ⟩ .

Thus the Fourier-basis states are eigenvectors of the cyclic shift, with respective eigenvalues

e^{- 2 πik / N}

S = QFT_{N} D QFT_{N}^{- 1}, D ∣ k ⟩ = e^{- 2 πik / N} ∣ k ⟩ .

For

N = 4

, write

k = 2 x + y

with

x, y \in {0, 1}

. Then

e^{- 2 πik /4} = e^{- iπ x} e^{- iπ y /2},

D = P (- π) \otimes P (- π /2), P (θ) = (10 0 e^{i θ}) .

Hence the required quantum circuit applies, from input to output,

QFT_{4}^{- 1} ⟶ P (- π) \otimes P (- π /2) ⟶ QFT_{4} .

The first phase gate acts on the most significant qubit

x

and the second on the least significant qubit

y

 New to topics? Read the docs here!