Google was 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 extent to which a quantum computer can perform a task that would impossible for ordinary computers. Google concedes its 2019 record won’t stand, but says quantum computers will eventually prevail.
Sycamore achieved quantum supremacy in a task of verifying that a sample of numbers emitted by a quantum circuit has a truly random distribution, which he was able to complete in 3 minutes and 20 seconds. The Google team said that even the most powerful supercomputer in the world 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, disputing Google’s claim that a quantum computer is the only practical way to do this. The researchers found that they could skip some of the computations without affecting the final output, significantly reducing computational requirements compared to previous best algorithms.
The researchers ran their algorithm on a cluster of 512 GPUs (graphics processing units), completing the task in around 15 hours. Although it is much longer than Sycamore, they show that a classic computer approach is still practical.
They also calculated that if they were able to run their algorithm efficiently on an exascale supercomputer – which is not a given, as there is performance overhead in translating code for these machines – he could solve the problem in “tens of seconds”, beating Sycamore’s time. The first public exascale machine only went online this year, although some are believed to be operating privately.
Ashley Montanaro at the University of Bristol, UK, argues that while the improvements to the classical algorithm are impressive, comparing 2019’s quantum hardware with state-of-the-art classical hardware like an exascale supercomputer ignores the likely gains in quantum computing research over the past three years.
“I think it was always clear when Google did its experiment that there was going to be a development of better classical algorithms that would try to somehow compete with the quantum computer because Google kind of stuck his head above the parapet,” he says.
Zhang says 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 some tasks. “Eventually, quantum computers will have overwhelming advantages over classical computing in solving specific problems,” he says.
Zhang’s team’s study isn’t the first challenge to Google’s claim, though it may be the strongest. After Google’s announcement in 2019, IBM claimed that Summit could have completed the task in two and a half days, but more importantly, it did not conduct the experiment, even on a smaller scale like Zhang’s team l ‘did.
In a statement, Sergio Boixo, Principal Scientist at Google Quantum AI, said: “In our 2019 paper, we said classical algorithms would improve…but the key point is that quantum technology is improving exponentially faster. . We therefore do not believe that this classical approach can keep pace with quantum circuits in 2022 and beyond, despite significant improvements in recent years. »
Journal reference: Physical examination lettersin press
Learn more about these topics: