Classical and Quantum Fingerprinting in the One-Way Communication Model

Farid Mansurovich Ablayev, Alexander Vasiliev

A.J. Scott, Jonathan Walgate, Barry C. Sanders

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. In the simultaneous message passing model, it is known that fingerprints composed of quantum information can be made exponentially smaller than those composed of classical information. For small message lengths, we present constructions of optimal classical fingerprinting strategies with one-sided error, in both the one-way and simultaneous message passing models, and provide bounds on the worst-case error probability with the help of extremal set theory. The performance of these protocols is then compared to that for quantum fingerprinting strategies constructed from spherical codes, equiangular tight frames and mutually unbiased bases.

Atsuya Hasegawa, Srijita Kundu, François Le Gall +2 more

Buhrman, Cleve, Watrous, and de Wolf (PRL 2001) discovered the quantum fingerprinting protocol, which is the quantum SMP protocol with $O(\log n)$ qubits communication for the equality problem. In the protocol, Alice and Bob create some quantum fingerprints of their inputs, and the referee conducts the SWAP tests for the quantum fingerprints. Since $Ω(\sqrt{n})$ bits communication is required with the classical SMP scheme for the equality problem first shown by Newman and Szegedy (STOC 1996), there exists an exponential quantum advantage in the amount of communication. In this paper, we consider a setting in which the referee can do only incoherent measurements rather than coherent measurements including the SWAP tests. We first show that, in the case of one-way LOCC measurements, $Ω(\sqrt{n})$ qubits communication is required. To prove the result, we derive a new method to replace quantum messages by classical messages and consider a reduction to the optimal lower bound in the hybrid SMP model where one message is quantum and the other is classical, which was first shown by Klauck and Podder (MFCS 2014). Our method uses the result of Oszmaniec, Guerini, Wittek, and Acín (PRL 2017), who showed that general POVM measurements can be simulated by randomized projective measurements with small ancilla qubits, and Newman's theorem. We further investigate the setting of quantum SMP protocols with two-way LOCC measurements, and derive a lower bound against some restricted two-way LOCC measurements. To prove it, we revisit the technique to replace quantum messages by classical deterministic messages introduced by Aaronson (ToC 2005) and generalized by Gavinsky, Regev, and de Wolf (CJTCS 2008), and show that, using the deterministic message, the referee can simulate the two-way LOCC measurements.

Rahul Jain, Shengyu Zhang

Andreas Winter

R.T. Horn, A.J. Scott, Jonathan Walgate +3 more

Within the simultaneous message passing model of communication complexity, under a public-coin assumption, we derive the minimum achievable worst-case error probability of a classical fingerprinting protocol with one-sided error. We then present entanglement-assisted quantum fingerprinting protocols attaining worst-case error probabilities that breach this bound.