Surprise Comes Out of Black-Hole Studies: Error-Correcting Codes

Information seems abstract, but it plays surprisingly substantive roles in physics; for example, trying to understand what happens to the information content of matter that falls into a black hole has forced theorists to question their views of relativity and quantum mechanics. Now, their attempt to reconcile quantum information and gravity has revealed a surprising connection: new types of error-correcting codes for proposed quantum computers have emerged from tools developed to study quantum gravity.

For decades, physicists have aspired to compute using quantum bits, or qubits, in place of the bits used by "classical" computers. Because each qubit can represent both 0 and 1 simultaneously, an assembly of them could in principle perform some massively parallel computations exponentially faster than an ordinary computer. Unfortunately, the delicate quantum states can be disrupted by tiny changes in the environment, so even a carefully isolated system would not have time to complete a usefully complex calculation.

This problem could be solved in an ordinary computer by using an error-correcting code, such as redundantly representing 1 x 3 independent bits, 111. Even if one of the bits is changed, invoking a majority rule will still give a reliably correct answer (at the cost of extra hardware to store the redundant bits). Quantum mechanics, however, forbids "cloning" of a quantum state, so physicists at first thought that error correction would be impossible for quantum computing, making it much less useful.

In the mid-1990s, however, researchers were able to show that quantum error correction could be achieved by spreading the quantum state among many qubits (without looking at them, which would destroy the quantum information). If the combination is chosen properly, then even if one of the qubits is disturbed, the combined state preserves the original information (just as 110, 101, and 111 still represent 1 for three classical bits).

In these schemes, "the information is stored non-locally in the entanglement between the qubits," said Daniel Harlow, a post-doctoral researcher in the High Energy Theory Group of the Center for the Fundamental Laws of Nature at Harvard University. Entanglement, called "spooky action at a distance" by Einstein, links the measured properties of two separated quantum systems, such as qubits. Even though the outcome for each is intrinsically unpredictable, the two will always agree. "It’s almost like you have two copies–but not quite," said Harlow. The challenge is to identify specific ways to efficiently entangle a set of qubits so the information is reliably preserved. In recent papers, Harlow and others showed that working correction schemes can be deduced from a surprising source: the analysis of quantum gravity.  

In the late 1990s, theoretical physicist Juan Maldacena, now at the Institute for Advanced Study in Princeton, NJ, proposed the "AdS/CFT correspondence," which mathematically maps some models of gravity onto gravity-free quantum field theories. The correspondence is called "holographic" because the quantum model reigns on the boundary surrounding the gravity theory and so has one fewer dimension. The models are equivalent, so solving either one immediately sheds light on the other, just as illuminating a two-dimensional hologram can recreate a three-dimensional shape. The AdS/CFT correspondence has been extensively exploited by physicists to study both gravitational and quantum systems.

For the new error-correction picture, the physical qubits are imagined to be on the boundary, while the information to be preserved corresponds to activity deep in the bulk. The rules of the correspondence, called "the dictionary," show how to translate a bulk state into a particular entangled combination of physical qubits. In particular, low-energy states in the quantum-gravity bulk are highly entangled, Harlow said. "The key insight from this work that they’re entangled in the way to do quantum error correction," Harlow said. "This has led to people coming up with codes that are different from any before, and in some ways better."

These new codes have not yet changed the way people plan to do quantum computing, said Daniel Gottesman of the Perimeter Institute for Theoretical Physics, in Waterloo, ON. Existing codes that he and others developed already correct rare errors perfectly: a common rule of thumb is that errors should occur less than once in every 10,000 operations, although the precise number varies. Some experimental qubit systems are approaching this threshold, although many practical barriers to quantum computing remain.

Still, "the latest work leads not just to new codes, but new approaches," Gottesman said, "which could lead the field in new directions."

Don Monroe is a science and technology writer based in Boston, MA.