 Solution

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

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

The known circuit from part (b) lets us apply

U_{I}

without querying the faulty oracle. Their composition satisfies

U_{I} U_{f} ∣ x ⟩ ∣ y ⟩ = {∣ x ⟩ ∣ y ⟩, ∣ x ⟩ ∣ y \oplus a ⟩, x \neq = x_{0}, x = x_{0} .

Because

a = 00 \dots 01

, only the last answer qubit is flipped in the exceptional case.

Prepare the answer register as

∣0 ⟩^{\otimes (n - 1)} ∣ - ⟩, ∣ - ⟩ = \frac{∣0 ⟩ - ∣1 ⟩}{2} .

Since

X ∣ - ⟩ = - ∣ - ⟩

, quantum phase kickback gives, for an arbitrary search-register state,

(U_{I} U_{f}) ∣ x ⟩ ∣ 0^{n - 1} ⟩ ∣ - ⟩ = (- 1)^{[x = x_{0}]} ∣ x ⟩ ∣ 0^{n - 1} ⟩ ∣ - ⟩ .

The answer register is unchanged and factors out. The induced operation on the first register is therefore

I_{x_{0}} = I - 2∣ x_{0} ⟩ ⟨ x_{0} ∣ .

 New to topics? Read the docs here!