Quantum Computing Without the Hype: Amplitudes, Interference and the Long Road to Error Correction

Asked for the basics, Aaronson describes quantum computing as a proposal for a new way to harness nature to compute, based on principles of quantum mechanics that have been fixed since 1926. What is new is how people want to use them. Physicists, he says, have long convinced others that the subject is hopelessly complicated.

His secret is that it becomes much simpler if you do what quantum information theorists do and take the physics out. Quantum mechanics then looks like a generalization of the rules of probability. Nobody would say there is a negative 30 percent chance of snow, but the world is described by numbers called amplitudes, which can be positive, negative or even complex.

A superposition just assigns an amplitude to every possible configuration you might see on measuring. Looking at an electron forces those amplitudes to become probabilities, found by taking the squared absolute value. While a system is isolated, though, its amplitudes evolve by rules unlike ordinary probability. Aaronson says every weird quantum phenomenon is another consequence of nature being described by these amplitudes.

Amplitudes can interfere, which Aaronson illustrates with the double-slit experiment. There are places on the second screen where an electron never lands, yet closing one slit makes it possible to land there. Reducing the number of paths therefore raises the chance of arriving. The electron has one amplitude for each slit, and if they point in opposite directions they cancel to zero.

He defines a quantum computer as a machine that exploits superposition, amplitudes and interference to solve certain problems much faster than we know how to otherwise. Its basic unit is the qubit, with an amplitude for zero and another for one. The key point is scale: a thousand qubits need an amplitude for every setting of all thousand bits, meaning two to the 1000th amplitudes, more than would fit in the observable universe.

This is where Aaronson says popular articles go off the rails. They repeat the exponential-amplitudes point and then claim a quantum computer works by trying every possible answer in parallel. He says that sounds too good to be true and unfortunately it kind of is. Making a superposition over all answers is easy, but measuring it yields only a random one, which you could have picked yourself with far less trouble.

The real art, he explains, is choreographing a pattern of interference. For each wrong answer, some of the paths leading to it should have positive amplitudes and others negative, so they cancel. All the paths to the right answer should point the same way and reinforce each other. Designing quantum algorithms is exactly the choreography of interference.

Fridman then asks where information fits in. Aaronson answers that the bit has been the basic unit of information since Shannon's 1948 paper, and the qubit is its quantum counterpart: any object that can be manipulated in a superposition of zero and one. Physically, qubits can be superconducting coils cooled close to absolute zero, as in Google's quantum supremacy experiment, or the spin of an atomic nucleus. Like a programmer who needs no knowledge of transistors, he says, the logic of qubits is the same whatever the hardware.

In principle the logic of qubits is separate from the hardware, but Aaronson admits that today the layers interfere because machines are noisy. The hope is error-corrected quantum computers whose qubits behave like perfect abstract ones for as long as desired. Today's problem, he says, is more specifically decoherence, recognized since the 1990s: unwanted interaction between the qubits and the outside environment.

Measurement collapses a superposition, and it does not need a conscious observer. If information about whether a qubit was zero or one leaks into radiation, air molecules or connected wires, it is as if the qubit was measured. The qubit has become entangled with its environment. So the qubits must be fanatically isolated, yet still controlled and made to interact in a precisely choreographed way, which led some distinguished scientists in the 1990s to call it impossible.

What changed minds, Aaronson says, was the mid-to-late 1990s theory of quantum error correction and fault tolerance. Qubits need not be perfectly isolated, only very well isolated. If leaks occur at a low enough rate, information can be encoded across the collective state of many qubits, so a small percentage of leaks can be detected and corrected. That discovery set the engineering agenda for the field up to the present.

The goal is to reach a break-even point where error correction is a net win, after which simulated qubits can simulate even more reliable ones. He says we are not there yet, but orders of magnitude closer than in the 1990s. The catch is overhead: breaking RSA would need several thousand logical qubits, and with known codes each needs thousands of physical qubits, so millions overall.

That overhead, he says, is why quantum computers are not already breaking cryptography, and it is multiplicative, roughly a factor of a thousand. Much work goes into better codes in the meantime.

Aaronson says we are in what physicist John Preskill called the noisy intermediate-scale quantum, or NISQ, era. He compares it to the early vacuum tube days of classical computing, noting that the quantum analog of the transistor, perhaps true error correction, has not been invented. Still, since Google's quantum supremacy announcement, a noisy device has done something hard for classical computers to simulate.

Whether such machines can do something both beyond classical computers and useful is still unknown. Google, IBM, startups, research labs and governments will race to find out over the next decade. Asked what it takes to escape the vacuum tube era, he guesses all of the above: it is fundamentally an engineering issue, since the theory has existed since the 1990s, but the hardware is not at that level.

Someone could conceivably spend a trillion dollars on a quantum Manhattan Project and build the error-corrected machine envisioned in the 1990s. He thinks it more plausible that further theoretical breakthroughs will cut the cost of doing it.