{'fraction_non_alphanumeric': 0.0296228539262595, 'fraction_numerical': 0.014213340838727835, 'mean_word_length': 4.682926829268292, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Observation of quantum fingerprinting beating the classical limit

Quantum communication has historically been at the forefront of advancements, from fundamental tests of quantum physics to utilizing the quantum-mechanical properties of physical systems for practical applications. In the field of communication complexity, quantum communication allows the advantage of an exponential reduction in the information transmitted over classical communication to accomplish distributed computational tasks. However, to date, demonstrating this advantage in a practical setting continues to be a central challenge. Here, we report an experimental demonstration of a quantum fingerprinting protocol that for the first time surpasses the ultimate classical limit to transmitted information. Ultra-low noise superconducting single-photon detectors and a stable fibre-based Sagnac interferometer are used to implement a quantum fingerprinting system that is capable of transmitting less information than the classical proven lower bound over 20 km standard telecom fibre for input sizes of up to two Gbits. The results pave the way for experimentally exploring the advanced features of quantum communication and open a new window of opportunity for research in communication complexity and testing the foundations of physics.

computational tasks 4 . It not only has many connections to the foundational issues of quantum mechanics 5,17 , but also has important applications for the design of communication systems, green communication techniques, computer circuits and data structures 18 . For instance, QCC essentially connects the foundational physics questions regarding nonlocality with those of communication complexity studied in theoretical computer science 5 .
Quantum fingerprinting, proposed by Buhrman, Cleve, Watrous and Wolf, is the most appealing protocol in QCC 19 . Specifically, the simultaneous message-passing model 3 corresponds to the scenario where two parties, Alice and Bob, respectively receive inputs x a , x b ∈ {0, 1} n and send messages to a third party, Referee, who must determine whether x a equals x b or not, with a small error probability . This model has two requirements: (i) Alice and Bob do not have access to shared randomness; (ii) there is one-way communication to Referee only. Alice and Bob can achieve their goal by sending fingerprints of their original inputs that are much shorter than the original inputs. It has been shown that the optimal classical protocols require fingerprints of a length that is at least O( √ n) 21,22 , while, using quantum communication, Alice and Bob need to send fingerprints of only O(log n) qubits 19,20 . Therefore, when the goal is to reduce the transmitted information, quantum communication provides an exponential improvement over the classical case. Despite this advantage, demonstrating it in a practical setting continues to be a challenge 5 .
Recently, a coherent-state quantum fingerprinting protocol for the realization using linear optics was proposed by Arrazola and Lütkenhaus 23 . On the basis of this protocol, Xu et al. reported a proof-of-concept implementation that transmits less information than the best known classical protocol 9 . Nonetheless, as noted already in ref. 9 , a remaining question is "whether quantum fingerprinting can beat the classical theoretical limit of transmitted information." This limit has been proven to be roughly two orders of magnitude smaller than the best known classical protocol 22 , and surpassing it has been a long-standing experimental challenge. In this work, a quantum fingerprinting system is designed and demonstrated that for the first time beats the classical limit to transmitted information by up to 84%.
As illustrated in Fig. 1, the experiment adopted the coherent-state quantum fingerprinting protocol 23 . The detailed description of the protocol is presented in Table 1. It has been proven that the quantum information Q that can be transmitted by sending the sequence of weak coherent states satisfies 23 where µ is defined as the total mean photon number in the entire pulse sequence. An important feature of the protocol is to fix µ to a small constant, which restricts the transmitted information (see Methods for details). For a fixed µ, Q corresponds to an exponential improvement over the classical case of O( √ n) bits 21,22 , which precisely provides the quantum advantage.
To implement the coherent-state quantum fingerprinting protocol, the experiment utilizes a fibre-based Sagnac-type interferometer, as sketched in Fig. 2 (see Methods for the details). In this set-up, since the two pulses, sent from Referee to Alice and Bob, travel exactly the same path in the interferometer, two remarkable features are automatic compensation of the phase differences between the two pulses and high interference visibility. In experiment, one challenge is that Alice (Bob) should ensure that her (his) phase modulator (PM) modulate only the signal pulse, i.e., the one that returns from Bob (Alice), instead of the compensation pulse, i.e., the pulse that is sent directly from Referee. To do so, specific lengths of fibres and electrical cables are designed to separate the signal pulse from compensation pulse with 20 ns difference, and to carefully control the electrical gating signals applied to the PMs. Another challenge is that the coherent-state quantum fingerprinting protocol 23 requires the operation of the system at an ultra-low mean photon number, which is well below 10 −7 per pulse. Indeed, as can be deduced from Eq. (1), a lower mean photon number leads to a reduction in the transmitted information, which permits the demonstration of beating the classical limit. To properly detect such a weak signal, advanced SNSPDs with on-chip narrow-band-pass filters 25,26 are installed. These SNSPDs have an ultra-low dark count rate of about 0.11 Hz and a high quantum efficiency of 45.6% at 1532nm wavelength.
To surpass the classical limit, the losses should be carefully controlled. The overall transmittance of Referee's PBS and BS is 80.16% (78.5%) from Alice (Bob) to Referee. The system is implemented with total distances (from Alice to Bob) of 0 km, 10 km and 20 km fibre spools, whose losses are characterised to be about 0 dB, 1.86 dB and 3.92 dB respectively. The distances between Alice (or Bob) and the referee are 0 km, 5 km and 10 km. Under each distance, five different message sizes n are chosen as 2 × 10 6 , 4 × 10 7 , 1.42 × 10 8 , 1 × 10 9 , and 2 × 10 9 . For each message, an ECC is applied based on the Toeplitz-matrices random linear code 9 , which has a rate of R = 0.24 and a minimum distance of δ = 0.22. The random numbers to construct the matrices are generated from a quantum random number generator 27 . Here for a message up to two Gbits, the system requires several hours to transmit the pulses. Hence, a stable interference is essential for the experiment. The stability of the system is monitored, and the result is that, during 24 hours of continuous operation, the overall intensity fluctuations are less than 3.7% and the interference visibility remains over 96%. In the experiment, the key observation parameter is the number of counts on detector D 1 . These experimental results are shown in Fig. 3. The clear difference between the worst-case different inputs with δ = 0.22 difference (blue points) and the identical inputs (red points) makes it possible to run the protocol (see Table 1). In all the runs of experiments, a maximal error probability of = 2.6 × 10 −5 (See Supplementary) was achieved.
The maximum error probability was calculated from the theoretical model of the experiment 9, 23 . The best known classical protocol needs to transmit at least 32 √ n bits of information 22 . On the basis of the references 21, 22 , we prove an optimized bound for the classical limit (see Supplementary) 1 .
This bound is given by Fig. 4a indicates that, with the increase of input size n, the classical limit scales linearly in the log-log plot, while the transmitted quantum information remains almost a constant. The trans-mitted information is up to two orders of magnitude lower than that in the previous experiment 9 .
Importantly, for large n, these experimental results clearly beat the classical limit for a wide range of practical values of the input size. To further illustrate our results, γ is defined as the ratio between the classical limit C limit and the transmitted quantum information Q, i.e., γ = C limit /Q. A value γ > 1 implies that the classical limit is surpassed by our quantum fingerprinting protocol.
In Fig. 4b, γ is plotted as a function of different fibre distances and input data sizes. For the input sizes larger than one Gbit, γ is well above one. The ratio is as large as γ = 1.84, which implies that our quantum fingerprinting implementation beats the classical limit by up to 84%.
Finally, to show the ability of the quantum protocol in the real world, two video files with sizes of two Gbits 28 were experimentally fingerprinted over 20 km fibre. A 14% reduction in the transmitted information was obtained, as compared to the classical limit (see Supplementary Table   4 for details).
To conclude, by using ultra-low dark count superconducting detectors (i.e., ∼ 0.1 Hz), as well as an automatic-phase compensation Sagnac system, a quantum-enhanced method for fingerprinting to beat the ultimate classical theoretical limit was demonstrated. With ∼1300 transmitted photons as the information carrier, two ∼2 Gbits video files were experimentally fingerprinted over 20 km fibres, and the potential for practical applications was thus indicated. In the future, our system can be deployed in the metropolitan fibre network for a field test. Higher detection efficiency SNSPDs 29 can be exploited to increase the transmission distance and reduce the required message length. Alice and Bob can also hold independent laser sources and apply the phase-locking techniques to interfere the weak coherent pulses. Last but not least, we point that many connections between communication complexity and foundational issues of quantum mechanics have been recently discovered 5 . In particular, quantum communication complexity is intimately linked to quantum nonlocality. Our experiment provides a first step in the development of experimental quantum communication complexity, which could even lead new proposals for experiments that test the foundations of physics.

Methods
Transmitted information. In the coherent-state quantum fingerprinting protocol, the sequence of coherent states prepared by Alice and Bob are given by 23 Here E(x a ) j (E(x b ) j ) is the jth binary bit of Alice's (Bob's) codeword, α is a complex amplitude, and θ j -which is assumed to be the same for Alice and Bob -is the global phase of jth pulse. We define µ := |α| 2 as the total mean photon number in the entire pulse sequence. The states of Eq. (3) can be understood as a coherent-state version of an encoding of m-dimensional quantum states into states of a single photon across m modes 23 . Importantly, by fixing µ to a small constant, we are restricting ourselves to an exponentially small subspace of the larger Hilbert space associated with the optical modes. This in turn restricts the capability of these systems to transmit information.
Thus, to achieve the central goal of a reduction in the transmitted information, our protocol must use a number of modes that is linear in the input size n, with the significant advantage that the total mean photon number µ is very small. In particular, the number of photons used is more than quadratically smaller than in a classical protocol using photonic bits, where O( Similarly, the right pulse from the referee travels to Bob for a polarization compensation first and then goes to Alice for encoding according to Alice's codeword E(x a ). Finally, the left pulse and the right pulse return simultaneously at Referee's polarization maintaining BS, where they interfere and are detected by two superconducting nanowire single photon detectors (SNSPDs). In front of the SNSPD, PC is used to optimize the detection efficiency. A time-to-digital converter records all the detected events and a 2.5 ns effective time window is used to detect the pulses.
The electric signals that control the optical devices are generated from a AWG70002 waveform generator (manufactured by Tektronix).  and observes the clicks at the outputs of the BS, using two single-photon detectors, which are labelled "D 0 " and "D 1 ". This process allows Referee to verify whether the relative phases of the incoming pulses are same or different 24 . In an ideal situation, a click in detector D 1 will never happen if the phases of the incoming states are equal.

Decision.
In the presence of experimental imperfections such as detector dark counts and imperfect interference, detector D 1 may fire even when the inputs are equal. However, in a case of small imperfections, the total number of clicks on D 1 for different inputs is much larger than the total number of clicks for equal inputs. A decision rule for Referee is employed on the basis of only the total number of clicks observed in detector D 1 9 . Referee sets a threshold value D 1,th such that, if the number of clicks is smaller than or equal to D 1,th , he will conclude that the inputs are equal. Otherwise, he concludes that they are different.
In the protocol, the value of D 1,th is chosen in such a way that an error is equally likely to occur in both cases.  information of our experimental quantum fingerprinting protocol is much lower than the transmitted information of the best known classical algorithm. For large n, our results are, in strict terms, better than the classical limit for a wide range of practical values of the input size. b, The ratio γ between classical limit C limit and the transmitted quantum information Q. For the three small input sizes, no advantage over the classical limit was obtained. However, for the two large input sizes, the ratio is well above one over different fibre distances. Our experiment transmitted as much as 84% less information than the classical limit.