Pan's team proves the quantum computing advantage of Nine Chapters
Quantum computers can outperform their classical counterparts when it comes to solving certain computational problems; but for most tasks, ordinary, off-the-shelf laptops are still much better.
Now, an experimental team at the University of Science and Technology of China, including Lu Chaoyang and Pan Jianwei, has solved two graph-theoretic problems using a photonic network-based quantum computer (Chapter 9) - and their results extend the list of tasks where today's noise-containing medium-scale quantum computers (NISQs) have " advantage" over classical computers.
The results were published May 9 in Physical Review Letters, the top journal of physics, under the title "Solving Graph Problems Using Gaussian Boson Sampling.
Gaussian Boson Sampling (GBS), a variant of Aaronson-Arkipov Boson Sampling, has attracted considerable attention for its potential applications to graph-related problems, quantum chemistry, and machine learning.
This is because of the potential mathematical connection between GBS and graph theory. GBS is not only a feasible protocol for proving quantum computational advantage (QCE), but is also mathematically relevant to certain graph-related and quantum chemistry problems. In particular, it has been proposed that samples generated by Gaussian Boson sampling can be used to enhance the performance of classical stochastic algorithms in searching for graphs.
This time, the experimental team investigated an open question: does the enhancement of classical random algorithms by GBS persist on computationally meaningful systems (medium-scale quantum computers with noise)? How does it scale as the system size increases?
The samples in the experiment were generated by a fully connected photonic processor with 144 modes (modes).
As these photons are injected into the network one by one, the GBS solution is a prediction or "sampling" of the probability distribution of the photons recorded on the network's 144 output detectors.
This sampling method is mathematically linked to the graph problem, which is a pairwise relationship between objects defined by a matrix. In their experiments, the researchers used their photon processor to implement a search algorithm defined by two such problems.
GBS enhancement for Max-Haf and dense k-subgraph (subgraph) problem solving
The scalability of GBS is measured by the score advantage, speed advantage as a function of photon-click number.
The step histogram of the target value achieved by the RS algorithm for GBS enhancement is a function of various noise levels. For each subplot, a number of trials are repeated and the Y-axis corresponds to the number of occurrences of steps that exceed the target value. The target was set as the average value achieved by the classical RS algorithm at 10,000 steps. (a-b) Theoretical simulation of the effect of photon loss noise on the GBS enhancement of the Max-Haf problem
By treating each output port of the processor as a graph vertex and each detected photon as a subgraph vertex, they can determine which subgraph maps to the solution. Ultimately, their processor arrived at a solution after obtaining 221,891 samples, each corresponding to a specific distribution of up to 80 detected photons-each of which would have taken 700 seconds to run using the exact algorithm on the world's fastest supercomputer.
In this work, the experimental team has demonstrated the enhanced effect of GBS on random algorithms: solving two graph problems of different nature with 144-mode NISQ devices "in nine chapters" in the quantum computing advantage regime.
"Previous claims of quantum dominance have been challenged by the argument that quantum computers do not compete with the best possible classical algorithms for this task." The editors of Physics Magazine commented.
"However, it remains an open question whether GBS yields an advantage over improved classical and quantum-inspired algorithms."
In the paper, the experimental team also stated, "We look forward to a more comprehensive algorithmic analysis and discussion of the various scenarios. We also hope that our work will stimulate experimental work on larger scale, higher scalability and fully programmable GBS, explore real-world applications where computational problems can be mapped onto GBS, and develop more efficient classical and quantum-inspired algorithms."
Reference links:
[1] https://physics.aps.org/articles/v16/s64
[2] https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.130.190601
