Advertisement

technologyTechnology

Traditional Computers Can Beat Google’s Quantum Computer Thanks To Smart Algorithm Design

The claim a quantum computer had finally achieved something traditional computers cannot has been challenged using superior algorithm design.

author

Stephen Luntz

Freelance Writer

clockAug 4 2022, 11:43 UTC
Looking down a long corridor in a huge computer system
Smart algorithm design indicates claims of quantum supremacy are premature. Image credit: Gorondenkoff/Shutterstock.com

Claims of great feats by quantum processing devices have come thick and (very) fast in the last three years. The builders of these machines boast they can perform calculations swiftly that would take the world’s most powerful supercomputers impractically long periods of time. Now, however, a team of scientists has shown traditional computers still have some tricks up their sleeves and may outperform these newcomers for a while yet.

Where classical computers can only store information as 1s and 0s, quantum computers can hold superpositions of these two states. In theory, this should allow them to perform certain calculations swiftly that would take existing supercomputers the age of the universe to compute. However, building working quantum computers proved harder than expected, and scaling them up harder still.

Advertisement

The term “quantum supremacy” was invented to indicate the day when quantum computers would take the lead over traditional counterparts, at least at specific tasks. Three years ago Google claimed to have achieved just that with their Sycamore processor. However, a new paper in Physical Review Letters (preprint on ArXiv.org) challenges this.

Back in 2019, Google’s processor took just 200 seconds to sample the possible outcomes of a 20-gate quantum circuit. The machine’s creators argued even the best supercomputer in the world would take 10,000 years to do the same thing, hence quantum supremacy. The following year a Chinese team made a claim their processor could perform an operation that would take the best supercomputers half the age of the Earth to do.

From the start, IBM, who is also racing to be the first to achieve this goal, argued this was not true quantum supremacy. The term referred to a quantum computer doing something no classical computer could manage at all, IBM argued. The fact it would take a supercomputer the time since the invention of agriculture to reach the same solution was irrelevant – it would get there in the end if civilization didn’t collapse first.

Advertisement

Others regarded this as splitting hairs – the fact the quantum processor was so much faster indicated clear superiority. Now, however, even that has been challenged. 

Dr Pan Zhang of China’s Institute of Theoretical Physics and co-authors designed a more efficient algorithm for tackling the problem Sycamore solved. Rather than the cumbersome Schrödinger-Feynman algorithm Sycamore’s makers had proposed as the classical method, Pan and co-authors modeled the problem as a three-dimensional mathematical array in which layers substituted for the gates in the original. They also allowed for the same level of imprecision as Sycamore produced, rather than demanding perfection.

It took Pan’s and co.'s computer 15 hours to solve the problem – considerably longer than Sycamores' 3.3 minutes, but a refutation of the idea it was effectively beyond classical machines.

Advertisement

Moreover, the computer used to run the program was not particularly powerful. “If our algorithm could be implemented with high efficiency on a modern supercomputer with ExaFLOPS performance, we estimate that ideally, the simulation would cost a few dozens of seconds, which is faster than Google’s quantum hardware,” the authors write. 

“I think they’re right that if they had access to a big enough supercomputer, they could have simulated the … task in a matter of seconds,” the University of Texas, Austin’s Professor Scott Aaronson told Science Magazine.

Notably, Sycamore and other quantum processors are not yet full computers. The range of tasks they can perform is very limited. Their maker’s goal is to achieve quantum supremacy on a specific task chosen to suit their strengths and gradually expand capabilities from there. The question is whether the first task has been achieved.

Advertisement

“There’s an urgent need for better quantum supremacy experiments,” Aaronson said. Ideally, these might be tasks whose solutions are useful, not just demonstrations of capacity.


technologyTechnology
  • tag
  • quantum computing,

  • google,

  • computer science

ABOUT THE AUTHOR