Quantum computers proved to have ‘quantum advantage’ over standard computers on some tasks

Not only do quantum computers have the edge over classical computers on some tasks, but they are also exponentially faster, according to a new mathematical proof

By Alex Wilkins

It’s official – there is now proof that quantum computers can perform some tasks exponentially faster than classical computers, and it could massively boost their usefulness.

Quantum computers use quantum bits, or qubits, to measure and extract information. Unlike the bits of classical computers, which can store a 1 or 0, qubits can store multiple values at the same time. This theoretically gives them a huge speed advantage over classical computers and algorithms. However, demonstrating that the machines have this quantum advantage, and can actually beat regular machines, hasn’t been easy.

In 2018, for instance, an example of quantum advantage – for recommendation systems such as those you might find on Netflix or Amazon – was overturned and shown to be achievable using a classical algorithm.

Now, however, Hsin-Yuan Huang at the California Institute of Technology and his colleagues have proved mathematically that not only can quantum computers have the edge on some tasks, they can be exponentially faster too.

“We now have the right mathematical framework for proving this exponential separation,” says Huang. People have flipped between saying it is possible to get exponential speed-up and becoming very pessimistic about it, he says. “It’s like a rollercoaster ride.”

Speed advantage

Huang and his team used their mathematical framework to prove the speed advantage on three broad classes of quantum problems, which involved measuring and predicting properties of a quantum system, extracting information from noisy real-world signals and learning how quantum systems change through time. For each problem, they showed that the classical version of the experiment would need to be run an exponential number of times more.

Unlike previous examples of quantum advantage like boson sampling, these problems could have useful applications, such as building advanced sensors to detect gravitational waves or measuring complex biological systems.

The researchers then performed two experiments that demonstrated this advantage on Google’s Sycamore quantum computer, made challenging by the presence of statistical noise, which wasn’t covered in their proofs.

The first experiment measured quantum properties of a system that is inaccessible to classical computers because of the uncertainty principle, which says, for example, that we can’t be certain about both the position and the momentum of particles at the same time. The second experiment involved finding whether a quantum process was the same if it was run forwards or backwards in time, which could be important in high-energy and nuclear physics.

“The authors are able to show that there are some experiments where there’s a lower bound on how many samples you’re going to need using a classical computer,” says Ashley Montanaro at the University of Bristol, UK. “They’re able to outperform that bound even using a noisy quantum computer, which, for me, is a very impressive achievement given the early stage of today’s quantum hardware.”

While the framework that Huang and his team came up with is general, they only used it for specific classes of problems. Future work will need to explicitly prove quantum advantage for many more quantum problems, says Huang.

Journal reference: Science, DOI: 10.1126/science.abn7293