Recently, Chinese scientists have realized the quantum superiority of machine learning and communication complexity at the same time. Yin Hualei and Chen Zengbing, from the school of physics of Nanjing University, the State Key Laboratory of solid microstructure physics and the collaborative innovation center of Artificial Microstructure science and technology, proved for the first time that quantum technology can provide learning algorithms with quantum advantages for machine learning, designed a quantum version of blind box games, and verified the potential application value of quantum coupon theory.
Relevant achievements were published in research, the first cooperative Journal of science magazine in the United States.
Picture from research
Machine learning can extract useful information and knowledge from data, which has a significant impact on basic theory, advanced technology and social productivity. Precise regulation of quantum state technology has shown quantum advantages over classical technology in communication security, computing speed and measurement accuracy. Using quantum technology to improve machine learning or realize quantum machine learning is a research hotspot in recent years, and a lot of research work has carried out innovative exploration.
However, most of the previous attempts were heuristic and did not theoretically prove that quantum machine learning showed better performance or shorter training time than classical machine learning. The "possibly approximately correct" (PAC) learning theory quantifies the minimum number of samples required for a learning algorithm to effectively learn a task. Therefore, using this theory to study quantum machine learning can lay a theoretical foundation for exploring the quantum advantages in machine learning.
In 2020, the research team of the University of Amsterdam in the Netherlands and the research team of IBM in the United States jointly proposed the problem of quantum coupon collection, and strictly proved the existence of a learning algorithm with quantum advantages by Using PAC learning theory for the first time. Specifically, the set composed of all the objective functions you want to learn is called "concept class", and given a learning algorithm, the set of all possible mappings it considers is called "hypothesis space". If in PAC learning, it is assumed that the space and concept class are exactly the same, that is, it is properly PAC learnable; otherwise, it is not properly PAC learnable.
Generally speaking, the learning sample complexity of classical just and improper PAC is different. However, for the coupon collection problem, the sample complexity required for just and not just PAC learning can be the same under the quantum algorithm. Therefore, quantum coupon collection algorithm is the first algorithm to show that there is a fundamental difference between classical and quantum machine learning based on PAC learning theory.
Coupon collection problem, picture from vcubingx
The experimental demonstration of the original quantum coupon algorithm requires highly complex single photon quantum fingerprint States and highly nonlinear measurement devices far beyond the current experimental technology to realize ultra-high-dimensional positive semidefinite operator measurement (POVM).
This time, the research group of Yin Hualei and Chen Zengbing proposed the coherent state quantum coupon protocol, which skillfully converts the single photon quantum fingerprint state into the equivalent coherent state tensor product form, and converts the amplitude information of the single photon in the dimension into the phase information of the coherent state in the time box. Therefore, the quantum coupon collection task was successfully demonstrated by using the linear optical quantum technology experiment, and the PAC learning theory was used, The first experiment proves that quantum technology can provide a learning algorithm with quantum advantages for machine learning.
The team theoretically proved the equivalence between coherent state quantum coupons and original quantum coupons in terms of quantum advantages of machine learning, so as to realize the task of demonstrating quantum coupon collection by using the widely used optical quantum communication technology (lasers, linear optical components and single photon detectors).
In the experiment, we need to minimize the noise of quantum state interferometry, including: using Sagnac interferometer to achieve stable time and phase alignment; High speed and accurate phase preparation is realized by using high-precision phase modulation technology; Polarization and intensity alignment are realized by using a highly symmetrical polarization maintaining fractional filter; A superconducting nanowire single photon detector with high efficiency and ultra-low dark count is used to achieve near perfect measurement. Based on these experimental techniques, the team finally clearly demonstrated the quantum advantages of machine learning.
Experimental results of quantum coupons. The picture is from the school of physics of Nanjing University
In order to further demonstrate the potential application value of quantum coupon theory, the team designed its quantum version for the blind box game loved by young people and successfully conducted an experimental demonstration, which fully demonstrated the potential application value of quantum coupon theory and the advantages of quantum technology in communication complexity.
In the blind box game, businesses put balls with different patterns into different boxes to form a blind box, select almost all boxes as a blind box set, and make multiple sets of blind box sets with the same configuration. Customers can only select one blind box from each set of blind box sets to confirm the patterns of all small balls in the whole set of blind box sets. The customer needs to pay a certain amount of fee for each set of blind box suit consumed. If the customer guesses correctly, the merchant will reward the customer with a bonus. The amount of bonus is the expected value of the cost of blind box suit consumed under the classical strategy.
Using quantum resources to encode the blind box, customers can reduce their costs by designing quantum coding and quantum measurement, so as to get more returns in the game. The experimental results of quantum coupon show that quantum protocol can effectively reduce the number of samples required to learn coupons with up to 14000 elements. The experimental results of quantum blind box game show that for different types of blind box suits, customers can always reduce the cost by selecting the appropriate light intensity (luminous intensity) to obtain more returns, which shows that the resources consumed by quantum coupon protocol in this game are less than the optimal classical strategy.
The picture comes from the school of physics of Nanjing University
The above experimental results strongly prove that even without the use of multi particle entangled states and quantum gate manipulation, the quantum technology of linear optics can achieve the quantum superiority over the classical technology in terms of machine learning and communication complexity.
The co first authors of the paper are postgraduates Zhou Mingang, Cao Xiaoyu and Lu yushuo of the school of physics of Nanjing University, and the corresponding authors are Associate Professor Yin Hualei and Professor Chen Zengbing of Nanjing University. The above work has been supported by the National Natural Science Foundation of China, the natural science foundation of Jiangsu Province, the basic scientific research business fee of central universities, the key R & D plan of Nanjing Jiangbei new area, etc.