Quantum computing’s (debatably) big milestone: Beating a supercomputer

The unique selling point of quantum computers is that, theoretically, they could outperform classical computers at some tasks, ushering in a new world of computing performance. That's in theory; showing it to be the case has proved rather more difficult.

Until very recently, today's prototype quantum computers have been too small and limited to take on calculations that couldn't be performed equally well on a classical machine. So showing that there's any genuine advantage to quantum computing has been all but impossible.

Nevertheless, in 2012, quantum information theorist John Preskill coined a term for a demonstration of this sort: quantum supremacy. "By quantum supremacy we mean quantum computing that does something that can't be matched by the most powerful computers we have today, or at least would be very hard to do," he says.

It became a somewhat controversial phrase, not least because "supremacy" has acquired troubling political connotations — as one group of scientists has put it , the word "has overtones of violence, neocolonialism and racism." Some researchers prefer to speak instead of "quantum advantage." Besides, no one ever anticipated that there would be an unambiguous threshold of device performance above which quantum supremacy could be declared. For one thing, how hard a computation is by classical means varies from one problem to another. All the same, for many researchers, the notion of quantum supremacy persists, and an experimental demonstration of it would represent a significant milestone in the evolution of quantum computers, establishing their real potential to achieve unprecedented things in the future.

It has long been suspected that a quantum computer with just 50 or so qubits of sufficient quality should be capable of demonstrating quantum supremacy. That, says Preskill, should give it a capacity to conduct calculations "beyond what can be simulated by brute force using the most powerful existing supercomputers." Because the number of different qubit states effectively doubles with every additional qubit, 50 of them gives access to a staggering 1 quadrillion (10 to the power 15).

Project Sycamore

Google Research's AI Quantum group in Mountain View has now made such a machine. At the end of 2019, its hardware team, led by John Martinis prior to his recent departure from the company , used it to claim the first clear demonstration of quantum supremacy. But a good enough quantum computer — with enough, and good enough, qubits — was not the whole story. Also required was an algorithm that could be shown, with confidence, to be tractable at this scale with a quantum computer but not with a classical one.

The Google team identified one: to figure out what output to expect, given a specified set of binary inputs, from a series of qubits connected randomly into a quantum circuit.

If that sounds like something a quantum computer should be good at, well, that's the whole point. To solve the problem classically, you must simulate the quantum problem using complicated mathematical approximations. This makes the problem not unlike that of quantum simulation: trying to predict the properties of a collection of quantum objects, such as atoms linked into a complex molecule or material. Such simulations are likely to be one of the first major applications of early quantum computers. Here, they have the advantage that, rather than needing some cumbersome classical approximation to the quantum rules governing the objects and their interactions, such rules would essentially be built into the very way that a quantum computer works.

To carry out their study, Martinis and his colleagues at the time developed a bespoke quantum chip, called the Sycamore processor, in which 54 qubits were linked into a two-dimensional grid so that each had four neighbors. This architecture permits easy connection of the qubits into random circuits. These qubits had to have very low error rates for the algorithm to work: about 0.6%, "which is best in the world right now for such a large device," Martinis said in an interview prior to his departure from Google. What's more, keeping so many qubits in the quantum-entangled state needed for the computation is at the limit of what is currently possible.

"Doing all three things, all hard, and at the same time is a lot of work," Martinis said. But it did work.

A demonstration of power?

Even so, while the Google result was hugely impressive and widely praised, it should be kept in context. This quantum computer had to be carefully tuned to the problem, both in terms of hardware and the algorithm that it ran — although Martinis' Google colleague Sergio Boixo pointed out that this did not prevent it from being able to execute other tasks too.

What's more, a team at IBM — perhaps Google's main competitor in this field, admittedly — announced in the wake of Google's result that they had found a way to simulate the same computation on one of IBM's classical supercomputers much faster than the 10,000 years Martinis and colleagues said would be needed — in fact, in just two and a half days or less — and with better fidelity than the quantum computation.

That claim is still being debated by experts. All the same, IBM's Edwin Pednault and his colleagues suggested skepticism was in order. "We urge the community to treat claims that, for the first time, a quantum computer did something that a classical computer cannot with a large dose of skepticism."

And while Google's claim of supremacy affirms the potential of this technology, it doesn't signal the impending obsolescence of classical computation. The milestone is as much psychological as technological.

"Quantum supremacy is a worthy goal, notable for entrepreneurs and investors not so much because of its intrinsic importance but rather as a sign of progress toward more-valuable applications further down the road," Preskill says.

Martinis agrees with that. "We think this is a big deal since it directly shows to engineers and technologists that powerful quantum computing is not just a pipe dream, but a reality — and it is coming," he says. "I think physicists don't think this way, since they expect it to work. But the rest of the world wanted some kind of demonstration that you could do a powerful computation."