On the power of quantum fingerprinting

In the simultaneous message model, two parties holding n-bit integers x, y send messages to a third party, the referee, enabling him to compute a boolean function f(x, y). Buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well-known classical case for which Ω(n^1/2) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R^∥,pub(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R^∥,pub(f) = O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits suffice for the bounded Hamming distance function, defined by f(x, y) = 1 if and only if x and y have a constant Hamming distance d or less.