Race Not Over Between Classical and Quantum Computers
In the race to achieve the coveted “advantage” of a quantum computer, those developing quantum algorithms are pitted against each other and against those working on classical algorithms. With each potential claim of such an advantage—the successful calculation on a quantum computer of something that is infeasible on a classical one—scientists have designed more efficient classical algorithms against which the quantum algorithms must then be compared. Now, by exactly that route, Jacob Bulmer of the University of Bristol, UK, Bryn Bell of Imperial College London, and colleagues have knocked down a peg a recent claim of quantum advantage using a method called Gaussian boson sampling. The team behind that advantage claim had asserted that a classical computation of Gaussian boson sampling would take 600 million years on the world’s fastest supercomputer. But Bulmer, Bell, and colleagues show that their classical algorithm can do it in just 73 days. This result, along with other recent improvements to classical algorithms, helps build the case that the quantum-advantage race is far from over.
Gaussian boson sampling is an adaptation of a 2011 idea from Scott Aaronson of the University of Texas at Austin and Alex Arkhipov, who, at the time, was at the Massachusetts Institute of Technology. The idea, known as boson sampling, proposed sending a beam of single photons through a network of beam splitters to create a complex web of correlations between the paths of the photons.
To imagine the resulting photon-path web, Aaronson and Arkhipov compared their system to a quantum version of a Galton board, a vertical board with pegs fastened to its surface in a two-dimensional pattern. Drop a ball from the top of the board, and it will bounce off the pegs, tracing a random path, until it reaches the ground. If repeated many times, the horizontal distribution of the balls approaches a Gaussian shape. In the case of photons, this distribution should be much more complicated because of the ability of photons to entangle. Aaronson and Arkhipov argued that this distribution likely couldn’t be calculated efficiently with a classical computer. The simplicity of the problem made it a good candidate for a near-term demonstration of a quantum advantage.
In 2020, a group of researchers led by Jian-Wei Pan at the University of Science and Technology of China (USTC) did just that using Gaussian boson sampling. This method uses a boson sampler to perform the calculation using squeezed states of light. Photodetectors stationed at the endpoints of all possible paths counted the number of photons that took each path. The team used the sampler to calculate—in 200 seconds—the distribution of the photons through a network of beam splitters with 100 possible paths, something that calculations at the time indicated would take 600 million years on the world’s fastest supercomputer, Fugaku. Bulmer, Bell, and their colleagues decide to see if they could reduce that classical calculation time.
Bulmer says that the team knew that one of the main bottlenecks in the classical calculation was determining the “loop Hafnian,” a matrix function that is at the heart of simulating Gaussian-boson-sampling experiments. This function gives the probability of measuring a particular distribution of photons at the end of the experiment. The function is inherently difficult to calculate classically, which gives Gaussian boson samplers their advantage over classical computers. Bulmer, Bell, and their colleagues found that they could improve the calculation time by taking advantage of patterns in the structure of the matrix that mathematically describe how photons travel through the maze of beam splitters. This change, along with some other improvements and simplifications, allowed the team to reduce the estimated simulation time of the USTC experiment to just 73 days.
“I think it’s great that they’ve managed to improve the [classical] runtime,” Aaronson says. But he adds that the new algorithm developed by Bulmer, Bell, and colleagues “still isn’t able to simulate classically, in any reasonable amount of time, the most recent quantum [advantage] experiments” (see Viewpoint: Quantum Leap for Quantum Primacy).
While the USTC team’s Gaussian-boson-sampling algorithm is still about 4 orders of magnitude faster than that of Bulmer, Bell, and colleagues, some researchers see the factor-of-a-billion drop in classical simulation time as a sign that determining a quantum advantage is a murky problem. “The reality is that this line is not actually well defined,” says Alex Moylett, a scientist at Riverlane, UK, a quantum engineering company.
In the distant future, most researchers expect that quantum computers will outperform classical ones by such a large margin that nobody could possibly doubt that they are better. Aaronson has the same hope, but in the meantime, he thinks that classical computers “can, at least for a while, fight back.” He says, “developments like these send a message that the experimenters need to up their game if they want [a] quantum [advantage]…to be maintained and improved into the future.”
–Katie McCormick
Katie McCormick is a freelance science writer based in Sacramento, California.