One of the standard communication complexity problems is deciding whether bit strings held by two separate parties Alice (A) and Bob (B) are equal or different. In the simultaneous message passing model, A and B send certain information to a Referee, who makes the decision. The overall goal is to minimize the amount of communication involved while not exceeding desired error probability. This is achieved by sending only fingerprints of the original n-bit strings. In the best classical protocols, these scale as O(√n) if A and B have no access to shared randomness [1]. The recently proposed [2] and demonstrated quantum fingerprinting [3], exploiting phase-modulated weak coherent pulses, provides O(log2n) scaling in the number of used qubits, but needs phase stability between A and B. Here we introduce and analyse a quantum fingerprinting protocol based on two-photon interference which does require a shared phase reference and works in scenarios when the global phase of transmitted signals becomes completely random. Interestingly, the performance of this protocol, quantified in terms of the Chernoff information [4], is enhanced through the use of non-classical single-photon states, even in the regime of high transmission loss.
We present a quantum fingerprinting protocol relying on two-photon interference which does not require a shared phase reference between the parties preparing optical signals carrying data fingerprints. We show that the scaling of the protocol, in terms of transmittable classical information, is analogous to the recently proposed and demonstrated scheme based on coherent pulses and first-order interference, offering comparable advantage over classical fingerprinting protocols without access to shared prior randomness. We analyze the protocol taking into account non-Poissonian photon statistics of optical signals and a variety of imperfections, such as transmission losses, dark counts, and residual distinguishability. The impact of these effects on the protocol performance is quantified with the help of Chernoff information.
Quantum fingerprinting allows two remote parties to determine whether their datasets are identical or different by sending exponentially less information compared to the classical protocol with equivalent performance. Optical implementations of the quantum protocol based on weak coherent states have been proposed and realized. However, in these realizations phase stability between the sending parties is required. Here we analyze the practical feasibility of the recently introduced quantum fingerprinting protocol based on higher-order interference, which does not require a phase lock between transmitters. We show that an experimental demonstration of a quantum fingerprinting protocol beating the known bound on the performance of classical schemes should be possible using currently available technology.
We introduce several families of quantum fingerprinting protocols to evaluate the equality function on two
n-bit strings in the simultaneous message passing model. The original quantum fingerprinting protocol uses a tensor product of a small number of
O(logn)-qubit high-dimensional signals [H. Buhrman et al., Phys. Rev. Lett. 87, 167902 (2001)], whereas a recently proposed optical protocol uses a tensor product of
O(n) single-qubit signals, while maintaining the
O(logn) information leakage of the original protocol [J. M. Arazola and N. L\"utkenhaus, Phys. Rev. A 89, 062305 (2014)]. We find a family of protocols which interpolate between the original and optical protocols while maintaining the
O(logn) information leakage, thus demonstrating a tradeoff between the number of signals sent and the dimension of each signal. There has been interest in experimental realization of the recently proposed optical protocol using coherent states [F. Xu et al., Nat. Commun. 6, 8735 (2015); J.-Y. Guan et al., Phys. Rev. Lett. 116, 240502 (2016)], but as the required number of laser pulses grows linearly with the input size
n, eventual challenges for the long-time stability of experimental setups arise. We find a coherent state protocol which reduces the number of signals by a factor
21 while also reducing the information leakage. Our reduction makes use of a simple modulation scheme in optical phase space, and we find that more complex modulation schemes are not advantageous. Using a similar technique, we improve a recently proposed coherent state protocol for evaluating the Euclidean distance between two real unit vectors [N. Kumar et al., Phys. Rev. A 95, 032337 (2017)] by reducing the number of signals by a factor
21 and also reducing the information leakage.
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
O(log2n) qubits, thus exhibiting an exponential separation in abstract 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 transmits an amount of information that can be more than two orders of magnitude smaller than a classical fingerprinting protocol.
Quantum fingerprinting (QF) promises exponential reduction of information transmission in executing communication complexity tasks. Practicality and quantum advantage of this novel protocol has been recently demonstrated using weak coherent pulses to carry the fingerprinting information. However, all coherent QF implementations rely upon a direct optical link to maintain coherence between the users, which does not comply with the protocol's rule that the users must not have any access to a shared randomness. To close this loophole, we propose, and experimentally demonstrate, a novel protocol based on asynchronous coincidence pairing from the interference result between coherent optical fields that are remotely and independently prepared. Over a length of 20 km telecom fiber, our QF setup has outperformed the best-known classical algorithm, for the first time without being susceptible to shared randomness. Our result paves the way toward practical applications of QF in communication complexity.