 Solution

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

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

With the restricted operations, begin in

∣0 ⟩ ∣0 ⟩

and apply

F

to the first register:

\frac{1}{N} \sum_{i} ∣ i ⟩ ∣0 ⟩ .

Now apply

O_{x}, Z, O_{x} .

∣ i ⟩ ∣0 ⟩ \mapsto ∣ i ⟩ ∣ x_{i} ⟩ \mapsto (- 1)^{x_{i}} ∣ i ⟩ ∣ x_{i} ⟩ \mapsto (- 1)^{x_{i}} ∣ i ⟩ ∣0 ⟩ .

The first register is therefore the same phase state used in part (a). Apply

F^{- 1}

and measure. Again, outcome

0

occurs with probability one for a constant string and probability zero for a balanced string. The construction uses exactly two queries to

O_{x}

and only the permitted operations.

 New to topics? Read the docs here!