New Algorithm Closes Quantum Supremacy Window

Scaling Solutions, Quantum Supremacy?

New Algorithm Closes Quantum Supremacy Window

Random circuit sampling, a popular technique for showing the power of quantum computers, doesn’t scale up if errors go unchecked.

By Ben Brubaker Staff Writer  in QuantumMagazine

Introduction

In what specific cases do quantum computers surpass their classical counterparts? That’s a hard question to answer, in part because today’s quantum computers are finicky things, plagued with errors that can pile up and spoil their calculations.

By one measure, of course, they’ve already done it. In 2019, physicists at Google announced that they used a 53-qubit machine to achieve quantum supremacy, a symbolic milestone marking the point at which a quantum computer does something beyond the reach of any practical classical algorithm. Similar demonstrations by physicists at the University of Science and Technology of China soon followed.

But rather than focus on an experimental result for one particular machine, computer scientists want to know whether classical algorithms will be able to keep up as quantum computers get bigger and bigger. “The hope is that eventually the quantum side just completely pulls away until there’s no competition anymore,” said Scott Aaronson, a computer scientist at the University of Texas, Austin.

That general question is still hard to answer, again in part because of those pesky errors. (Future quantum machines will compensate for their imperfections using a technique called quantum error correction, but that capability is still a ways off.) Is it possible to get the hoped-for runaway quantum advantage even with uncorrected errors?  ....   '