First proof of quantum computer advantage

quantum computer
Credit: CC0 Public Domain

For many years, quantum computers were not much more than an idea. Today, companies, governments and intelligence agencies are investing in the development of quantum technology. Robert König, professor for the theory of complex quantum systems at the TUM, in collaboration with David Gosset from the Institute for Quantum Computing at the University of Waterloo and Sergey Bravyi from IBM, has now placed a cornerstone in this promising field.

Conventional computers obey the laws of classical physics. They rely on the binary numbers zero and one. These numbers are stored and used for mathematical operations. In conventional memory units, each bit—the smallest unit of information—is represented by a charge that determines whether the bit is set to one or zero.

In a computer, however, a bit can be both zero and one at the same time. This is because the laws of allow electrons to occupy multiple states at one time. Quantum bits, or qubits, thus exist in multiple overlapping states. This so-called superposition allows quantum computers to perform operations on many values in one fell swoop, whereas a single conventional computer must execute these operations sequentially. The promise of lies in the ability to solve certain problems significantly faster.

From conjecture to proof

König and his colleagues have now conclusively demonstrated the advantage of quantum computers. To this end, they developed a quantum circuit that can solve a specific difficult algebraic problem. The new circuit has a simple structure—it only performs a fixed number of operations on each qubit. Such a circuit is referred to as having a constant depth. In their work, the researchers prove that the problem at hand cannot be solved using classical constant-depth . They furthermore answer the question of why the quantum algorithm beats any comparable classical circuit: The quantum algorithm exploits the non-locality of quantum physics.

Prior to this work, the advantage of quantum computers had been neither proven nor experimentally demonstrated—notwithstanding that evidence pointed in this direction. One example is Shor's , which efficiently solves the problem of prime factorization. However, it is merely a complexity-theoretic conjecture that this problem cannot be efficiently solved without quantum computers. It is also conceivable that the right approach has simply not yet been found for classical computers.

Robert König considers the new results primarily as a contribution to complexity theory. "Our result shows that quantum information processing really does provide benefits—without having to rely on unproven complexity-theoretic conjectures," he says. Beyond this, the work provides new milestones on the road to quantum computers. Because of its simple structure, the new quantum circuit is a candidate for a near-term experimental realization of quantum algorithms.

Explore further

Quantum Cloud Services is entering arena with big prize offer

More information: "Quantum advantage with shallow circuits," Science (2018). … 1126/science.aar3106
Journal information: Science

Citation: First proof of quantum computer advantage (2018, October 18) retrieved 18 September 2019 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Feedback to editors

User comments

Oct 18, 2018
A bespoke, single-purpose, quantum engine beats a classical general-purpose computer, or what? I'm not sure what has been proved here.

Would it outperform an equally-special-purpose  circuit? I don't mean as a thought-experiment. Let John Henry go against the steam-hammer.

Oct 19, 2018
Yes Dan R it would. From the abstract:

Bravyi et al. proved theoretically that whereas the number of "steps" needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits.

We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms. Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality.

Oct 19, 2018
So in the meantime, whilst the man in the street cannot afford a shiny new quantum computer, the super-rich and government hackers will be able to undo any and all encryption using their new-found quantum technology.
They themselves will of course ensure that their communications cannot be intercepted or spied upon......

Oct 19, 2018
Fred, you better pray the super-rich and government hackers are not able to trace you. You are taking quite a risk posting stuff like that on a public site. Be careful and watch your back.....

Oct 19, 2018
Don't get your hopes up about owning a quantum computer anytime soon. Compared to computers of today, quantum computers are on a similar level as an abacus. Even though there has been breakthroughs when it comes to the conceptual aspirations for technical advancement in the quantum field, quantum physics is still a mystical realm where laws and general principals do not apply. We have been spoiled when it comes to the "Plug and Play" aspects of today's computers, where as with the quantum compute the "plug" part works perfectly but the "play" is no where to be found. Keeping the dream alive to develop and build the first fully functional quantum computer is "heralded" with each new technical advancement. But not yet.

Oct 20, 2018
I don't fully get it either. The cartoon picture I have is of a game, where I have a vector with n binary entries, and you have to guess it with queries. In a query, you write down your own n binary entry vector and show it to me, I compute the product of both modulo 2 and give you the 1 bit result. It obviously will take n queries for you to figure out my whole vector since it's n bits and I'm giving 1at a time. In the quantum version though, you can solve it in one query: you write down your vector and show it to me, I compute the result and return one qubit, and you then look at your sheet of paper where everything you wrote down changed non-locally while I was computing to get the full answer, violating the bandwidth restraint from the classic version, and making non locality the key to the speed up.

Oct 22, 2018
Yeah, first. Sorry America. Trying to steal the biscuit again... lols.

DWave systems (founded 1999) provided the first functional prototype February 13, 2007. But you know, let's just ignore that. Or let's totally ignore Keio University (Japan)'s masters and PhD programs in quantum computing.

Sorry guys, but you're a DECADE (quite probably two) behind the curve on providing the first "proof of advantage". Heck, even before the theoretical systems were proposed, there was proof of advantage in quantum physics and maths. Oh, I dunno... the complex "solve the fastest route" equation being the easiest example to cite.

First? Far FAR from it. Contributing to the field? Sure. But - put the cookies back in the jar, they're not yours.

Oct 22, 2018
I'll correct myself - the title "first proof of advantage" is misleading, and my kneejerk reaction to it was born from that point. There's been plenty of mathematical proof. The difference here is that it's illustrating a real-world example whereas before it was on paper.

I think that "contributing to new examples demonstrating theorems" might be a better statement. Otherwise, we must draw a philosophical line between mathematical proofs and a computer doing what we say it can do.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more