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.