  We present a protocol for quantum fingerprinting that is ready to be
implemented with current technology and is robust to experimental errors. The
basis of our scheme is an implementation of the signal states in terms of a
coherent state in a superposition of time-bin modes. Experimentally, this
requires only the ability to prepare coherent states of low amplitude, and to
interfere them in a balanced beam splitter. The states used in the protocol are
arbitrarily close in trace distance to states of $\mathcal{O}(\log_2 n)$
qubits, thus exhibiting an exponential separation in communication complexity
compared to the classical case. The protocol uses a number of optical modes
that is proportional to the size $n$ of the input bit-strings, but a total mean
photon number that is constant and independent of $n$. Given the expended
resources, our protocol achieves a task that is provably impossible using
classical communication only. In fact, even in the presence of realistic
experimental errors and loss, we show that there exist a large range of input
sizes for which our quantum protocol requires communication that can be more
than two orders of magnitude smaller than a classical fingerprinting protocol.

Quantum Physics