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.