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]