New Algorithm Closes Quantum Supremacy Window
upstart writes:
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?
Most researchers suspected the answer was no, but they couldn't prove it for all cases. Now, in a paper posted to the preprint server arxiv.org, a team of computer scientists has taken a major step toward a comprehensive proof that error correction is necessary for a lasting quantum advantage in random circuit sampling - the bespoke problem that Google used to show quantum supremacy. They did so by developing a classical algorithm that can simulate random circuit sampling experiments when errors are present.
"It's a beautiful theoretical result," Aaronson said, while stressing that the new algorithm is not practically useful for simulating real experiments like Google's.
Read more of this story at SoylentNews.