Race Not Over Between Classic and Quantum Computers

Physics 15, 19

A new classical algorithm reduces – by a factor of one billion – a recent assertion of a so-called quantum advantage.

Shuo / stock.adobe.com

Researchers have significantly diminished the advantage of a newly proven quantum computing algorithm over its classical equivalent.

In the race to achieve the coveted “advantage” of a quantum computer, these evolving quantum algorithms are pitted against each other and against those working on classical algorithms. With every possible claim of such an advantage – the successful calculation on a quantum computer of something that is impossible on a classical one – scientists have designed more efficient classical algorithms against which the quantum algorithms must then be compared. Now, right along the way, Jacob Bulmer of the University of Bristol, UK, Bryn Bell of Imperial College London, and colleagues dropped a peg a recent assertion of a quantum advantage using a method called Gaussian boson sampling. The team behind that advantage claim claimed that classical computing of Gaussian boson sampling will take 600 million years on the world’s fastest supercomputer. But Bulmer, Bell and colleagues show that their classic 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 by Scott Aaronson of the University of Texas at Austin and Alex Arkhipov, who was at the Massachusetts Institute of Technology at the time. The idea, known as boson sampling, proposed sending a beam of single photons through a network of radio dividers to create a complex network of correlations between the paths of the photons.

To imagine the resulting photo-path network, Aaronson and Arkhipov compared their system to a quantum version of a Galton board, a vertical board with pegs attached 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 due to the ability of photons to involve. Aaronson and Arkhipov argued that this distribution probably could not be calculated effectively by a classical computer. The simplicity of the problem made it a good candidate for a short-term demonstration of a quantum advantage.

In 2020, a group of researchers led by Jian-Wei Pan at China University of Science and Technology (USTC) did just that using a Gaussian boson specimen. This method uses a boson sampler to perform the calculation using compressed light states. 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 photons across a network of radio dividers 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 can reduce that classic countdown time.

Bulmer says the team knew that one of the main questions in the classical calculus was to determine the “Hafnian loop,” 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 basically difficult to calculate classically, which gives Gaussian boson samplers their advantage over classical computers. Bulmer, Bell, and their colleagues found that they were able to improve computation time by using patterns in the structure of the matrix that mathematically describe how photons travel through the maze of beam dividers. 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” is not yet capable of simulating classically, at any acceptable time, the most recent quantum. [advantage] experiments ”(see Viewpoint: Quantum Jump for Quantum Primacy).

While the USTC team’s Gaussian boson testing algorithm is still about 4 magnitudes faster than that of Bulmer, Bell, and colleagues, some researchers see the factor-of-billion drop in classical simulation time as a sign that determining quantum advantage is a confusing problem. “The reality is that this line isn’t actually well defined,” says Alex Moylett, a scientist at Riverlane, UK, quantum engineering.

In the distant future, most researchers expect quantum computers to surpass classics by such a large margin that no one could doubt that they are better. Aaronson has the same hope, but in the meantime, he thinks that classic computers “can, at least for a while, fight back.” He says, “Such developments send a message that experimenters need to improve their game if they want to [a] quantum [advantage]… to be preserved and improved in the future. “

“Katie McCormick.”

Katie McCormick is a Seattle, WA-based science writer.

Thematic Areas

Quantum InformationQuantum Physics

Recent Articles

The Shrink Transistor

The Shrink Transistor

Researchers have identified the best materials of silicon and silicon dioxide for the next generation of transistors, which are expected to be only nanometers long. Read more “

Parametric Oscillator for Phonics
Looking Inside the Superfluid Helium-3 Universe

Additional Articles

Leave a Reply

Your email address will not be published.