  Classical fingerprinting associates with each string a shorter string (its
fingerprint), such that, with high probability, any two distinct strings can be
distinguished by comparing their fingerprints alone. The fingerprints can be
exponentially smaller than the original strings if the parties preparing the
fingerprints share a random key, but not if they only have access to
uncorrelated random sources. In this paper we show that fingerprints consisting
of quantum information can be made exponentially smaller than the original
strings without any correlations or entanglement between the parties: we give a
scheme where the quantum fingerprints are exponentially shorter than the
original strings and we give a test that distinguishes any two unknown quantum
fingerprints with high probability. Our scheme implies an exponential
quantum/classical gap for the equality problem in the simultaneous message
passing model of communication complexity. We optimize several aspects of our
scheme.
