In 2019, the Sycamore computer was used by Google to demonstrate how a quantum computer could complete a task that would be impossible for ordinary computers.
At the time 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.
Chinese Academy of Sciences boffin Pan Zhang and his colleagues have solved the challenge without needing a quantum computer. They just used better coding.
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 is still practical and did not require the use of any cats.
They calculated that if they were able to run their algorithm efficiently on an exascale supercomputer it could solve the problem in “a few dozens of seconds”, beating Sycamore’s time.
Zhang says that his team’s algorithm is “massively more efficient than existing methods” but 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.
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.”