How Space and Time Could Be a Quantum Error-Correcting Code
In toy “holographic” universes (if not the real universe), the fabric of space and time emerges from a network of quantum particles. Physicists have discovered that this works according to a principle called quantum error correction.
DVDP for Quanta Magazine
Introduction
In 1994, a mathematician at AT&T Research named Peter Shor brought instant fame to “quantum computers” when he discovered that these hypothetical devices could quickly factor large numbers — and thus break much of modern cryptography. But a fundamental problem stood in the way of actually building quantum computers: the innate frailty of their physical components.
Unlike binary bits of information in ordinary computers, “qubits” consist of quantum particles that have some probability of being in each of two states, designated |0⟩ and |1⟩, at the same time. When qubits interact, their possible states become interdependent, each one’s chances of |0⟩ and |1⟩ hinging on those of the other. The contingent possibilities proliferate as the qubits become more and more “entangled” with each operation. Sustaining and manipulating this exponentially growing number of simultaneous possibilities are what makes quantum computers so theoretically powerful.
But qubits are maddeningly error-prone. The feeblest magnetic field or stray microwave pulse causes them to undergo “bit-flips” that switch their chances of being |0⟩ and |1⟩ relative to the other qubits, or “phase-flips” that invert the mathematical relationship between their two states. For quantum computers to work, scientists must find schemes for protecting information even when individual qubits get corrupted. What’s more, these schemes must detect and correct errors without directly measuring the qubits, since measurements collapse qubits’ coexisting possibilities into definite realities: plain old 0s or 1s that can’t sustain quantum computations.
In 1995, Shor followed his factoring algorithm with another stunner: proof that “quantum error-correcting codes” exist. The computer scientists Dorit Aharonov and Michael Ben-Or (and other researchers working independently) proved a year later that these codes could theoretically push error rates close to zero. “This was the central discovery in the ’90s that convinced people that scalable quantum computing should be possible at all,” said Scott Aaronson, a leading quantum computer scientist at the University of Texas — “that it is merely a staggering problem of engineering.”
From top: Peter Shor, Dorit Aharonov and Michael Ben-Or laid the foundation for quantum error correction and fault-tolerant quantum computing more than 20 years ago.
From left: Peter Shor, Dorit Aharonov and Michael Ben-Or laid the foundation for quantum error correction and fault-tolerant quantum computing more than 20 years ago.
Courtesy of Peter Shor; Courtesy of Dorit Aharonov; The Hebrew University of Jerusalem (Ben-Or)
Now, even as small quantum computers are materializing in labs around the world, useful ones that will outclass ordinary computers remain years or decades away. Far more efficient quantum error-correcting codes are needed to cope with the daunting error rates of real qubits. The effort to design better codes is “one of the major thrusts of the field,” Aaronson said, along with improving the hardware.
But in the dogged pursuit of these codes over the past quarter-century, a funny thing happened in 2014, when physicists found evidence of a deep connection between quantum error correction and the nature of space, time and gravity. In Albert Einstein’s general theory of relativity, gravity is defined as the fabric of space and time — or “space-time” — bending around massive objects. (A ball tossed into the air travels along a straight line through space-time, which itself bends back toward Earth.) But powerful as Einstein’s theory is, physicists believe gravity must have a deeper, quantum origin from which the semblance of a space-time fabric somehow emerges.
That year — 2014 — three young quantum gravity researchers came to an astonishing realization. They were working in physicists’ theoretical playground of choice: a toy universe called “anti-de Sitter space” that works like a hologram. The bendy fabric of space-time in the interior of the universe is a projection that emerges from entangled quantum particles living on its outer boundary. Ahmed Almheiri, Xi Dong and Daniel Harlow did calculations suggesting that this holographic “emergence” of space-time works just like a quantum error-correcting code. They conjectured in the Journal of High Energy Physics that space-time itself is a code — in anti-de Sitter (AdS) universes, at least. The paper has triggered a wave of activity in the quantum gravity community, and new quantum error-correcting codes have been discovered that capture more properties of space-time.
John Preskill, a theoretical physicist at the California Institute of Technology, says quantum error correction explains how space-time achieves its “intrinsic robustness,” despite being woven out of fragile quantum stuff. “We’re not walking on eggshells to make sure we don’t make the geometry fall apart,” Preskill said. “I think this connection with quantum error correction is the deepest explanation we have for why that’s the case.”
The language of quantum error correction is also starting to enable researchers to probe the mysteries of black holes: spherical regions in which space-time curves so steeply inward toward the center that not even light can escape. “Everything traces back to black holes,” said Almheiri, who is now at the Institute for Advanced Study in Princeton, New Jersey. These paradox-ridden places are where gravity reaches its zenith and Einstein’s general relativity theory fails. “There are some indications that if you understand which code space-time implements,” he said, “it might help us in understanding the black hole interior.”
As a bonus, researchers hope holographic space-time might also point the way to scalable quantum computing, fulfilling the long-ago vision of Shor and others. “Space-time is a lot smarter than us,” Almheiri said. “The kind of quantum error-correcting code which is implemented in these constructions is a very efficient code.”
From top: Ahmed Almheiri, Xi Dong and Daniel Harlow originated a powerful new idea that the fabric of space-time is a quantum error-correcting code.
From left: Ahmed Almheiri, Xi Dong and Daniel Harlow originated a powerful new idea that the fabric of space-time is a quantum error-correcting code.
Maryam Meshar (Almheiri); Courtesy of Xi Dong; Justin Knight (Harlow)
So, how do quantum error-correcting codes work? The trick to protecting information in jittery qubits is to store it not in individual qubits, but in patterns of entanglement among many.
As a simple example, consider the three-qubit code: It uses three “physical” qubits to protect a single “logical” qubit of information against bit-flips. (The code isn’t really useful for quantum error correction because it can’t protect against phase-flips, but it’s nonetheless instructive.) The |0⟩ state of the logical qubit corresponds to all three physical qubits being in their |0⟩ states, and the |1⟩ state corresponds to all three being |1⟩’s. The system is in a “superposition” of these states, designated |000⟩ + |111⟩. But say one of the qubits bit-flips. How do we detect and correct the error without directly measuring any of the qubits?
The qubits can be fed through two gates in a quantum circuit. One gate checks the “parity” of the first and second physical qubit — whether they’re the same or different — and the other gate checks the parity of the first and third. When there’s no error (meaning the qubits are in the state |000⟩ + |111⟩), the parity-measuring gates determine that both the first and second and the first and third qubits are always the same. However, if the first qubit accidentally bit-flips, producing the state |100⟩ + |011⟩, the gates detect a difference in both of the pairs. For a bit-flip of the second qubit, yielding |010⟩ + |101⟩, the parity-measuring gates detect that the first and second qubits are different and first and third are the same, and if the third qubit flips, the gates indicate: same, different. These unique outcomes reveal which corrective surgery, if any, needs to be performed — an operation that flips back the first, second or third physical qubit without collapsing the logical qubit. “Quantum error correction, to me, it’s like magic,” Almheiri said.
Lucy Reading-Ikkanda/Quanta Magazine
The best error-correcting codes can typically recover all of the encoded information from slightly more than half of your physical qubits, even if the rest are corrupted. This fact is what hinted to Almheiri, Dong and Harlow in 2014 that quantum error correction might be related to the way anti-de Sitter space-time arises from quantum entanglement.
It’s important to note that AdS space is different from the space-time geometry of our “de Sitter” universe. Our universe is infused with positive vacuum energy that causes it to expand without bound, while anti-de Sitter space has negative vacuum energy, which gives it the hyperbolic geometry of one of M.C. Escher’s Circle Limit designs. Escher’s tessellated creatures become smaller and smaller moving outward from the circle’s center, eventually vanishing at the perimeter; similarly, the spatial dimension radiating away from the center of AdS space gradually shrinks and eventually disappears, establishing the universe’s outer boundary. AdS space gained popularity among quantum gravity theorists in 1997 after the renowned physicist Juan Maldacena discovered that the bendy space-time fabric in its interior is “holographically dual” to a quantum theory of particles living on the lower-dimensional, gravity-free boundary.
The hyperbolic geometry in M.C. Escher’s 1959 woodcut, Circle Limit III, is also a feature of anti-de Sitter space.
In exploring how the duality works, as hundreds of physicists have in the past two decades, Almheiri and colleagues noticed that any point in the interior of AdS space could be constructed from slightly more than half of the boundary — just as in an optimal quantum error-correcting code.
In their paper conjecturing that holographic space-time and quantum error correction are one and the same, they described how even a simple code could be understood as a 2D hologram. It consists of three “qutrits” — particles that exist in any of three states — sitting at equidistant points around a circle. The entangled trio of qutrits encode one logical qutrit, corresponding to a single space-time point in the circle’s center. The code protects the point against the erasure of any of the three qutrits.
Of course, one point is not much of a universe. In 2015, Harlow, Preskill, Fernando Pastawski and Beni Yoshida found another holographic code, nicknamed the HaPPY code, that captures more properties of AdS space. The code tiles space in five-sided building blocks — “little Tinkertoys,” said Patrick Hayden of Stanford University, a leader in the research area. Each Tinkertoy represents a single space-time point. “These tiles would be playing the role of the fish in an Escher tiling,” Hayden said.
In the HaPPY code and other holographic error-correcting schemes that have been discovered, everything inside a region of the interior space-time called the “entanglement wedge” can be reconstructed from qubits on an adjacent region of the boundary. Overlapping regions on the boundary will have overlapping entanglement wedges, Hayden said, just as a logical qubit in a quantum computer is reproducible from many different subsets of physical qubits. “That’s where the error-correcting property comes in.”
“Quantum error correction gives us a more general way of thinking about geometry in this code language,” said Preskill, the Caltech physicist. The same language, he said, “ought to be applicable, in my opinion, to more general situations” — in particular, to a de Sitter universe like ours. But de Sitter space, lacking a spatial boundary, has so far proven much harder to understand as a hologram.
For now, researchers like Almheiri, Harlow and Hayden are sticking with AdS space, which shares many key properties with a de Sitter world but is simpler to study. Both space-time geometries abide by Einstein’s theory; they simply curve in different directions. Perhaps most importantly, both kinds of universes contain black holes. “The most fundamental property of gravity is that there are black holes,” said Harlow, who is now an assistant professor of physics at the Massachusetts Institute of Technology. “That’s what makes gravity different from all the other forces. That’s why quantum gravity is hard.”
The language of quantum error correction has provided a new way of describing black holes. The presence of a black hole is defined by “the breakdown of correctability,” Hayden said: “When there are so many errors that you can no longer keep track of what’s going on in the bulk [space-time] anymore, you get a black hole. It’s like a sink for your ignorance.”
Ignorance invariably abounds when it comes to black hole interiors. Stephen Hawking’s 1974 epiphany that black holes radiate heat, and thus eventually evaporate away, triggered the infamous “black hole information paradox,” which asks what happens to all the information that black holes swallow. Physicists need a quantum theory of gravity to understand how things that fall in black holes also get out. The issue may relate to cosmology and the birth of the universe, since expansion out of a Big Bang singularity is much like gravitational collapse into a black hole in reverse.
AdS space simplifies the information question. Since the boundary of an AdS universe is holographically dual to everything in it — black holes and all — the information that falls into a black hole is guaranteed never to be lost; it’s always holographically encoded on the universe’s boundary. Calculations suggest that to reconstruct information about a black hole’s interior from qubits on the boundary, you need access to entangled qubits throughout roughly three-quarters of the boundary. “Slightly more than half is not sufficient anymore,” Almheiri said. He added that the need for three-quarters seems to say something important about quantum gravity, but why that fraction comes up “is still an open question.”
In Almheiri’s first claim to fame in 2012, the tall, thin Emirati physicist and three collaborators deepened the information paradox. Their reasoning suggested that information might be prevented from ever falling into a black hole in the first place, by a “firewall” at the black hole’s event horizon.
Like most physicists, Almheiri doesn’t really believe black hole firewalls exist, but finding the way around them has proved difficult. Now, he thinks quantum error correction is what stops firewalls from forming, by protecting information even as it crosses black hole horizons. In his latest, solo work, which appeared in October, he reported that quantum error correction is “essential for maintaining the smoothness of space-time at the horizon” of a two-mouthed black hole, called a wormhole. He speculates that quantum error correction, as well as preventing firewalls, is also how qubits escape a black hole after falling in, through strands of entanglement between the inside and outside that are themselves like miniature wormholes. This would resolve Hawking’s paradox.
This year, the Department of Defense is funding research into holographic space-time, at least partly in case advances there might spin off more efficient error-correcting codes for quantum computers.
On the physics side, it remains to be seen whether de Sitter universes like ours can be described holographically, in terms of qubits and codes. “The whole connection is known for a world that is manifestly not our world,” Aaronson said. In a paper last summer, Dong, who is now at the University of California, Santa Barbara, and his co-authors Eva Silverstein and Gonzalo Torroba took a step in the de Sitter direction, with an attempt at a primitive holographic description. Researchers are still studying that particular proposal, but Preskill thinks the language of quantum error correction will ultimately carry over to actual space-time.
“It’s really entanglement which is holding the space together,” he said. “If you want to weave space-time together out of little pieces, you have to entangle them in the right way. And the right way is to build a quantum error-correcting code.”
This article was reprinted on Wired.com.
