Scientists Prove a Quantum Computing Advantage Over Classical.

Is quantum computing just a flashy new alternative to the ” Georgian Technical University classical” computers that are our smartphones laptops cloud servers high performance computers and mainframes ?

Can they really perform some calculations faster than classical computers can ?  How do you characterize those areas where they can or potentially can do better ?  Can you prove it ?

X Prof. Proving something mathematically is not just making a lot of observations and saying “it seems likely that such and such is the case”.

Y formulated his eponymous algorithm that demonstrated how to factor integers on a quantum computer almost exponentially faster than any known method on a classical computer. This is getting a lot of attention because some people are getting concerned that we may be able to break prime-factor-based encryption like RSA (RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and it is different from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the “factoring problem”) much faster on a quantum computer than the thousands of years it would take using known classical methods. However people skip several elements of the fine print.

Scientists prove 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.

First 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.

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. “Shallow quantum circuits are more powerful than their classical counterparts”.

Quantum computing will advance by the joint scientific research of physicists material scientists, mathematicians, computer scientists and work in other disciplines and engineering. The mathematics underlying quantum computing is ultimately as important as the shiny cryostats we construct to hold our quantum devices. The scientific advancements at all levels need to be celebrated to show that quantum computing is real, serious and on the right path to what we hope will be significant advantages in many application areas.