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 鈥渜uantum 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鈥檛 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鈥檚 most powerful supercomputer at the time, IBM鈥檚 Summit, would take 10,000 years to achieve the same result.
Now, 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鈥檚 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.
Advertisement
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鈥檛 a given, as there are performance overheads in translating code for these machines 鈥�听it could solve the problem in 鈥渁 few dozens of seconds鈥�, beating Sycamore鈥檚 time. The first public exascale machine only went online this year, though some are thought to be operating in private.
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.
鈥淚 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鈥檚 algorithm is 鈥渕assively more efficient than existing methods鈥� but also concedes that classical computers are unlikely to keep pace with quantum machines for certain tasks. 鈥淓ventually quantum computers will display overwhelming advantages over classical computing in solving specific problems,鈥� he says.
The study from Zhang鈥檚 team isn鈥檛 the first challenge against Google鈥檚 claim, although it is perhaps the strongest. After Google鈥檚 announcement in 2019, IBM claimed that Summit could have completed the task in two and a half days, but crucially it didn鈥檛 run the experiment, even on a smaller scale as Zhang鈥檚 team did.
In a statement, , principal scientist at Google Quantum AI, said: 鈥淚n our 2019 paper we said that classical algorithms would improve鈥� but the key point is that quantum technology improves exponentially faster. So we don鈥檛 think this classical approach can keep up with quantum circuits in 2022 and beyond, despite significant improvements in the last few years.鈥�
Journal reference: Physical Review Letters, in press
