Facebook
Twitter
Pocket
Reddit
Email
Quantum computers will never fully replace “classical” ones like the device you’re reading this article on. They won’t run web browsers, help with your taxes, or stream the latest video from Netflix.
What they will do—what’s long been hoped for, at least—will be to offer a fundamentally different way of performing certain calculations. They’ll be able to solve problems that would take a fast classical computer billions of years to perform. They’ll enable the simulation of complex quantum systems such as biological molecules, or offer a way to factor incredibly large numbers, thereby breaking long-standing forms of encryption.
The threshold where quantum computers cross from being interesting research projects to doing things that no classical computer can do is called “quantum supremacy.” Many people believe that Google’s quantum computing project will achieve it later this year. In anticipation of that event, we’ve created this guide for the quantum-computing curious. It provides the information you’ll need to understand what quantum supremacy means, and whether it’s really been achieved.
What is quantum supremacy and why is it important?
To achieve quantum supremacy, a quantum computer would have to perform any calculation that, for all practical purposes, a classical computer can’t.
In one sense, the milestone is artificial. The task that will be used to test quantum supremacy is contrived—more of a parlor trick than a useful advance (more on this shortly). For that reason, not all serious efforts to build a quantum computer specifically target quantum supremacy. “Quantum supremacy, we don’t use [the term] at all,” said Robert Sutor, the executive in charge of IBM’s quantum computing strategy. “We don’t care about it at all.”
But in other ways, quantum supremacy would be a watershed moment in the history of computing. At the most basic level, it could lead to quantum computers that are, in fact, useful for certain practical problems.
There is historical justification for this view. In the 1990s, the first quantum algorithms solved problems nobody really cared about. But the computer scientists who designed them learned things that they could apply to the development of subsequent algorithms (such as Shor’s algorithm for factoring large numbers) that have enormous practical consequences.
“I don’t think those algorithms would have existed if the community hadn’t first worked on the question ‘What in principle are quantum computers good at?’ without worrying about use value right away,” said Bill Fefferman, a quantum information scientist at the University of Chicago.
The quantum computing world hopes that the process will repeat itself now. By building a quantum computer that beats classical computers—even at solving a single useless problem—researchers could learn things that will allow them to build a more broadly useful quantum computer later on.
“Before supremacy, there is simply zero chance that a quantum computer can do anything interesting,” said Fernando Brandão, a theoretical physicist at the California Institute of Technology and a research fellow at Google. “Supremacy is a necessary milestone.”
In addition, quantum supremacy would be an earthquake in the field of theoretical computer science. For decades, the field has operated under an assumption called the “extended Church-Turing thesis,” which says that a classical computer can efficiently perform any calculation that any other kind of computer can perform efficiently. Quantum supremacy would be the first experimental violation of that principle and so would usher computer science into a whole new world. “Quantum supremacy would be a fundamental breakthrough in the way we view computation,” said Adam Bouland, a quantum information scientist at the University of California, Berkeley.
How do you demonstrate quantum supremacy?
By solving a problem on a quantum computer that a classical computer cannot solve efficiently. The problem could be whatever you want, though it’s generally expected that the first demonstration of quantum supremacy will involve a particular problem known as “random circuit sampling.”
A simple example of a random sampling problem is a program that simulates the roll of a fair die. Such a program runs correctly when it properly samples from the possible outcomes, producing each of the six numbers on the die one-sixth of the time as you run the program repeatedly.
In place of a die, this candidate problem for quantum supremacy asks a computer to correctly sample from the possible outputs of a random quantum circuit, which is like a series of actions that can be performed on a set of quantum bits, or qubits. Let’s consider a circuit that acts on 50 qubits. As the qubits go through the circuit, the states of the qubits become intertwined, or entangled, in what’s called a quantum superposition. As a result, at the end of the circuit, the 50 qubits are in a superposition of 250 possible states. If you measure the qubits, the sea of 250 possibilities collapses into a single string of 50 bits. This is like rolling a die, except instead of six possibilities you have 250, or 1 quadrillion, and not all of the possibilities are equally likely to occur.
Quantum computers, which can exploit purely quantum features such as superpositions and entanglement, should be able to efficiently produce a series of samples from this random circuit that follow the correct distribution. For classical computers, however, there’s no known fast algorithm for generating these samples—so as the range of possible samples increases, classical computers quickly get overwhelmed by the task.
What’s the holdup?
As long as quantum circuits remain small, classical computers can keep pace. So to demonstrate quantum supremacy via the random circuit sampling problem, engineers need to be able to build quantum circuits of at least a certain minimum size—and so far, they can’t.
Circuit size is determined by the number of qubits you start with, combined with the number of times you manipulate those qubits. Manipulations in a quantum computer are performed using “gates,” just as they are in a classical computer. Different kinds of gates transform qubits in different ways—some flip the value of a single qubit, while others combine two qubits in different ways. If you run your qubits through 10 gates, you’d say your circuit has “depth” 10.
“It’s not like a rocket launch or a nuclear explosion, where you just watch and immediately know whether it succeeded,” says Scott Aaronson
To achieve quantum supremacy, computer scientists estimate a quantum computer would need to solve the random circuit sampling problem for a circuit in the ballpark of 70 to 100 qubits with a depth of around 10. If the circuit is much smaller than that, a classical computer could probably still manage to simulate it — and classical simulation techniques are improving all the time.
Yet the problem quantum engineers now face is that as the number of qubits and gates increases, so does the error rate. And if the error rate is too high, quantum computers lose their advantage over classical ones.
There are many sources of error in a quantum circuit. The most crucial one is the error that accumulates in a computation each time the circuit performs a gate operation.
At the moment, the best two-qubit quantum gates have an error rate of around 0.5%, meaning that there’s about one error for every 200 operations. This is astronomically higher than the error rate in a standard classical circuit, where there’s about one error every 1017operations. To demonstrate quantum supremacy, engineers are going to have to bring the error rate for two-qubit gates down to around 0.1%.
How will we know for sure that quantum supremacy has been demonstrated?
Some milestones are unequivocal. Quantum supremacy is not one of them. “It’s not like a rocket launch or a nuclear explosion, where you just watch and immediately know whether it succeeded,” said Scott Aaronson, a computer scientist at the University of Texas, Austin.
To verify quantum supremacy, you have to show two things: that a quantum computer performed a calculation fast, and that a classical computer could not efficiently perform the same calculation.
It’s the second part that’s trickiest. Classical computers often turn out to be better at solving certain kinds of problems than computer scientists expected. Until you’ve proved a classical computer can’t possibly do something efficiently, there’s always the chance that a better, more efficient classical algorithm exists. Proving that such an algorithm doesn’t exist is probably more than most people will need in order to believe a claim of quantum supremacy, but such a claim could still take some time to be accepted.
How close is anyone to achieving it?
By many accounts Google is knocking on the door of quantum supremacy and could demonstrate it before the end of the year. (Of course, the same was said in 2017.) But a number of other groups have the potential to achieve quantum supremacy soon, including those at IBM, IonQ, Rigetti and Harvard University.
These groups are using several distinct approaches to building a quantum computer. Google, IBM and Rigetti perform quantum calculations using superconducting circuits. IonQ uses trapped ions. The Harvard initiative, led by Mikhail Lukin, uses rubidium atoms. Microsoft’s approach, which involves “topological qubits,” seems like more of a long shot.
Each approach has its pros and cons.
Superconducting quantum circuits have the advantage of being made out of a solid-state material. They can be built with existing fabrication techniques, and they perform very fast gate operations. In addition, the qubits don’t move around, which can be a problem with other technologies. But they also have to be cooled to extremely low temperatures, and each qubit in a superconducting chip has to be individually calibrated, which makes it hard to scale the technology to the thousands of qubits (or more) that will be needed in a really useful quantum computer.
Ion traps have a contrasting set of strengths and weaknesses. The individual ions are identical, which helps with fabrication, and ion traps give you more time to perform a calculation before the qubits become overwhelmed with noise from the environment. But the gates used to operate on the ions are very slow (thousands of times slower than superconducting gates) and the individual ions can move around when you don’t want them to.
At the moment, superconducting quantum circuits seem to be advancing fastest. But there are serious engineering barriers facing all of the different approaches. A major new technological advance will be needed before it’s possible to build the kind of quantum computers people dream of. “I’ve heard it said that quantum computing might need an invention analogous to the transistor—a breakthrough technology that performs nearly flawlessly and which is easily scalable,” Bouland said. “While recent experimental progress has been impressive, my inclination is that this hasn’t been found yet.”
Say quantum supremacy has been demonstrated. Now what?
If a quantum computer achieves supremacy for a contrived task like random circuit sampling, the obvious next question is: OK, so when will it will do something useful?
The usefulness milestone is sometimes referred to as quantum advantage. “Quantum advantage is this idea of saying: For a real use case—like financial services, AI, chemistry—when will you be able to see, and how will you be able to see, that a quantum computer is doing something significantly better than any known classical benchmark?” said Sutor of IBM, which has a number of corporate clients like JPMorgan Chase and Mercedes-Benz who have started exploring applications of IBM’s quantum chips.
A second milestone would be the creation of fault-tolerant quantum computers. These computers would be able to correct errors within a computation in real time, in principle allowing for error-free quantum calculations. But the leading proposal for creating fault-tolerant quantum computers, known as “surface code,” requires a massive overhead of thousands of error-correcting qubits for each “logical” qubit that the computer uses to actually perform a computation. This puts fault tolerance far beyond the current state of the art in quantum computing. It’s an open question whether quantum computers will need to be fault tolerant before they can really do anything useful. “There are many ideas,” Brandão said, “but nothing is for sure.”
Correction July 18, 2019: Mikhail Lukin’s group at Harvard is making a quantum computer out rubidium atoms controlled with laser light, not photons as the article originally stated.
Lead image: Graham Carlow
Get the Nautilus newsletter
Cutting-edge science, unraveled by the very brightest living thinkers.
