Quantum Fingerprinting

Classical fingerprinting solves the equality problem with reduced communication by having each party compute a short hash (fingerprint) of their data and compare hashes rather than raw strings. If Alice holds a string x and Bob holds a string y, each of length n bits, a classical randomized fingerprint of length O(log n) bits suffices to distinguish x = y from x ≠ y with high probability. This already saves communication compared to sending n bits, but the fingerprint size still grows (logarithmically) with the data length. Quantum fingerprinting, introduced by Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf in 2001, achieves fingerprints of size O(log n) qubits while requiring only a constant number of qubits of communication in the simultaneous message passing model, an exponential separation from the classical case.

The quantum fingerprint of an n-bit string x is a quantum state |f(x)> constructed using a Hadamard error-correcting code. The Hadamard encoding maps each x to a codeword C(x) of length 2^n bits, where C(x)_i = x . i mod 2 (the inner product of x with the binary representation of index i). The fingerprint state is |f(x)> = (1/sqrt(2^n)) sum_i (-1)^{C(x)_i} |i>, a uniform superposition with phases determined by the codeword. Because the Hadamard code has large minimum distance, the inner product |<f(x)|f(y)>| is small when x ≠ y and equals 1 when x = y. This orthogonality is the property that the SWAP test exploits to distinguish the two cases.

The SWAP test is a simple three-step circuit: apply a Hadamard to a single ancilla qubit, apply a controlled-SWAP between the two fingerprint registers conditioned on the ancilla, then apply a Hadamard to the ancilla and measure it. The probability of measuring 0 is (1 + |<f(x)|f(y)>|^2) / 2, which equals 1 when x = y and is close to 1/2 when x ≠ y. A referee with both fingerprint states can run the SWAP test with only the two O(log n)-qubit states in hand, without ever seeing the full strings. The total quantum communication from Alice and Bob to the referee is O(log n) qubits each, versus the classical lower bound of Omega(sqrt(n)) bits for any randomized classical protocol in this model, an exponential improvement.

Quantum fingerprinting is a landmark result in quantum communication complexity, demonstrating that quantum information can accomplish tasks requiring exponentially less communication than any classical scheme. It does not violate the no-communication theorem because a referee must be present to perform the SWAP test; the parties are not sending classical information to each other directly. Practical implementations require reliably preparing and transmitting the fingerprint states, which are spread across O(log n) qubits with delicately structured phase patterns. An experimental demonstration was performed in 2016 using coherent laser pulses as an analog approximation to the quantum fingerprint states, verifying the communication advantage in a photonic setting. The result connects to broader quantum communication complexity theory, where quantum protocols with small entanglement or quantum message size can sometimes compress communication that would require large classical messages.