The research team composed of Pan Jianwei, Lu Chaoyang, Liu Naile and others of the University of Science and Technology of China completed the solution of the two types of graph theory problems of “dense subgraph” and “Max-HAF” based on the “Chapter 9” optical quantum computing prototype, and studied the acceleration brought by the “Chapter 9” processing of these two types of graph theory problems to the search algorithm through experiments and theories, and the dependence of this acceleration on the problem scale and experimental noise, and the experimental rate was about 180 million times faster than the world’s fastest supercomputer. This research result is the first experimental research on the application value problem on the optical quantum computing prototype with the superiority of quantum computing. Related papers were recently published in Physical Review Letters in the form of “Editor’s Recommendation”.

?

**“Chapter 9” Schematic diagram of the correspondence principle between quantum computing prototype and graph theory problem. Photo courtesy of China University of Science and Technology**

The physical implementation of quantum computers is one of the major challenges at the forefront of current science and technology. The international academic community has formulated a three-step roadmap for the experimental development of quantum computing, the first of which is to achieve “quantum computing superiority”. “Quantum computing superiority” refers to the efficient solution of specific high-complexity mathematical problems that supercomputers cannot solve in a reasonable time by manipulating nearly a hundred physical bits with high precision. The significance of this step is to prove quantum computing acceleration for the first time experimentally and conclusively, and to challenge the “extended Church-Turing thesis”.

At present, only three teams, Google, China University of Science and Technology and Xanadu Canada, have achieved the goal of “quantum computing superiority”. Only on the basis of realizing the “superiority of quantum computing” can experimental research on quantum computing applications be expected to bring quantum acceleration. Therefore, an important scientific research goal in the next stage of the international academic community is to explore the use of quantum computing prototypes to demonstrate the solution of problems with practical value.

Recently, while continuing to develop higher quality and more scalable optical quantum computing prototypes, Pan Jianwei’s team has carried out research and exploration of applying the Gaussian boson sampling task performed in Chapter 9 to graph theory problems. By mapping each output port of the Gaussian boson sampling device to the vertices of the graph and each detected photon to the vertex of the subgraph, researchers can use the experimental sample acceleration search algorithm to find subgraphs with greater density or Hafnian, thereby helping to solve these two types of graph theory problems. These two types of graph theory problems have important applications in the fields of data mining, bioinformatics, network analysis, and some chemical model studies.

In this work, researchers for the first time used Gaussian boson sampling performed in Chapter 9 to accelerate the solution of graph theory problems by random search algorithms and simulated annealing algorithms. In the experiment, the researchers used more than 200,000 80-photon match counting samples, which is about 180 million times faster than the world’s fastest supercomputer and accurately simulated using the current best classical algorithms. (Source: Wang Min, China Science News)

Related paper information:https://doi.org/10.1103/PhysRevLett.130.190601