Research Article  Open Access
MinGang Zhou, XiaoYu Cao, YuShuo Lu, Yang Wang, Yu Bao, ZhaoYing Jia, Yao Fu, HuaLei Yin, ZengBing Chen, "Experimental Quantum Advantage with Quantum Coupon Collector", Research, vol. 2022, Article ID 9798679, 11 pages, 2022. https://doi.org/10.34133/2022/9798679
Experimental Quantum Advantage with Quantum Coupon Collector
Abstract
An increasing number of communication and computational schemes with quantum advantages have recently been proposed, which implies that quantum technology has fertile application prospects. However, demonstrating these schemes experimentally continues to be a central challenge because of the difficulty in preparing highdimensional states or highly entangled states. In this study, we introduce and analyze a quantum coupon collector protocol by employing coherent states and simple linear optical elements, which was successfully demonstrated using realistic experimental equipment. We showed that our protocol can significantly reduce the number of samples needed to learn a specific set compared with the classical limit of the coupon collector problem. We also discuss the potential values and expansions of the quantum coupon collector by constructing a quantum blind box game. The information transmitted by the proposed game also broke the classical limit. These results strongly prove the advantages of quantum mechanics in machine learning and communication complexity.
1. Introduction
The “second quantum revolution” is aimed at exploring the superiority of quantum resources over classical resources in terms of communication, computation, and artificial intelligence. To demonstrate that this goal is feasible in practice, a series of schemes with quantum advantages were experimentally implemented. These schemes included improving on the security of communication [1–12], enhancing computational power for specific tasks [13–25], and reducing the necessary resources used to complete specific communication tasks [26–31]. In addition, machine learning can extract useful knowledge from data, which can then have a significant impact on productivity, technology, and the economy [32]. This has led to an increasing interest in the question of quantum machine learning [33]: Can we improve machine learning by using quantum resources? Owing to the unique entanglement properties of quantum states, quantum models may be able to produce atypical patterns that cannot be effectively produced by classical models or effectively reduce training time. Therefore, some studies have made bold attempts. For example, in Ref. [34], a quantum autoencoder that can successfully denoise specific quantum states subjected to specific noises was developed. Reference [35] described a quantum neural network that can accurately recognize quantum states associated with a onedimensional symmetryprotected topological phase. Moreover, there are several other excellent studies [36–41].
On the other hand, most of these attempts are heuristic and have not theoretically proven that quantum machine learning exhibits a better performance or shorter training time than classical machine learning. The training time of a model includes the time complexity of the learning algorithm. If the algorithm takes a constant amount of time for processing each sample, the concern for the time complexity translates into a concern of the sample complexity. Probably approximately correct (PAC) learning theory [42, 43] provides the minimum number of samples necessary for a learning algorithm to complete a learning task. Researching quantum machine learning using this theory can therefore lay a positive theoretical foundation for exploring quantum advantages in machine learning.
For the first time, Ref. [44] described the use of PAC learning theory to rigorously prove that quantum technology can provide a learning algorithm with quantum advantage for machine learning. The method applied clever quantum measurements to the learning task known as the “coupon collector problem” [45]. Specifically, Ref. [44] gives a surprising result: for the coupon collector problem, the sample complexity of the quantum learning algorithm does not change with changes in the search space of the algorithm. This result is impossible in classical machine learning [42]. However, the experimental demonstration of this algorithm [44] requires highdimensional states that are difficult to prepare. Even if these states are decomposed into a tensor product of qubits, these qubits must be highly entangled [26, 46, 47]. These requirements are far beyond the scope of current technology. More seriously, the algorithm requires a specific projective measurements, which is difficult to implement in experiment.
In this work, we experimentally demonstrate the quantum coupon collector algorithm by proposing a coherentstate quantum coupon collector protocol. Our protocol avoids the abovementioned difficulties. To do this, our protocol not only maintains the important properties of the original one but also introduces new conceptual tools that can be implemented using only linear optics operations and singlephoton detectors. Even without a quantum computer, these tools enable us to demonstrate the quantum advantages in machine learning at the current technological level. Moreover, the coupon collector problem can be considered as a communication task. Similar to quantum fingerprinting [27, 28], our protocol also experimentally demonstrates the advantages of quantum mechanics in the context of communication complexity. These results, in addition to their fundamental interest [48–50], will further inspire new designs of communication systems, largescale integration circuit designs, and data structures [51], thus paving the way for other communication or computational tasks that rely on similar principles.
2. Results
2.1. CoherentState Quantum Coupon Collector Protocol
To clearly describe our protocol, we briefly introduce the coupon collector problem [45]. This problem can be abstracted as learning exactly an unknown set . Specifically, this set is limited to a subset of the set , where the size of set is known. To learn the set , several copies of are given, and only one element is allowed to be extracted from each copy. The task is to determine the minimum number of copies required to learn exactly.
Because the elements in are independent of each other, the best strategy for learning is to randomly extract one of these elements in each copy. Under this strategy, if distinct elements have been obtained, the expected number of copies needed to learn the th element is . Therefore, the expected number of copies needed to learn is . Continuing based on this, Ref. [45] shows that copies are necessary and sufficient for learning with a high probability.
However, if these copies are quantum copies in the form of , the number of copies required can be further reduced. This is because we can perform more quantum operations on before measuring them on the computational basis. In other words, by using quantum copies , the strategy for learning is no longer limited to random sampling. Reference [44] shows that when the number of missing elements is very small, the number of copies of used to learn is reduced to . The method first performs a outcome projective measurement with operators and on copies of , where . After the measurement, the second outcome is obtained with probability , where is the set of missing elements, and . Then, is measured on the computational basis to obtain the missing elements. This method transforms into and then infers the elements in by learning the elements in from . Because has fewer elements, this method reduces the number of copies required to learn .
However, difficulties arise when we attempt to demonstrate this method experimentally. This is because it is difficult to experimentally construct a single dimensional quantum state [52–54]. Even if this state is decomposed into a tensor product of qubits, these qubits must be highly entangled [26, 46, 47]. This is also not feasible using current technology. More seriously, the operators and in this method are difficult to implement in experiments.
Therefore, we introduce an alternative scheme, which is defined as the “coherentstate quantum coupon collector protocol.” This scheme maintains the main idea of the original one, which is to learn by measuring the missing elements. In addition, this scheme uses a sequence of coherent states to implement copies of . Coherent states are easy to prepare and can be transformed using simple linear optical elements. Therefore, this scheme is particularly attractive from a practical point of view.
In our scheme, copies of are implemented using a time sequence of weak coherent optical pulses where is a complex number and is a coherent state with amplitude at the th time mode, where for and otherwise. The phases of these coherent pulses depend on , but their intensities are the same. Thus, the state has the mean photon number . Note that is given by projecting the state into the singlephoton subspace. The total intensity of represents the number of copies of . However, our scheme uses instead of . In other words, when , our scheme sends state instead of a vacuum state. This method can improve the efficiency of detecting missing elements, but it also causes the number of copies by our scheme to be slightly different from those of a scheme using . Specifically, the number of copies by our scheme are at most . For comparison, the number of copies by a scheme using is at most . However, as we will see later, this subtle difference can be ignored, and using greatly improves the efficiency of detecting missing elements.
As we discussed previously, our scheme maintains the important characteristics of the original one; that is, the time bin of state in is found through complementary measurements, and the elements in are derived from these time bins. To do this, a local state is prepared and sent to a 50 : 50 beam splitter (BS) to interfere with (Figure 1(a)), where
The interference result is recorded by a singlephoton detector . If the detector clicks at the th time bin, then we consider the pulse of the th time bin in to be . Thus, all time bins containing in can be learned exactly from the outcomes of the detector . Without loss of generality, let Alice be a coupon maker and Bob be a coupon collector. Bob’s task is to learn all elements in from the state prepared by Alice. The detailed steps are described as follows: (1)Alice selects elements from set as set and selects an appropriate value as the intensity of each pulse(2)Alice encodes the pulses according to and the intensity ; if , Alice prepares a coherent pulse at the th time bin and sends it to Bob; otherwise, Alice sends to Bob(3)Alice announces the value of , the elements of , and the size of (4)Bob encodes the pulses according to and intensity : Bob prepares a coherent pulse for all time bins(5)Bob uses a 50 : 50 beam splitter and two singlephoton detectors to perform interference measurements on the pulses and (6)Bob records whether the detector clicks or not at each time bin, and then learns exactly based on the outcomes of the detector and the size of the set
At each time bin , the output state after the BS is . Because is unnecessary in this work, it is not drawn in Figure 1(a). It is easy to verify that in the ideal case, the value of determines whether the pulses output by the BS go to or , thus helping Bob to learn the state .
However, even under ideal conditions, the proposed scheme has an intrinsic failure probability. This is because a coherent pulse may collapse to a vacuum state after being measured and thus cannot be detected by detector . Specifically, when Alice sends the coherent pulse , will never click. Therefore, Bob can always obtain the correct results. However, when Alice sends a coherent pulse , the detector has a nonclick probability of (the detection efficiency is assumed to be 100% in the ideal case). Note that if Alice sends a vacuum state when , then the nonclick probability of is increased to . This is why when , our scheme sends instead of a vacuum state. Only when detector detects all sent by Alice can we infer the elements in . Therefore, the success probability of our scheme without experimental imperfections is , where is the number of missing elements of . Note that although the use of the coherentstate sequence for implementing copies of is easier to demonstrate experimentally, it also introduces an intrinsic failure probability. Fortunately, as we will see later, this failure probability is negligible compared to the failure probability introduced by experimental imperfections.
To demonstrate the quantum advantage of our scheme experimentally, we need to eliminate the influence of the failure probability as much as possible. On the one hand, we can reduce the failure probability by increasing the mean photon number per coherent pulse. On the other hand, we can calculate the required number of copies based on the expectation of 100% success. However, these methods increase the number of copies required. Therefore, the selection of an appropriate mean photon number is particularly important.
2.2. Protocol in the Presence of Experimental Imperfections
So far, we have only discussed the success probability of our protocol under ideal conditions. However, owing to experimental imperfections, the success probability formula of our protocol must be modified. We consider imperfect experimental models characterized by three parameters: the combined effects of limited detector efficiency and channel loss , dark count rate of the singlephoton detector, and the limited visibility of the interferometer.
By replacing with , we can eliminate the effect of without changing the form of the success probability formula. However, and will cause to click at incorrect time bins with a nonzero probability; thus, the success probability formula must be modified. In this case, when Alice sends a pulse , the probability that detector clicks is given by and when Alice sends a pulse , the probability that the detector clicks is
Because may click when Alice sends and may not click when Alice sends , the number of clicks of the detector may be different from the size of . In this case, Bob can determine that the experimental results are not available and must be discarded. Therefore, Alice and Bob need to repeat multiple experiments to obtain usable experimental data. Here, we define a new efficiency to measure the ratio of the number of available experimental results of the total number of experiments, which can be calculated by the following formula: where represents the sum of the probabilities of all possible cases where detects out of coherent states sent by Alice, and represents the sum of the probabilities of all possible cases where detects out of coherent states sent by Alice.
In addition, even if Bob obtains usable experimental results, has a probability of clicking at the wrong time bin, thus making him misjudge the elements in . This requires us to define the correct probability when the experimental results are available. Thus, the success probability is modified to . Based on the expectation of 100% success, the number of quantum samples required to complete the task is
Without loss of generality, we choose a special set to verify the quantum advantage of our protocol, where and size . Therefore, the correct probability can be simplified as
Based on the above formulae, we present the numerical simulation in Figures 1(b) and 1(c). The simulation results also guide our experimental demonstration. Figure 1(b) shows that a higher intensity results in a higher correct probability . This is because can more easily detect a higher intensity sent by Alice. In contrast, as the visibility of the interferometer is not perfect, higher intensity also increases the probability of clicking when Alice sends . These two factors lead to the experimental efficiency and success probability increasing first and then decreasing with an increase in light intensity. directly affects the number of quantum samples required to complete the task. Therefore, we must choose an appropriate light intensity to achieve a balanced tradeoff between improving the correct probability and reducing quantum resources.
Figure 1(c) shows a comparison between the resources required by our protocol and the size of the set with the correct probability . To highlight our quantum advantage, we also draw the classical limit of the required samples for comparison. The cost of our protocol is lower than the classical limit when . When , the samples required by our protocol are less than half of those required by the classical protocols.
Note that the objective of this article was to construct a specific computational task for experimentally demonstrating quantum advantages in the context of machine learning and communication complexity. Therefore, to simplify the implementation of our protocol, we do not consider the case in which Alice sends incorrect coherent pulses to Bob. In fact, this case belongs to a more complex communication task and is beyond the scope of this article.
3. Experimental Setup and Results
We used linear optics components and singlephoton detectors to present a proofofprinciple experimental demonstration of the coherentstate quantum coupon collector protocol (Figure 2(a)). First, the continuouswave light with a wavelength of 1550.12 nm emitted by a laser source was carefully modulated into optical pulses at a repetition rate of 312.5 MHz by using an intensity modulator (IM). To make the modulated waveform as perfect as possible, the modulated light was monitored by a singlephoton detector instead of an oscilloscope during the modulation phase. Then, the modulated optical pulses were attenuated to the desired level by a variable optical attenuator (VOA) and separated by a 50 : 50 BS into two identical pulse sequences and . These two pulse sequences travel clockwise and counterclockwise in the Sagnac loop. After passing through a phase modulator (PM), the clockwise pulse sequence is modulated to according to the value of the coupon . To convert the counterclockwise sequence into the local state , the PM is turned off when passes through it. We used the Sagnac loop to automatically stabilize the phase fluctuation of the channel to improve interference visibility. In addition, to make the two pulse sequences pass through the PM at different times, one arm of the Sagnac loop was designed to be 1 m longer than the other arm. The optical circulator was used to prevent the previous optical pulses transmitted back by the BS from affecting the subsequent optical pulses. Finally, the interference results were detected using a superconducting nanowire singlephoton detector ().
Our scheme combines all copies of the required to learn into a sequence of coherent states. Compared with a state that consists of a single photon in modes, the coherentstate sequence is easier to prepare. Moreover, combining all copies of enhances the mean photon number of each time mode of the coherentstate sequence, thus increasing the probability of measuring each mode. These features make our scheme easier to implement in experiments and more effective.
Note that we can only learn correctly if each element is correctly classified as or . Therefore, even if and have a small effect on a single pulse, it is difficult to correctly classify all elements when is very large. This means that and limit the maximum size of that our protocol can achieve quantum advantage with a given correct probability. However, in our experiment, because can reach the order of under the current experimental conditions, the effects of the random detection events caused by can be ignored. In contrast, the maximum visibility of an interferometer that can be achieved in a laboratory is on the order of . As a result, seriously limits the success probability of learning , even if the size of is relatively small. In addition, directly affects the number of quantum samples required to complete the task. Therefore, and are the experimental parameters that need to be improved. When the accuracy of is improved in the future, our protocol can also achieve quantum advantage over with a larger size.
To improve the success probability, we selected a BS whose visibility in the Sagnac loop was nearly 99.9993%. We also reduced the magnitude of the dark count probability to . At this magnitude, the dark count probability hardly affects the system performance. In addition, we tried to adjust the amplitude of the radiofrequency signal driving the PM to achieve an accurate phase shift. However, it is almost impossible for a PM to apply a perfect phase shift on a specific pulse without influencing other pulses in a period, especially as the duty cycle in this experimental demonstration is on the order of . Consequently, the number of clicks caused by the pulses in a coupon period is much higher than theoretically expected, which means that the experimental interference visibility is lower than that of the BS. Fortunately, during data processing, we found that selecting certain time windows can significantly improve the visibility for interference. However, this approach inevitably filters out certain detection events, thereby affecting the final success probability. By repeatedly selecting different time windows, we achieved a better tradeoff between improving visibility and reducing detection events, thereby reducing the number of quantum samples of different coupon lengths.
The experiment was performed with different sizes of the set ranging from 2000 to 18000. For each size , we ran the experiment for 5 s and analyzed the detection results. The relevant experimental parameters are listed in Figure 2(c). The detailed results are listed in Table 1. Our protocol consumes fewer samples than the classic protocol for (Figure 2(b)). The gray area in Figure 2(b) indicates the region in which our protocol consumes more samples than the classical one. By choosing different time windows, we set for and for . Note that these visibility levels are approximate values based on experimental data. To achieve better experimental results, we did not choose the time window with the most detection events, but the window with the highest visibility. The result is that only a fraction of the photons were detected, which is equivalent to reducing the detection efficiency of detector . Therefore, the intensities of the coherentstate pulses were modulated much higher than theoretically expected in this experiment. Furthermore, because the quantum resources consumed in our protocol are proportional to the intensity of each pulse in , the degree of photon dissipation directly affects the results of the experiment. When the photon dissipation is larger, a higher intensity is required to compensate for the photon dissipation, thus consuming more quantum resources. Therefore, in our experiments, we strive to improve the channel efficiency between Alice and and the detection efficiency to reduce the consumed quantum resources. Reducing the voltage fluctuations of the phase modulator and selecting a better time window can further improve the experimental results.

