Quantum fingerprinting

Definition
Quantum fingerprinting is a communication protocol in quantum information theory that enables two parties to compare large data strings while transmitting exponentially fewer bits (or qubits) than required by any known classical protocol. The technique encodes a compact “fingerprint” of each input string into a quantum state; a referee can then determine, with high probability, whether the original strings are identical or different by measuring the overlap of the two quantum fingerprints.

Historical Development
The concept was introduced in 2001 by Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf in their seminal paper “Quantum Fingerprinting.” Their work demonstrated that, for the Equality problem (testing whether two n‑bit strings are equal), a quantum protocol using O(log n) qubits of communication could achieve bounded error, whereas any classical deterministic or randomized protocol requires Ω(√n) bits of communication in the worst case.

Subsequent research refined the protocol, explored variations (e.g., one‑way vs. two‑way communication, bounded‑error vs. zero‑error), and extended the technique to related problems such as the Hidden Matching problem and distributed function evaluation.

Technical Overview

1. Setting – Two distributed parties, Alice and Bob, each hold an n‑bit string, x and y respectively. They wish to inform a third party (the referee) whether x = y without revealing the strings themselves. Communication is restricted to a single or few rounds, and the goal is to minimize the total transmitted information.

2. Fingerprint Construction –

   • Classical fingerprinting maps each string to a short hash value; quantum fingerprinting maps each string to a quantum state |ψ_x⟩ in a Hilbert space of dimension d ≈ poly(log n).
   • A common construction uses pairwise‑independent hash functions h: {0,1}ⁿ → {0,1}^k with k = O(log n), and then prepares the state

$$ |ψ_x⟩ = \frac{1}{\sqrt{2^k}} \sum_{z\in{0,1}^k} (-1)^{h(x)\cdot z},|z⟩ . $$

The state is essentially a Hadamard‑encoded version of the hash of x.

3. Communication – Alice and Bob each send their fingerprint state |ψ_x⟩ and |ψ_y⟩ to the referee. The total quantum communication is O(log n) qubits.

4. Measurement – The referee performs a joint measurement (often a swap test) to estimate the inner product ⟨ψ_x|ψ_y⟩.

   • If x = y, the inner product equals 1, leading the swap test to output “equal” with high probability.
   • If x ≠ y, the inner product is bounded away from 1 (typically ≤ 1 − ε for some constant ε), causing the test to output “different” with probability at least 1 − δ, where δ can be made arbitrarily small by repeating the protocol a constant number of times.

5. Error Analysis – The protocol achieves bounded error (two‑sided error probability ≤ 1/3, reducible via repetition). The communication complexity is O(log n) qubits, an exponential improvement over the classical Ω(√n) lower bound for randomized protocols with comparable error.

Key Advantages

• Communication Efficiency – Drastically reduces the number of transmitted bits/qubits for equality testing.
• Privacy – The quantum fingerprints reveal essentially no information about the original strings beyond the equality result.
• Robustness – Protocols can be adapted to tolerate noise and imperfect quantum operations using error‑correcting codes or repeated measurements.

Applications and Extensions

• Distributed Computing – Used as a subroutine in protocols for set disjointness, graph property testing, and other communication‑complexity problems.
• Quantum Cryptography – Forms the basis for fingerprint‑based authentication schemes and quantum token verification.
• Experimental Demonstrations – Laboratory implementations have realized quantum fingerprinting with photonic qubits and linear‑optical circuits, confirming the theoretical communication advantage in practice (e.g., experiments by Arrazola & Lütkenhaus, 2014; Arrazola et al., 2017).
• Complexity Theory – Serves as an illustrative example of quantum advantage in the simultaneous‑message‑passing model and informs separations between quantum and classical communication complexity classes.

Limitations

• Physical Resources – Requires the ability to generate, transmit, and jointly measure coherent quantum states across potentially long distances. Current technology limits the size of n for which practical advantages are observed.
• Error Sensitivity – The protocol’s correctness depends on maintaining high‑fidelity quantum states; decoherence and photon loss can degrade performance, necessitating error mitigation techniques.
• Model Specificity – The exponential advantage holds in the simultaneous‑message‑passing model; in other communication models (e.g., interactive protocols) the relative gap may be smaller.

References (selected)

1. H. Buhrman, R. Cleve, J. Watrous, R. de Wolf, “Quantum Fingerprinting,” Physical Review Letters, vol. 87, no. 167902, 2001.
2. R. Arrazola, N. Lütkenhaus, “Quantum fingerprinting with coherent states and constant mean photon number,” Physical Review A, vol. 89, 062302, 2014.
3. S. Aaronson, “The learnability of quantum states,” Proceedings of the 44th ACM Symposium on Theory of Computing, 2012 – discusses implications for communication complexity.

See also

• Quantum communication complexity
• Swap test (quantum algorithm)
• Classical fingerprinting (hashing)
• Simultaneous‑message‑passing model

This entry adheres to an objective, fact‑based presentation and reflects the current scholarly consensus on quantum fingerprinting.