There’s Now a Proven Way for Quantum Computers to Beat Classical Computers—With a Catch

Entrepreneurs and physicists are pursuing a new kind of computer—one based on the physics of the subatomic particles—that promises to revolutionize various fields. Presumably, such a quantum computer should offer some advantage over the classical computers we already use, right? The trouble is, it’s unclear what tasks quantum computers can definitively perform better than regular computers.

Today, a team of researchers from IBM and the Technical University of Munich in Germany have released a paper proving a real advantage that a near-term quantum computer could have over a classical computer. The proof puts stringent limits on both the quantum computer and the classical computer’s abilities, and doesn’t yet demonstrate the hyped and long-sought “quantum supremacy.” But it’s an important stepping stone in showing that these nascent quantum processors might one day live up to all their hype.

Here’s the usual quantum spiel: Today’s classical computers translate every problem into long strings of binary code, represented by bits that could equal either zero and one. There are certain lucrative endeavors for which a new kind of computer might offer an advantage, such as factoring very large numbers, modeling molecules, or artificial intelligence. A quantum computer’s quantum bits, or qubits, communicate in a whole new way. Qubits can take on values in between zero and one during the calculation and interact in ways regular computers bits can’t. Quantum processors still always return binary strings, meaning zeroes and ones, except each qubit’s final value has an innate probability based on how close its value was to zero or one right before the program measured the qubit. Qubits can also entangle, where the probabilities apply to combinations of two or more qubits’ values simultaneously.

Several present-day quantum computers exist in rudimentary forms from companies including IBM and Rigetti, generally with 20 or less qubits. As they move ahead with building these devices, physicists and computer scientists are developing quantum algorithms they hope will solve problems better than a classical computer can. But there’s always the chance that some better classical computer algorithm exists for the problem that just hasn’t been devised yet—in which case, why bother with the quantum machine? That’s why scientists have set out looking for definitive proof of areas in which a quantum computer might offer a speedup.

“A quantum computer might seem to be faster, but you want to have rigorous mathematical proofs,” Bob Sutor, VP of Cognitive, Blockchain, and Quantum Solutions at IBM Research, told Gizmodo.

A proof devised by IBM scientists last year but published in the journal Science today proves that a limited quantum computer could always beat a classical computer at solving a simple linear algebra problem—but only if the classical computer has the same limits as the quantum computer. 

Those limits are the same ones faced by today’s quantum computers and are referred to as having “shallow circuits.” Computer scientists call single units of bit interaction “logic gates.” These gates return a value based on one or more bits. Quantum gates instead move a qubit’s value to somewhere else between zero or one, or change the built-in statistics of an entangled qubit pair. A “circuit” is a series of gates. A “shallow quantum circuit” is one where each qubit can only perform a limited number of gates before becoming a zero or a one again, and those gates can only involve, at most, one other qubit. It’s fine if two gates occur on unrelated pairs of qubits on the processor simultaneously.

Rather than compare a general quantum computer with a general classical computer, they just put the same limits on a classical computer. “We just ask a different question,” explained Sergey Bravyi, IBM researcher. “We compared shallow quantum circuits and shallow classical circuits.”

If you get anything from this article, it’s this: A new paper found a specific scenario in which a quantum computer (let’s think of it as a particularly clever child) would always win in a footrace against a classical computer (let’s this of this as an adult marathon runner), regardless of the race length. The child’s cunning represents the quantum computer’s ability to act quantum-ly; it’s like finding shortcuts along the race route. But according to the race’s rules, the marathon runner must always take the same-sized strides as the child.

So, there are a lot of caveats, but that’s still an important milestone.

“It’s nice to have clean statements that can tell us about the relationship between quantum and classical computers,” Andrew Childs, computer scientist at the University of Maryland, told Gizmodo. “We have to start somewhere, and having a theoretical advance is a step in the right direction when we haven’t seen something like it before.”

And it’s important that scientists still have the full-powered classical computer to verify that the quantum computer returned the right results, said Bravyi. This is not the same as Google’s quantum supremacy experiment, which is instead a devised problem that a quantum computer can solve exponentially faster than a classical computer simulating a quantum computer.

Additionally, most of the previously described cases in which quantum computers promise to beat a classical computer without the shallow circuit limit (such as the Shors algorithm, which factors numbers) still require some overall assumption about what’s possible to do with classical computers, Aram Harrow, MIT theoretical physics professor, told Gizmodo. In other words, you might assume, without actually proving it, that the marathon runner can’t outrun a cheetah. This paper doesn’t require assumptions like that.

But the new paper is not perfect. “This is not for a practical problem, and no one has proposed connecting it to a practical problem,” said Harrow. “Even if it were, the speedup would be too small to care about in practice. If a quantum computer is only a little bit faster than a classical computer of the same size, then the fact that quantum computers are so much harder to build would make us opt for the classical algorithm.”

IBM and others are powering forward to build their quantum computers, and Sutor told Gizmodo that he hopes to actually perform one of these tests on an existing IBM quantum processor in the next week or so. There’s still a long way to go, and even though quantum computers continue to grow in size and promise, physicists are still laying the bricks of their underlying mathematical foundation.