= Solution
Use the <entanglement-assisted promised equality protocol>. Alice applies the <phase oracle> $O_x|i\rangle=(-1)^{x_i}|i\rangle$ on $A$, and Bob applies $O_y|i\rangle=(-1)^{y_i}|i\rangle$ on $B$. These are <unitary operators> because their diagonal entries have <modulus> one. After Alice sends $A$ to Bob, the joint <pure state> is
$$
|\Omega_{xy}\rangle=\frac1{\sqrt n}\sum_{i=0}^{n-1}(-1)^{x_i+y_i}|ii\rangle.
$$
Let $|\Omega\rangle=n^{-1/2}\sum_i|ii\rangle$ be the original <maximally entangled state>. If $d=d_H(x,y)$ is the <Hamming distance>, then
$$
\langle\Omega|\Omega_{xy}\rangle
=\frac1n\sum_i(-1)^{x_i+y_i}
=\frac{n-d-d}{n}=1-\frac{2d}{n}.
$$
Bob performs the <projective measurement> with projectors $P=|\Omega\rangle\langle\Omega|$ and $I-P$. Under the promise,
$$
\boxed{d=0\implies\Pr(P)=1,\qquad
d=n/2\implies\Pr(P)=0.}
$$
He declares equal strings for the first outcome and distance $n/2$ for the other. This is exact because the promised outputs occupy <orthogonal> subspaces. A <basic measurement> also suffices: extend $|\Omega\rangle$ to an <orthonormal basis> and group all its other outcomes together. Alice transmits one $n$-dimensional system, realizable using $\lceil\log_2n\rceil$ <qubits>; $n$ need not be a power of two.
Back to article page