3.1. Quantum Blind Box
Our protocol can not only be used to verify quantum advantage in machine learning from the PAC theory but can also be regarded as a communication task to demonstrate quantum advantage in communication complexity. To this end, we designed a specific application scenario for our protocol, which is called a quantum blind box game. In this game (Figure 3(a)), Alice acts as a merchant, and Bob acts as a customer. Alice prepares small balls with different patterns and packs them in boxes to form blind boxes. Alice then takes of these boxes as a blind box system, where , and encodes the coherent state according to the patterns of the balls in that system. Alice then tells Bob all patterns of the balls and the number of blind boxes in the blind box system.
To determine the patterns contained in the blind box system, Bob uses the same encoding method as Alice to create a local state . The merchant Alice provides the entire measurement system, which is the same as the experimental device shown in Figure 2(a). Bob can decide the total intensity of the coherent state sent by Alice, but the money he needs to pay to Alice is equal to the quantum resources consumed by . The required quantum resources are bits [27, 54]. Therefore, the higher the intensity of , the more money Bob needs to pay. Finally, Bob judges the patterns in the blind box system based on the results of the singlephoton detector . If Bob gives the correct answer, he will be rewarded with dollars, which is the minimum expected value of the information that needs to be transmitted to obtain the correct answer using classic resources. Therefore, when Bob consumes fewer quantum resources than the classical limit, he can obtain a positive return in this transaction.
Let us consider and as an example for demonstrating this game. The experimental results show that for a given value of , the expected quantum resources are significantly affected by the light intensity (Figure 3(b)). The detailed experimental results are presented in Materials and Methods. Note that the comparison used herein is the expected value of the quantum resources spent to obtain the correct answer. When the light intensity is small, Bob will not spend a large amount of resources in each game, but it is also difficult to obtain the correct answer. To obtain the bonus, Bob may need to play multiple games. As a result, the expected value of the quantum resources that he spends has increased. This is the reason why quantum resources at a 0.5 light intensity are relatively high for and .
Figure 3(b) also shows that Bob can break the classical limit by choosing the proper intensity for achieving a positive return. In other words, Bob successfully uses quantum resources to design a better strategy than random extraction in this game. This means that in the quantum blind box game, Alice can also allow customers to design various coding methods and measurement strategies for guessing the blind box. The smaller the expected value of the information required for a strategy designed by a customer, the more he can get in return. Overall, quantum advantage in communication complexity has been successfully demonstrated in experiments through the quantum blind box game. We reasonably expect that the ideas contained in this game can be used to design communication protocols with a lower amount of information needed to complete specified communication tasks.
4. Discussion
Prior works have mainly demonstrated the quantum advantages of improving the security of communication and enhancing computational power for specific tasks. Although many studies have attempted to find the superiority of quantum machine learning, these studies have not theoretically proven the quantum advantages of machine learning. In this work, we propose a coherentstate quantum coupon collector protocol and demonstrate it experimentally by using simple linear optical elements and coherent states. Experimental results show that our protocol can effectively reduce the number of samples required to learn coupons exactly with up to 14000 elements on the basis of a 90% correct probability. Combined with the arguments in Ref. [44], our result strongly demonstrates the quantum advantages of machine learning under current technology. To compare with quantum advantages achieved by other studies, we summarize them in Table 2. Note that our scheme does not resort to immature technologies, such as complicated entangled states or ideal singlephoton sources. This makes our scheme particularly practical, especially for exemplifying the ability of linear optics.

