IBM researchers have published a paper proving that quantum computers can indeed be faster than classical computers, something that has only be theorized so far.
Quantum Algorithm Shows Speed Advantage
One of the main promises of quantum computers has been that they can solve complex problems much faster than classical computers can. Classical computers typically require exponentially more resources and power as the number of variables increase.
IBM was able to prove, for a specific difficult algebraic problem, that quantum computers need only a fixed number of steps to solve the problem, even as the number of inputs increases. This makes the quantum computation much more efficient than the classical counterpart. The more complex the problem becomes, the more efficient the quantum computed solution should be too.
The IBM researchers Sergey Bravyi, David Gosset and Robert König said in their paper:
“We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms.
Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for near-future experimental realizations, as it requires only constant-depth quantum circuits with nearest-neighbor gates on a two-dimensional grid of qubits (quantum bits).”
Quantum Computers Showing Potential
Over the past few years, we’ve seen major technology companies such as IBM, Google, Microsoft, Intel and others race against each other to show quantum supremacy, or proof that a quantum computer can solve a task faster than any supercomputer on Earth. They have yet to achieve this result, but Google believes it will soon.
Meanwhile, what IBM showed in this paper is that quantum algorithms can indeed be faster than their classical counterparts, but this doesn’t mean that the best quantum computer we have today can be faster than our fastest classical computers, since the quantum computers have not become powerful enough.
The paper showed that quantum computers have the ability to solve some problems much more efficiently, and once they become powerful enough they will be able to solve those problems faster than any other classical computer. Other problems will likely continue to be solved by classical computers, even as quantum computers mature, because not every problem may have a highly parallelized quantum computing solution.