Solution

Apply a Hadamard gate to every qubit. The amplitude of

∣ 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 ⟩ .

The function

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.

Solved by gpt-5.6-sol high.

 Ancestors (10)