In addition to the demonstration of the quantum advantage of machine learning based on the PAC learning theory for the first time, we also specifically designed a quantum blind box game based on our protocol and experimentally demonstrated quantum advantage in communication complexity through this game. Our protocol does not save resources exponentially like other communication tasks with quantum advantages. Nevertheless, our protocol can still effectively learn the missing elements in the set . We hope that the ideas contained in this game can inspire other useful applications, such as quantum voting.
Overall, despite potential limitations, our study provides new opportunities for the development of quantum machine learning and quantum communication complexity. We expect that the ability of linear optics can help us achieve more quantumadvantaged communication and computational schemes.
5. Materials and Methods
5.1. Selection of Time Windows
As described above, the visibility of the interferometer plays a crucial role in determining the cost in terms of quantum resources. Without phase modulation, in our scheme can easily reach over 99.999%. However, imperfections in PM often cause extra counts in unexpected places, which leads to a decrease in visibility.
Fortunately, we find that the visibility varies when different time windows are chosen, which is why the simulation shown in Figure 2(b) uses two visibilities. The choice of time window also affects the number of detection events. In our experiment, as visibility increased, the number of detected events tended to decrease, which is equivalent to a decrease in the detection efficiency. Therefore, the equivalent detection efficiencies and visibilities for different time windows are different.
To ensure the correct probability , we traverse different time windows to find the minimum value of the expected value of the required quantum resources. For the expected values displayed shown in Figure 2(b), we adapted the corresponding experimental parameters according to the time window.
5.2. Experimental Details of Quantum Blind Box
In the experiment, we correlate the patterns of the balls to the positions of the pulses. The corresponding positions of the balls that are not in the blind box system are loaded with a phase. Therefore, this game can be realized using the experimental setup shown in Figure 2(a).
The system was run at a repetition rate of 10 MHz, and each round was 5 seconds long. The duty cycle of a pulse was approximately 5%. The dark count rate per 5 ns detection gate was approximately . Considering the channel loss, the detection efficiency was approximately 68%. The detailed experimental results are presented in Table 3. The experimental apparatus was the same as that used before.

