IBM Proves Quantum Computers Can Be Faster Than Classical Ones

IBM Q quantum computer lab. Credit: IBMIBM Q quantum computer lab. Credit: IBMIBM 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.

    Your comment
  • Matt C
    Hey, I know two of those three!
  • stdragon
    With quantum computing, it's like "Schrödinger's bit"- where the results are already known right up until you directly observe them. Until then, it's both a 1 and a 0 at the same time

  • alextheblue
    Most of these comparisons are against general purpose processors. This article doesn't say ANYTHING about the hardware in question. Pit the quantum computers against systems that accelerate work using GPUs and other accelerators (FPGAs, for example). I'm not disputing quantum speedup exists, of course. But it depends on the quantum and conventional systems in question, and the algorithms (algorithms can be optimized for convential computing as well in many cases). Quantum computing has a long way to go, and these declarations of quantum supremacy are often light on facts and employ a lot of hand-waving.