= Solution
Apply a <Hadamard gate> to every qubit. The amplitude of $|0^n\rangle$ becomes
$$
\langle0^n|H^{\otimes n}|\xi\rangle
=\frac1{2^n}\sum_{x\in\mathcal B_n}(-1)^{f(x)}.
$$
It equals $1$ in case (I) and $0$ in case (II). A <quantum measurement in the computational basis>[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
$$
|\xi_A\rangle=2^{-n/2}\sum_x(-1)^{f_A(x)}|x\rangle
$$
using one query to her <Boolean quantum oracle>[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\rangle.
$$
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.
Back to article page
