IBM proves a quantum computing advantage over classical

IBM scientists have mathematically proven that there are certain problems that require only a fixed circuit depth when done on a quantum computer no matter how the number of inputs increase. On a classical computer, these same problems require the circuit depth to grow larger.

The proof is that there will be problems that can only be done on quantum computers and other which can be done much faster on quantum computers.

There is predicted polynomial speedup for Hidden Linear Functions.

We would need millions and millions of extremely high-quality qubits with low error rates and long coherence time for this to work. Today we have 50 at IBM or 72 at Google.

Second, there’s the bit about “faster than any known method on a classical computer.” Since we do not know an efficient way of factoring arbitrary large numbers on classical computers, this appears to be a hard problem. It’s not proved to be a hard problem. If someone next week comes up with an amazing new approach using a classical computer that factors as fast as Shor’s might, then the conjecture of it being hard is false. We just don’t know.

Is everything like that? Are we just waiting for people to be more clever on classical computers so that any hoped-for quantum computing advantage might disappear? The answer is no. Quantum computers really are faster at some things. We can prove it. This is important.

Let’s set up the problem. The basic computational unit in quantum computing is a qubit, short for quantum bit. While a classical bit is always 0 or 1, when a qubit is operating it can take on many other additional values. This is increased exponentially with the potential computational power doubling each time you add an additional qubit through entanglement. The qubits together with the operations you apply to them are called a circuit.

Today’s qubits are not perfect: they have small error rates and they also only exist for a certain length of time before they become chaotic. This is called the coherence time.

Because each gate, or operation, operation you apply to a qubit takes some time, you can only do so many operations before you reach the coherence time limit. We call the number of operations you perform the depth. The overall depth of a quantum circuit is the minimum of all the depths per qubit.

Since error rates and coherence time limit the depth, we are very interested in short depth circuits and what we can do with them. These are the practical circuits today that implement quantum algorithms. Therefore this is a natural place to look to see if we can demonstrate an advantage over a classical approach.

The width of a circuit, that is, the number of qubits, can be related to the required depth of the circuit to solve a specific kind of problem. Qubits start out as 0s or 1s, we perform operations on them involving superposition and entanglement, and then we measure them. Once measured, we again have 0s and 1s.

What the scientists proved is that there are certain problems that require only a fixed circuit depth when done on a quantum computer even if you increase the number of qubits used for inputs. These same problems require the circuit depth to grow larger when you increase the number of inputs on a classical computer.

To make up some illustrative numbers, suppose you needed at most a circuit of depth 10 for a problem on a quantum computer no matter how many 0s and 1s you held in that many qubits for input. In the classical case you might need a circuit of depth 10 for 16 inputs, 20 for 32 inputs, 30 for 64 inputs, and so on for that same problem.

This conclusively shows that fault-tolerant quantum computers will do some things better than classical computers can. It also gives us guidance in how to advance our current technology to take advantage of this as quickly as possible. The proof is the first demonstration of unconditional separation between quantum and classical algorithms, albeit in the special case of constant-depth computations.

In practice, short depth circuits are part of the implementations of algorithms, so this result does not specifically say how and where quantum computers might be better for particular business problems. That’s not really the point. As the paper says, “shallow quantum circuits are more powerful than their classical counterparts.”

The IBM Q team is now working to show examples of this advantage via Qiskit in a Jupyter notebook.

Research paper abstracts from Science and Arxiv

Science – Quantum advantage with shallow circuits

Quantum outperforms classical

Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-founded) conjectures in computational complexity theory, but rigorous comparisons between the capabilities of quantum and classical algorithms are difficult to perform. Bravyi et al. proved theoretically that whereas the number of “steps” needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits.

Abstract

Quantum effects can enhance information-processing capabilities and speed up the solution of certain computational problems. Whether a quantum advantage can be rigorously proven in some setting or demonstrated experimentally using near-term devices is the subject of active debate. 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).