 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-2/10d/solution

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

∣ 0^{n} ⟩

becomes

⟨ 0^{n} ∣ H^{\otimes n} ∣ ξ ⟩ = \frac{1}{2 ^{n}} \sum_{x \in B_{n}} (- 1)^{f (x)} .

It equals

1

in case (I) and

0

in case (II). A computational-basis measurement therefore returns

0^{n}

with certainty in case (I) and never returns it in case (II). This is the Deutsch-Jozsa algorithm.

For the distributed problem, Alice prepares

∣ ξ_{A} ⟩ = 2^{- n /2} \sum_{x} (- 1)^{f_{A} (x)} ∣ x ⟩

using one query to her quantum oracle, and sends these

n

qubits to Bob. Bob applies his phase oracle, producing

2^{- n /2} \sum_{x} (- 1)^{f_{A} (x) \oplus f_{B} (x)} ∣ x ⟩ .

h = f_{A} \oplus f_{B}

is constant zero in case (1) and balanced in case (2). Bob applies

H^{\otimes n}

and measures as above: outcome

0^{n}

identifies case (1), while every other outcome identifies case (2), with certainty.

 New to topics? Read the docs here!