 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2008/iii/paper-57/4/a/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 57 / 4 / a / Solution by

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

Label the control qubits by binary weight: the bit

x_{n}

contributes

2^{n}

to

x = \sum_{n = 0}^{N - 1} 2^{n} x_{n}

. For each

n

, use that qubit as the control of the supplied controlled-

V^{2^{n}}

, with the same target eigenstate

∣ v_{j} ⟩

. The controlled unitary gate acts by

\frac{∣0 ⟩ + ∣1 ⟩}{2} ∣ v_{j} ⟩ ⟼ \frac{∣0 ⟩ + e ^{i 2^{n} ϕ_{j}} ∣1 ⟩}{2} ∣ v_{j} ⟩,

since

V^{2^{n}} ∣ v_{j} ⟩ = e^{i 2^{n} ϕ_{j}} ∣ v_{j} ⟩

. The target remains unchanged after every application. Multiplying these factors gives

[⨂_{n = 0}^{N - 1} \frac{∣0 ⟩ + e ^{i 2^{n} ϕ_{j}} ∣1 ⟩}{2}] ∣ v_{j} ⟩ = \frac{1}{2 ^{N}} x = 0 \sum 2^{N} - 1 e^{i ϕ_{j} x} ∣ x ⟩ ∣ v_{j} ⟩ .

The ordering of the tensor factors is chosen to match the binary place values. Discarding the unchanged target leaves the required phase register. This uses quantum phase kickback in the phase accumulation step of quantum phase estimation.

 Read the full article

 New to topics? Read the docs here!