 Solution

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

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

Use the available unitaries to prepare

∣ s ⟩ = \frac{1}{N} \sum_{i \in Z_{N}} ∣ i ⟩

in the first register and

∣ - ⟩ = \frac{∣0 ⟩ - ∣1 ⟩}{2}

in the answer qubit. The quantum phase kickback identity gives

O_{x} ∣ s ⟩ ∣ - ⟩ = \frac{1}{N} \sum_{i} (- 1)^{x_{i}} ∣ i ⟩ ∣ - ⟩ .

Choose a unitary

F

with

F ∣0 ⟩ = ∣ s ⟩

, apply

F^{- 1}

to the first register, and measure it. Its amplitude at

∣0 ⟩

⟨ s ∣ \frac{1}{N} \sum_{i} (- 1)^{x_{i}} ∣ i ⟩ = \frac{1}{N} \sum_{i} (- 1)^{x_{i}} .

This equals

+ 1

- 1

for a constant string and zero for a balanced string. Thus outcome

0

means constant, while every other outcome means balanced, with certainty after one oracle query. This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary.

 New to topics? Read the docs here!