Quantum Supremacy Window Closed by a New Algorithm

What are the specific situations where quantum computers outperform their classical counterparts in comparison to them? This is a difficult question to answer in part because quantum computers today are finicky and plagued by errors that can accumulate and spoil their calculations.

They’ve done it by one measure. Google announced in 2019 that they had used a 53-qubit computer to achieve quantum supremacy. This symbolic milestone marks the moment when a quantum computer can do something beyond what is possible with a classical algorithm. Similar demonstrations were soon performed by physicists from the University of Science and Technology of China.

Computer scientists are interested in finding out if classical algorithms can keep up with quantum computers that grow larger and more powerful. “The hope is for eventually the quantum side just completely pulls apart until there’s nobody anymore,” stated Scott Aaronson a computer scientist from the University of Texas in Austin.

This is partly why the general question is difficult to answer. Future quantum machines will be able to correct their errors using a technique called quantum error correction. However, that capability is still far away. Is it possible for a quantum runaway advantage to be achieved even with uncorrected errors?

While most researchers believed the answer was yes, they could not prove it in all cases. A team of computer scientists has now posted a paper to arxiv.org. This paper is a significant step toward proving that error correction is required for a long-lasting quantum advantage in random sampling. This is the unique problem that Google used in order to prove its quantum supremacy. The team developed a classical algorithm to simulate random circuit sampling experiments in the event of errors.Aaronson stated that “it’s a beautiful theoretic result,” but stressed that the algorithm was not practical for simulating real experiments such as Google’s.