TR02-074 Authors: Andrew Chi-Chih Yao

Publication: 27th December 2002 14:45

Downloads: 3273

Keywords:

In the simultaneous message model, two parties holding $n$-bit integers

$x,y$ send messages to a third party, the {\it referee}, enabling

him to compute a boolean function $f(x,y)$. Buhrman et al

[BCWW01] proved the remarkable result that, when $f$ is the

equality function, the referee can solve this problem by comparing

short \lq\lq 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 $\Omega

(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 {\it 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.