For quantum computers to be considered viable, they need to successfully and verifiably perform tasks that are hard to reproduce on any classical computer – a situation known as “quantum advantage”. As both quantum computers and classical methods improve, however, it becomes difficult to draw the line beyond which quantum machines have the upper hand.
A recent development spearheaded by researchers at the University of Bristol, UK, has taken the competition up a notch by showing that classical machines can solve one such “hard” task drastically faster than previously thought. Although the quantum computer remains in the lead, the Bristol team’s new algorithm narrows the gap between classical and quantum by about nine orders of magnitude.
Photonic advantage
In late 2020 experimentalists at the University of Science and Technology of China (USTC) reported that they had demonstrated quantum advantage using a technique known as Gaussian boson sampling (GBS). Their experiment was based on the idea that the task of sampling probability distributions generated by quantum states in certain settings is known to be intractable for classical computers.
In GBS, the probability distributions come from a set of photons that pass through optical circuits. As the photons travel through the circuit, they interfere with one another before being measured. As the size of the optical circuit and the number of photons increases, calculating the statistics of the output measurements gets exponentially harder for classical computers. In just a few minutes, the quantum set-up built by the USTC team managed to calculate what a classical machine was expected to require several million years to compute.
Classical speedup
Unfazed by this gigantic gap, a team at Bristol’s Quantum Engineering Technology Labs (QET Labs), along with colleagues at Imperial College London and Hewlett Packard Enterprise, took on the challenge and came up with a way to reduce the classical runtime for solving the same problem. They showed, in a recent paper in Science Advances, that it is possible to simulate USTC’s experiment in mere months – a speed-up factor of around a billion when compared to previous estimates.
This new result overhauls several algorithms used in GBS simulations and outputs the results of an experiment, with the possibility to add noise and errors at will. This extra ability sets it apart from many other efficiency-focused simulation algorithms, which tend to explicitly rely on the way errors affect the output of the physical experiment to achieve faster simulation times. Adding noise models that represent experimental losses to classical simulations of GBS has been shown to reduce their complexity and hence shorten their runtime.
Implications and a look to the future
According to Jacob F Bulmer, a PhD student at Bristol and a lead author of the study, the goal of these experiments and simulations is not to solve a particular real-world problem. Rather, it is to better understand and demonstrate the criteria for quantum advantage. While the new result is still not faster than the quantum experiment, it pokes holes in what was previously conceived to be “difficult” for classical computers and raises the bar for future experiments.
Quantum advantage takes a giant leap in optical and superconducting systems
“I think the main implication is that we provided a clear benchmark which GBS experiments should be compared against,” Bulmer explains. “I hope that from now on, any new progress in GBS will include a comparison to our methods, which stand as the fastest classical algorithms for exact simulation of GBS.”
The race for quantum advantage is not over. On the classical side, the Bristol researchers have yet to fully exploit the noise and imperfections of experimental set-ups in ways that would speed up their simulations even further. At the same time, quantum technologies are continuing to race ahead. In October 2021, the USTC group reported new results in Physical Review Letters that surpass their 2020 findings by a large margin. Although the USTC team did not provide a benchmark against the new classical algorithm, with advances coming from both sides, it remains to be seen what quantum advantage really means for GBS.
