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 IBM Q Strategy and EcosystemÂ at IBM Research, told Gizmodo.

Advertisement

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

Advertisement

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

Advertisement

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

Advertisement

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.

[Science]