There’s now proof that quantum computers can outperform classical machines

The hype around quantum computing is real. But to fully realize the promise of quantum computing, it’ll still take a few years of research and scientific breakthroughs. And indeed, it still remains to be seen if quantum computers will ever live up to the hype. Today, though, we got mathematical proof that there are really calculations that quantum computers will definitely be able to perform faster than any classical computer.

What we have today are quantum computers with a very limited number of qubits and short coherence time. Those limitations put a damper on the amount of computation you can perform on those machines, but they still allow for some practical work. Unsurprisingly, researchers are very interested in seeing what they can do with the current set of available machines. Because they have such short coherence time before the system becomes chaotic and useless for any computations, you can only perform a relatively small number of operations on them. In quantum computing speak, that’s “depth,” and today’s systems are considered shallow.
Science today published a paper (“Quantum advantage with shallow circuits”) by Sergey Bravyi of IBM Research, David Gosset of the University of Waterloo’s Institute for Quantum Computing and Robert König of the Institute for Advanced Study and Zentrum Mathematik, Technische Universität München. In this paper, the researchers prove that a quantum computer with a fixed circuit depth is able to outperform a classical computer that’s tackling the same problem because the classical computer will require the circuit depth to grow larger, while it can stay constant for the quantum computer.
 
There is very little that’s intuitive about quantum computing, of course, but it’s worth remembering that quantum computers are very different from classical computers.
“Quantum circuits are not just basically the same but different from classical circuits,” IBM Q Ecosystem and Strategy VP Bub Sutor told me. Classic circuits, […]they are bits, they are zeros and ones, and there’s binary logic, ANDs, ORs, NOTs and things like. The very, very basic gate sets, the types of operations you can do in quantum are different. When these qubit are actually operating, with this notion of superposition you have much, much more to operate elbow room, not just two bits. You actually have a tremendous amount of more room here.” And it’s that additional room you get, because qubits can encode any number and not just zeros and ones, that allows them to be more powerful than a classical computer in solving the specific kind of problem that the researchers tackled.
The question the researchers here asked was if constant-depth quantum circuits can solve a computational problem that constant-depth classical circuits cannot? The problem they decided to look at is a variation on the well-known Bernstein-Vazirani problem (well-known among quantum computing wonks, that is). You don’t need to jump into the details here, but the researchers show that even a shallow quantum computer can easily outperform a classical computer in solving this problem.

“We tried to understand what kinds of things we can do with a shallow quantum circuit and looked for an appropriate model for a type of computation that can be done on a near-term quantum device,” Bravyi told me. “What our result says is that there are certain computational problems for which you can solve on a quantum computer with a constant depth. So as you increase the number of input bits, the depth of the quantum algorithm that solves the problem remains constant.” A constant depth classical computer can not solve this problem, though.
Sutor was very quick to note that we shouldn’t over-hype the current state of quantum computing or this result, though. “We try to be extremely cautious and honest in terms of saying ‘this is what quantum computers can do today’ versus what classical computers will do,” he told me. “And we do this for a very specific reason in that that this is something that will play out over the next three to five years and decades — probably decades.” But what this result shows is that it’s worth exploring quantum algorithms.
As Sutor noted, “there is still this core question, which is, ‘why are you bothering?’” Today’s result should put that question to rest, but Sutor still stressed that he tries to stay grounded and never says quantum computing “will” do something until it does. “There’s a strategy through this, but there’s going to be little left turns and right turns along the way.”
Source: TechCrunch
To Read Our Daily News Updates, Please Visit Inventiva Or Subscribe Our Newsletter & Push.