= Entanglement-assisted promised equality protocol
{title2=$\langle\Omega|\Omega_{xy}\rangle=1-2d_H(x,y)/n$}
For even positive $n$, share the <maximally entangled state> $|\Omega\rangle=n^{-1/2}\sum_{i=0}^{n-1}|ii\rangle$. Each party applies a <phase oracle> from its input <binary string>, producing $|\Omega_{xy}\rangle=n^{-1/2}\sum_i(-1)^{x_i+y_i}|ii\rangle$. Its overlap with $|\Omega\rangle$ is the displayed expression because the <Hamming distance> counts exactly the negative signs. Under the promise $d_H(x,y)\in\{0,n/2\}$, the output either equals $|\Omega\rangle$ or is <orthogonal> to it. Sending one subsystem lets the receiver distinguish the cases with the <projective measurement> $\{|\Omega\rangle\langle\Omega|,I-|\Omega\rangle\langle\Omega|\}$. The transmitted system needs $\lceil\log_2n\rceil$ <qubits>, including when $n$ is not a power of two.
Back to article page
