One qubit vs. one bit fingerprinting schemes - Niel de Beaudrap

Fingerprinting is a technique in communication complexity in which two parties (Alice and Bob) with large data sets send short messages to a third party (a referee), who attempts to determine whether these data sets are equal. In this talk, we consider the extreme scenario of performing fingerprinting where Alice and Bob both send either one bit (classically) or one qubit (in the quantum regime) messages to the referee. Restrictive bounds are demonstrated for the error probability of one-bit fingerprinting schemes, and show that it is easy to construct one-qubit fingerprinting schemes which can outperform any one-bit fingerprinting scheme. It is hoped that this analysis will provide results useful for performing physical experiments, which may help to advance implementations for more general quantum communication protocols.