Classical and quantum fingerprinting strategies

Full text: Fingerprinting enables two parties to infer whether the messages they hold are the same or different when the cost of communication is high: each message is associated with a smaller fingerprint and comparisons between messages are made in terms of their fingerprints alone. When the two parties are forbidden access to a public coin, it is known that fingerprints composed of quantum information can be made exponentially smaller than those composed of classical information. We present specific constructions of classical fingerprinting strategies through the use of constant-weight codes and provide bounds on the worst-case error probability with the help of extremal set theory. These classical strategies are easily outperformed by quantum strategies constructed from line packings and equiangular tight frames. (author)