Afcacia

Google has been challenged by an algorithm that could solve a problem faster than its Sycamore quantum computer, which it used in 2019 to claim the first example of “quantum supremacy” – the point at which a quantum computer can complete a task that would be impossible for ordinary computers. Google concedes that its 2019 record won’t stand, but says that quantum computers will win out in the end.

Sycamore achieved quantum supremacy in a task that involves verifying that a sample of numbers output by a quantum circuit have a truly random distribution, which it was able to complete in 3 minutes and 20 seconds. The Google team said that even the world’s most powerful supercomputer at the time, IBM’s Summit, would take 10,000 years to achieve the same result.

Now, Pan Zhang at the Chinese Academy of Sciences in Beijing and his colleagues have created an improved algorithm for a non-quantum computer that can solve the random sampling problem much faster, challenging Google’s claim that a quantum computer is the only practical way to do it. The researchers found that they could skip some of the calculations without affecting the final output, which dramatically reduces the computational requirements compared with the previous best algorithms.

The researchers ran their algorithm on a cluster of 512 GPUs (graphics processing units), completing the task in around 15 hours. While this is significantly longer than Sycamore, they say it shows that a classical computer approach remains practical.

They also calculated that if they were able to run their algorithm efficiently on an exascale supercomputer – which isn’t a given, as there are performance overheads in translating code for these machines – it could solve the problem in “a few dozens of seconds”, beating Sycamore’s time. The first public exascale machine only went online this year, though some are thought to be operating in private.

Ashley Montanaro at the University of Bristol, UK, says that although the improvements to the classical algorithm are impressive, comparing quantum hardware from 2019 with cutting-edge classical hardware like an exascale supercomputer ignores the probable gains in quantum computing research over the past three years.

“I think it was always sort of clear at the time that Google did their experiment that there was going to be some development of better classical algorithms that would somehow try to compete with the quantum computer because Google sort of stuck their heads above the parapet,” he says.

Zhang says that his team’s algorithm is “massively more efficient than existing methods” but also concedes that classical computers are unlikely to keep pace with quantum machines for certain tasks. “Eventually quantum computers will display overwhelming advantages over classical computing in solving specific problems,” he says.

The study from Zhang’s team isn’t the first challenge against Google’s claim, although it is perhaps the strongest. After Google’s announcement in 2019, IBM claimed that Summit could have completed the task in two and a half days, but crucially it didn’t run the experiment, even on a smaller scale as Zhang’s team did.

In a statement, Sergio Boixo, principal scientist at Google Quantum AI, said: “In our 2019 paper we said that classical algorithms would improve… but the key point is that quantum technology improves exponentially faster. So we don’t think this classical approach can keep up with quantum circuits in 2022 and beyond, despite significant improvements in the last few years.”