How quantum computers will correct their mistakes

In 1994 Peter Shore, a mathematician at Bell Labs in New Jersey, proved that a quantum computer can solve certain problems exponentially faster than a classical computer. The question was, can you build a quantum computer? Skeptics argued that quantum states are too fragile – the environment will inevitably mix information in a quantum computer, making it completely non-quantum.

Shore answered a year later. Classical circuits measured individual bits to check for errors, but this approach would not work for quantum bits or “qubits,” since any measurement would destroy the quantum state and therefore the computation. Shore found a way to determine if an error occurred without measuring the state of the qubit itself. Shor’s code marked the beginning of the field of quantum error correction.

The field of quantum error correction has blossomed. Most physicists see it as the only way to create an extremely powerful quantum computer. “Without error correction, we cannot scale quantum computers to the point where they can solve really difficult problems,” said John Preskill, a physicist at the California Institute of Technology.

As with quantum computing in general, it is one thing to develop error-correcting code, and quite another to implement it on a running machine. But in early October, researchers led by Chris Monroe, physics from the University of Maryland, reportedthat they demonstrated many of the ingredients required for Shor’s error correction scheme to work.

So how did Shore manage to solve the riddles he faced? He used the added complexity of quantum mechanics to his advantage.

Repeat repeat repeat

Shore modeled his protocol after the classic repeater code, which involves making copies of each bit of information and then periodically comparing those copies with each other. If one of the bits is different from the others, the computer can correct the error and continue the calculation.

Shor developed a quantum version of this protocol. He used three separate “physical” qubits to encode one qubit of information – a “logical” qubit. However, Shor’s quantum follower code could not exactly match the classical version. The significant power of quantum computing stems from the fact that qubits can exist in a “superposition” by being in a combination of 0 and 1 at the same time. Since measuring a quantum state would destroy the superposition, there was no easy way to check if an error had occurred.

Instead, Shore found a way to determine if three physical qubits are in the same state. If one of the qubits is different, it means that an error has occurred.

The task is not much different from solving a simple logic puzzle. You are given three balls that look the same, but one of the balls may have a different weight. You also have a simple scale. What measurements will allow you to determine if there is a different ball among the balls, and if so, which one?

The answer is to first weigh two balls, then replace one of the balls with the remaining ball and weigh again. If the scales were balanced both times, then all balls are identical. If the scales were balanced only once, then one of the replaced balls is different. If the weight is different both times, then the third ball is to blame.

Shor’s code replaces the scales with two additional “auxiliary” qubits. The first one compares the first and second physical qubits; the other compares the second and the third. By measuring the states of these auxiliary qubits, you can tell if three qubits containing information are in identical states without disturbing the states of any of them.

This code protects against bit flipping, which is the only possible error that occurs in classical computing. But qubits have another potential source of error.

Superposition is the key to quantum computing, but it’s not just the value of the qubit that matters. The relative “phase” between qubits also matters. You can think of this phase as a wave – it tells you the location of the peaks and troughs of the wave. When two waves are in phase, their peaks are synchronized. If they collide, they interfere, merging into a single wave twice the size. But if the waves are out of phase, then one wave is at a peak, the other is at a trough, and they neutralize each other.

The quantum algorithm uses this phase relationship between qubits. This creates a situation where the correct computation response interferes constructively and therefore amplifies, while the wrong response is suppressed by destructive interference.

But if the error results in a phase change, then destructive interference can switch to constructive interference and the quantum computer will start amplifying the wrong answer.

Shore discovered that he could correct phase errors using a principle similar to the one he used to switch bits. Each logical qubit is encoded into three qubits, and additional qubits check to see if one of the phases has changed.

Shor then combined the two codes. The result was a code that translated one logical qubit into nine physical qubits that offered both bit and phase checks.

Resilience to errors

Shor’s code basically protects an individual logical qubit from errors. But what if there was an error in the error measurements themselves? When trying to fix a non-existent error, you will switch a bit and inadvertently introduce a real error. In some cases, this can cause a cascade of errors that propagate through the code.

Shor’s code also did not consider how he would control a quantum computer built from his logical qubits. “We need some way to do coded state computation without losing this protection. And it’s not easy, “- said Daniel Gottesman, a theoretical scientist at the University of Maryland.

Then in 1996 Shor came up with the concept of fault tolerance. Fault-tolerant code can deal with errors introduced by the environment, imperfect operations on qubits, and even the error correction steps themselves – provided that the frequency of these errors is below a certain threshold.

Last month, Monroe and his team announced that they were using a crash-resistant version of Shor’s code, called Bacon-Shor’s code, to demonstrate nearly all the tools needed for a fully fault-tolerant quantum computer. They encoded a logic qubit into nine-ion quantum states, and then, using four auxiliary qubits, showed that they could flawlessly perform all the single-qubit operations required for quantum computing. The result shows that a fault-tolerant quantum computer is possible.

However, the creation of a quantum computer is not yet close. Monroe believes that the benefits of error correction will not be noticeable until quantum computers reach about 100 logical qubits. Such a machine would require about 1300 physical qubits, since each logical qubit needs nine physical qubits plus four auxiliary ones (currently the largest quantum processor, recently announced IBM Eagle, has 127 physical qubits). At this stage, “we’re going to start building a qubit factory and then implementing bug fixes,” Monroe said. “But not before.”