IT is 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 beat regular machines, hasn’t been easy. In 2018, for instance, an example of quantum advantage – for recommendation systems like those on Netflix or Amazon – was 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.
These problems could have useful applications, like modelling complex biological systems
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 over 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 sensors to detect gravitational waves or measuring complex biological systems.
The researchers then performed two experiments to demonstrate 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.”
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 prove quantum advantage for many more quantum problems,
says Huang.
