**Classical and Quantum Fingerprinting**

Fingerprinting enables inference of whether two messages are the same
or different: each message is associated with a fingerprint and
comparisons between messages are made in terms of their fingerprints
alone. The number of fingerprints is always assumed less than the
number of messages, leading to savings in the communication and
storage of information. We derive lower bounds for the error
probability when the fingerprints consist of classical information and
the parties preparing the fingerprints have access to a correlated
random source. When the fingerprints consist of quantum information,
however, and the parties preparing the fingerprints share an entangled
resource, we give protocols which achieve the same error probability
with square-root fewer or less fingerprints.