Efficient quantum communications with multiplexed coherent state fingerprints

We provide the first example of a communication model and a distributed task, for which there exists a realistic quantum protocol which is asymptotically more efficient than any classical protocol, both in the communication and the information resources. For this, we extend a recently proposed coherent state mapping for quantum communication protocols, introduce the notion of multiplexed coherent state fingerprints and show how to use them to design an efficient quantum protocol for estimating the Euclidean distance of two real vectors within a constant factor.