Computational Complexity And The Nature Of Reality
Physicists have spent the last 100 years attempting to reconcile Einstein’s theory of general relativity, which describes the large-scale geometry of spacetime, with quantum mechanics, which deals with the small-scale behavior of particles. It’s been slow going for a century, but now, suddenly, things are happening.
First, there’s ER=EPR. More idea than equation, it’s the brainchild of physicists Juan Maldacena and Leonard Susskind. On the left-hand side is an Einstein-Rosen bridge, a kind of geometric tunnel connecting distant points in space, otherwise known as a wormhole. On the right are Einstein, Rosen, and Podolsky, the three physicists who first pointed out the spooky nature of quantum entanglement, wherein the quantum state of two remote particles straddles the distance between them. Then there’s that equals sign in the middle. Boldly it declares: spacetime geometry and the links between entangled particles are two descriptions of the same physical situation. ER = EPR appears brief and unassuming, but it’s a daring step toward uniting general relativity and quantum mechanics—with radical implications.
Intuitively, the connection is clear. Both wormholes and entanglement flout the constraints of space. They’re shortcuts. One can enter a wormhole on one side of the universe and emerge from it on the other without having to traverse the space in between. Likewise, measuring one particle will instantaneously determine the state of its entangled partner, even if the two are separated by galaxies.
The connection becomes more intriguing when viewed in terms of information. For maximally entangled particles, the information they carry resides simultaneously in both particles but in neither alone; informationally speaking, no space separates one from the other. For particles that are slightly less than maximally entangled, we might say there is some space between them. As particles become less and less entangled, information becomes more and more localized, words like “here” and “there” begin to apply and ordinary space emerges.
One hundred years ago, Einstein gave us a new way to think about space—not as the static backdrop of the world, but as a dynamic ingredient. Now, ER=EPR gives us yet a newer interpretation: what we call space is nothing more than a way to keep track of quantum information. And what about time? Time, physicists are beginning to suspect, may be a barometer of computational complexity.
Computational complexity measures how difficult it is to carry out a given computation—how many logical steps it takes, or how the resources needed to solve a problem scale with its size. Historically, it’s not something physicists thought much about. Computational complexity was a matter of engineering—nothing profound. But all that has changed, thanks to what’s known as the black hole firewall paradox—an infuriating dilemma that has theoretical physicists pulling out their hair.
As a black hole radiates away its mass, all the information that ever fell in must emanate back out into the universe, scrambled amongst the Hawking radiation; if it doesn’t, quantum mechanics is violated. The very same information must reside deep in the black hole’s interior; if it doesn’t, general relativity is violated. And the laws of physics decree: information can’t be duplicated. The firewall paradox arises when we consider an observer, Alice, who decodes the information scrambled amongst the Hawking radiation, then jumps into the black hole where she will find, by various accounts, an illegal information clone or an inexplicable wall of fire. Either way, it’s not good.
But Alice’s fate recently took a turn when two physicists, Patrick Hayden and Daniel Harlow, wondered how long it would take her to decode the information in the radiation. Applying a computational complexity analysis, they discovered that the decoding time would rise exponentially with each additional particle of radiation. In other words, by the time Alice decodes the information, the black hole will have long ago evaporated and vanished, taking any firewalls or violations of physics with it. Computational complexity allows general relativity and quantum mechanics to peacefully coexist.
Hayden and Harlow’s work connects physics and computer science in a totally unprecedented way. Physicists have long speculated that information plays a fundamental role in physics. It’s an idea that dates back to Konrad Zuse, the German engineer who built the world’s first programmable electronic computer in his parent’s living room in 1938, and the first universal Turing machine three years later. In 1967, Zuse wrote a book called Calculating Space, in which he argued that the universe itself is a giant digital computer. In the 1970s, the physicist John Wheeler began advocating for “it from bit”—the notion that the physical, material world is, at bottom, made of information. Wheeler’s influence drove the burgeoning field of quantum information theory and led to quantum computing, cryptography and teleportation. But the idea that computational complexity might not only describe the laws of physics, but actually uphold the laws of physics, is entirely new.
It’s odd, on glance, that something as practical as resource constraints could tell us anything deep about the nature of reality. And yet, in quantum mechanics and relativity, such seemingly practical issues turn out to be equally fundamental. Einstein deduced the nature of spacetime by placing constraints on what an observer can see. Noticing that we can’t measure simultaneity at a distance gave him the theory of special relativity; realizing that we can’t tell the difference between acceleration and gravity gave him the curvature of spacetime. Likewise, when the founders of quantum mechanics realized that it is impossible to accurately measure position and momentum, or time and energy, simultaneously, the strange features of the quantum world came to light. That such constraints were at the heart of both theories led thinkers such Arthur Stanley Eddington to suggest that at its deepest roots, physics is epistemology. The new computational complexity results push further in that direction.
So that’s the news: a profound connection between information, computational complexity and spacetime geometry has been uncovered. It’s early to say where these clues will lead, but it’s clear now that physicists, computer scientists and philosophers will all bring something to bear to illuminate the hidden nature of reality.
