It is now clear that quantum computers can do certain tasks much faster than traditional computers. This could greatly increase their utility.
Quantum computers employ quantum bits (or qubits) to measure and extract data. Qubits are able to store multiple values simultaneously, unlike classical bits that can only store one or zero. The theory is that they have a significant speed advantage over algorithms and classical computers. It has been difficult to prove that these machines can beat regular machines with their quantum advantage.
For instance, quantum advantage was shown to be possible using classical algorithms in 2018.
Hsin-Yuan and his colleagues at the California Institute of Technology have now shown mathematically that quantum computers can not only have an edge in certain tasks but can also be exponentially more efficient.
Huang says, "We now have a mathematical framework to prove this exponential separation." He says that people have been split between believing it is possible to achieve exponential speed-up or becoming extremely pessimistic. It's like being on a rollercoaster.
Huang and his team used their mathematical frameworks to demonstrate the speed advantage in three broad categories of quantum problems. These included measuring and forecasting properties of a system of quantum particles, extracting information form noisy real-world signals, and studying how these systems change over time. They showed that each problem would require the classic version of the experiment to be repeated an exponential amount of times.
These problems, unlike previous examples of quantum advantage such as boson sampling could have useful applications like building advanced sensors that detect gravitational wave and measuring complex biological systems.
Two experiments were then conducted by the researchers to demonstrate this advantage on Google’s Sycamore quantum computing system. This was made more difficult by the presence statistical noise which wasn't covered.
The uncertainty principle is a method that allows us to measure quantum properties in a system that is not accessible to classical computers. It states, for instance, that it is impossible to be certain of both the position and momentum of particles simultaneously. The second experiment was to determine whether a quantum process behaved the same when it was run in reverse or forward time. This could be useful in nuclear and high-energy physics.
Ashley Montanaro, University of Bristol, UK says that the authors were able to demonstrate that there are experiments in which there is a lower limit on how many samples are required using a classical computer. "They are able to exceed that bound even with a noisy quantum computing system, which is an impressive feat considering the very early stages of quantum hardware."
Although the framework Huang and his team created is broad, it was only applicable to certain classes of problems. Huang says that future work will have to prove quantum advantage for many other quantum problems.