Data Availability
All data that support the findings of this study are available from the corresponding authors upon reasonable request.
Conflicts of Interest
The authors declare that there are no conflicts of interest regarding the publication of this article.
Authors’ Contributions
Y.F., H.L.Y., and Z.B.C. conceived and supervised the study. M.G.Z. and H.L.Y. built the theoretical model. X.Y.C., Y.S.L., Y.W., Y.B., Z.Y.J., and H.L.Y. designed and performed the experiments. M.G.Z., X.Y.C., Y.S.L., and H.L.Y. analyzed experimental data. M.G.Z., X.Y.C., Y.S.L., H.L.Y., and Z.B.C. cowrote the manuscript, with input from the other authors. All authors have discussed the results and proofread the manuscript. MinGang Zhou, XiaoYu Cao, and YuShuo Lu contributed equally to this work.
Acknowledgments
We gratefully acknowledge the support from the National Natural Science Foundation of China (No. 61801420), the Natural Science Foundation of Jiangsu Province (No. BK20211145), the Fundamental Research Funds for the Central Universities (No. 020414380182), the Key Research and Development Program of Nanjing Jiangbei New Area (No. ZDYD20210101), the KeyArea Research and Development Program of Guangdong Province (No. 2020B0303040001), and the China Postdoctoral Science Foundation (No. 2021M691536).
References
 A. Pappa, P. Jouguet, T. Lawson et al., “Experimental plug and play quantum coin flipping,” Nature Communications, vol. 5, no. 1, p. 3717, 2014. View at: Publisher Site  Google Scholar
 F. Xu, X. Ma, Q. Zhang, H.K. Lo, and J.W. Pan, “Secure quantum key distribution with realistic devices,” Reviews of Modern Physics, vol. 92, no. 2, article 025002, 2020. View at: Publisher Site  Google Scholar
 W.B. Liu, C. L. Li, Y. M. Xie et al., “Homodyne detection quadrature phase shift keying continuousvariable quantum key distribution with high excess noise tolerance,” PRX Quantum, vol. 2, no. 4, article 040334, 2021. View at: Publisher Site  Google Scholar
 Y. Fu, H.L. Yin, T.Y. Chen, and Z.B. Chen, “Longdistance measurementdeviceindependent multiparty quantum communication,” Physical Review Letters, vol. 114, no. 9, article 090501, 2015. View at: Publisher Site  Google Scholar
 W. Zhang, D. S. Ding, Y. B. Sheng, L. Zhou, B. S. Shi, and G. C. Guo, “Quantum secure direct communication with quantum memory,” Physical Review Letters, vol. 118, no. 22, article 220501, 2017. View at: Publisher Site  Google Scholar
 M. Lucamarini, Z. L. Yuan, J. F. Dynes, and A. J. Shields, “Overcoming the ratedistance limit of quantum key distribution without quantum repeaters,” Nature, vol. 557, no. 7705, pp. 400–403, 2018. View at: Publisher Site  Google Scholar
 J. Gu, Y. M. Xie, W. B. Liu, Y. Fu, H. L. Yin, and Z. B. Chen, “Secure quantum secret sharing without signal disturbance monitoring,” Optics Express, vol. 29, no. 20, pp. 32244–32255, 2021. View at: Publisher Site  Google Scholar
 P. Alikhani, N. Brunner, C. Crépeau et al., “Experimental relativistic zeroknowledge proofs,” Nature, vol. 599, no. 7883, pp. 47–50, 2021. View at: Publisher Site  Google Scholar
 Z. Li, X. Y. Cao, C. L. Li et al., “Finitekey analysis for quantum conference key agreement with asymmetric channels,” Quantum Science and Technology, vol. 6, no. 4, article 045019, 2021. View at: Publisher Site  Google Scholar
 Y.B. Sheng, L. Zhou, and G.L. Long, “Onestep quantum secure direct communication,” Scientific Bulletin, vol. 67, pp. 367–374, 2022. View at: Publisher Site  Google Scholar
 G.L. Long and H. Zhang, “Drastic increase of channel capacity in quantum secure direct communication using masking,” Scientific Bulletin, vol. 66, pp. 1267–1269, 2021. View at: Publisher Site  Google Scholar
 Z. Qi, Y. Li, Y. Huang, J. Feng, Y. Zheng, and X. Chen, “A 15user quantum secure direct communication network,” Light: Science & Applications, vol. 10, pp. 1–8, 2021. View at: Publisher Site  Google Scholar
 A. Neville, C. Sparrow, R. Clifford et al., “Classical boson sampling algorithms with superior performance to nearterm experiments,” Nature Physics, vol. 13, no. 12, pp. 1153–1157, 2017. View at: Publisher Site  Google Scholar
 M. Gong, S. Wang, C. Zha et al., “Quantum walks on a programmable twodimensional 62qubit superconducting processor,” Science, vol. 372, no. 6545, pp. 948–952, 2021. View at: Publisher Site  Google Scholar
 H.S. Zhong, H. Wang, Y. H. Deng et al., “Quantum computational advantage using photons,” Science, vol. 370, no. 6523, pp. 1460–1463, 2020. View at: Publisher Site  Google Scholar
 M. A. Broome, A. Fedrizzi, S. RahimiKeshari et al., “Photonic boson sampling in a tunable circuit,” Science, vol. 339, no. 6121, pp. 794–798, 2013. View at: Publisher Site  Google Scholar
 M. Bentivegna, N. Spagnolo, C. Vitelli et al., “Experimental scattershot boson sampling,” Science Advances, vol. 1, no. 3, article e1400255, 2015. View at: Publisher Site  Google Scholar
 H.S. Zhong, L.C. Peng, Y. Li et al., “Experimental gaussian Boson sampling,” Scientific Bulletin, vol. 64, pp. 511–515, 2019. View at: Publisher Site  Google Scholar
 E. Farhi and A. W. Harrow, “Quantum supremacy through the quantum approximate optimization algorithm,” 2016, https://arxiv.org/abs/1602.07674. View at: Google Scholar
 M. J. Bremner, A. Montanaro, and D. J. Shepherd, “Achieving quantum supremacy with sparse and noisy commuting quantum computations,” Quantum, vol. 1, p. 8, 2017. View at: Publisher Site  Google Scholar
 S. Bravyi, D. Gosset, and R. König, “Quantum advantage with shallow circuits,” Science, vol. 362, no. 6412, pp. 308–311, 2018. View at: Publisher Site  Google Scholar
 X. Gao, S.T. Wang, and L.M. Duan, “Quantum supremacy for simulating a translationinvariant Ising spin model,” Physical Review Letters, vol. 118, no. 4, article 040502, 2017. View at: Publisher Site  Google Scholar
 J. BermejoVega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, “Architectures for quantum simulation showing a quantum speedup,” Physical Review X, vol. 8, no. 2, article 021010, 2018. View at: Publisher Site  Google Scholar
 S. Boixo, S. V. Isakov, V. N. Smelyanskiy et al., “Characterizing quantum supremacy in nearterm devices,” Nature Physics, vol. 14, no. 6, pp. 595–600, 2018. View at: Publisher Site  Google Scholar
 F. Arute, K. Arya, R. Babbush et al., “Quantum supremacy using a programmable superconducting processor,” Nature, vol. 574, no. 7779, pp. 505–510, 2019. View at: Publisher Site  Google Scholar
 R. T. Horn, S. Babichev, K.P. Marzlin, A. Lvovsky, and B. C. Sanders, “Singlequbit optical quantum fingerprinting,” Physical Review Letters, vol. 95, no. 15, article 150502, 2005. View at: Publisher Site  Google Scholar
 F. Xu, J. M. Arrazola, K. Wei et al., “Experimental quantum fingerprinting with weak coherent pulses,” Nature Communications, vol. 6, no. 1, p. 8735, 2015. View at: Publisher Site  Google Scholar
 J.Y. Guan, F. Xu, H. L. Yin et al., “Observation of quantum fingerprinting beating the classical limit,” Physical Review Letters, vol. 116, no. 24, article 240502, 2016. View at: Publisher Site  Google Scholar
 N. Kumar, I. Kerenidis, and E. Diamanti, “Experimental demonstration of quantum advantage for oneway communication complexity surpassing bestknown classical protocol,” Nature Communications, vol. 10, no. 1, p. 4152, 2019. View at: Publisher Site  Google Scholar
 J. M. Arrazola, E. Diamanti, and I. Kerenidis, “Quantum superiority for verifying NPcomplete problems with linear optics,” npj Quantum Information, vol. 4, p. 56, 2018. View at: Publisher Site  Google Scholar
 F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, “Experimental demonstration of quantum advantage for NP verification with limited information,” Nature Communications, vol. 12, no. 1, p. 850, 2021. View at: Publisher Site  Google Scholar
 I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning, MIT Press, Cambridge, Mass, 2016.
 J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, “Quantum machine learning,” Nature, vol. 549, no. 7671, pp. 195–202, 2017. View at: Publisher Site  Google Scholar
 D. Bondarenko and P. Feldmann, “Quantum autoencoders to denoise quantum data,” Physical Review Letters, vol. 124, no. 13, article 130502, 2020. View at: Publisher Site  Google Scholar
 I. Cong, S. Choi, and M. D. Lukin, “Quantum convolutional neural networks,” Nature Physics, vol. 15, no. 12, pp. 1273–1278, 2019. View at: Publisher Site  Google Scholar
 K. Beer, D. Bondarenko, T. Farrelly et al., “Training deep quantum neural networks,” Nature Communications, vol. 11, no. 1, p. 808, 2020. View at: Publisher Site  Google Scholar
 Z.B. Chen, “Quantum neural network and soft quantum computing,” 2018, https://arxiv.org/abs/1810.05025. View at: Google Scholar
 K. H. Wan, O. Dahlsten, H. Kristjánsson, R. Gardner, and M. Kim, “Quantum generalisation of feedforward neural networks,” npj Quantum Information, vol. 3, p. 36, 2017. View at: Publisher Site  Google Scholar
 N. Killoran, T. R. Bromley, J. M. Arrazola, M. Schuld, N. Quesada, and S. Lloyd, “Continuousvariable quantum neural networks,” Phys. Rev. Research, vol. 1, no. 3, article 033063, 2019. View at: Publisher Site  Google Scholar
 E. Torrontegui and J. J. GarcaRipoll, “Unitary quantum perceptron as efficient universal approximator,” Europhysics Letters, vol. 125, no. 3, article 30004, 2019. View at: Publisher Site  Google Scholar
 J. M. Arrazola, T. R. Bromley, J. Izaac, C. R. Myers, K. Brádler, and N. Killoran, “Machine learning method for state preparation and gate synthesis on photonic quantum computers,” Quantum Science and Technology, vol. 4, no. 2, article 024004, 2019. View at: Publisher Site  Google Scholar
 L. G. Valiant, “A theory of the learnable,” Communications of the ACM, vol. 27, no. 11, pp. 1134–1142, 1984. View at: Publisher Site  Google Scholar
 D. Haussler, Probably Approximately Correct Learning, University of California, Santa Cruz, Computer Research Laboratory, 1990.
 S. Arunachalam, A. Belovs, A. M. Childs, R. Kothari, A. Rosmanis, and R. De Wolf, “Quantum coupon collector,” in 15th Conference on the Theory of Quantum Computation, Communication and Cryptography, pp. 10:1–10:17, Dagstuhl, Germany, 2020. View at: Google Scholar
 R. Motwani and P. Raghavan, Randomized Algorithms, Chapman & Hall/CRC, 2009.
 J. Du, P. Zou, X. Peng et al., “Experimental quantum multimeter and onequbit fingerprinting,” Physical Review A, vol. 74, no. 4, article 042319, 2006. View at: Publisher Site  Google Scholar
 J. N. de Beaudrap, “Onequbit fingerprinting schemes,” Physical Review A, vol. 69, no. 2, article 022307, 2004. View at: Publisher Site  Google Scholar
 G. Brassard, “Quantum communication complexity,” Foundations of Physics, vol. 33, no. 11, pp. 1593–1616, 2003. View at: Publisher Site  Google Scholar
 A. M. Steane and W. van Dam, “Physicists triumph at guess my number,” Physics Today, vol. 53, no. 2, pp. 35–39, 2000. View at: Publisher Site  Google Scholar
 H. Buhrman, R. Cleve, S. Massar, and R. De Wolf, “Nonlocality and communication complexity,” Reviews of Modern Physics, vol. 82, no. 1, pp. 665–698, 2010. View at: Publisher Site  Google Scholar
 E. Kushilevitz, Communication complexity. vol. 44, Cambridge Univ. Press, 2006.
 S. Massar, “Quantum fingerprinting with a single particle,” Physical Review A, vol. 71, no. 1, article 012310, 2005. View at: Publisher Site  Google Scholar
 J. C. GarciaEscartin and P. ChamorroPosada, “Swap test and HongOuMandel effect are equivalent,” Physical Review A, vol. 87, no. 5, article 052330, 2013. View at: Publisher Site  Google Scholar
 J. M. Arrazola and N. Lütkenhaus, “Quantum fingerprinting with coherent states and a constant mean number of photons,” Physical Review A, vol. 89, no. 6, article 062305, 2014. View at: Publisher Site  Google Scholar
Copyright
Copyright © 2022 MinGang Zhou et al. Exclusive Licensee Science and Technology Review Publishing House. Distributed under a Creative Commons Attribution License (CC BY 4.0).