The Complexity Conundrum

Let’s say that you have a black hole, says Adam Brown, a physicist at Stanford University, in Palo Alto, California. Let’s also say that you’ve ringed it with the ultimate sensor array, including enough telescopes, radio dishes, gravitational wave detectors, and the like to measure every quantum of energy emerging from the system. And let’s say that you feed the data streams from all those sensors into an incredibly powerful quantum computer that converts them into a perfect simulation of the black hole.

Is the result just a mathematical description, Brown wonders? Or is it a new black hole, as real as the first?

If this is the kind of question you might expect to hear in a philosophy class, that’s no accident: Brown earned an undergraduate degree in that subject from Oxford before becoming a physicist. But the question fits right in at FQXi, which has given Brown a $37,500 grant to explore it—mainly by relating the fundamental physics of gravity to the notion of quantum computational complexity, which counts how many steps a quantum computer has to take to solve a given problem.

Information Paradox

Brown’s puzzle goes all the way back to the black hole information paradox, a conundrum discovered by Cambridge University physicist Stephen Hawking in the 1970s, when he, too, was contemplating black holes. Any such object is governed by Einstein’s theory of gravity, also known as general relativity. And general relativity tells us that certain doom awaits any object unfortunate enough to fall within a certain distance known as the event horizon, where the black hole’s gravity becomes so strong that not even light can escape. Once inside, there is no turning back: the object will inexorably fall to the ’singularity’ at the black hole’s center and be crushed to infinite density.

Now wait a few zillion years, said Hawking. As he himself had discovered in 1974, quantum fluctuations in the space around a black hole will cause it to radiate photons and other particles as if it were hot. His argument is based on a standard result from quantum theory, which holds that these fluctuations are everywhere, and keep every patch of ’empty’ space aboil with particle-antiparticle pairs. Ordinarily, these particles recombine and vanish almost as soon as they appear, and have no effect. But in the space near a black hole, Hawking had pointed out, one of the particles can sometimes fall through the event horizon and be lost, forcing the other particle to fly off to infinity as radiation.

Each of these emerging quanta will carry off an infinitesimal bit of the black hole’s energy, decreasing its mass. Eventually the black hole will evaporate, leaving nothing to mark its existence but the expanding cloud of radiation.

And therein lay the paradox, said Hawking: the objects falling into the black hole over the eons carried all kinds of information about their structure and composition. So where did that information go? If you assumed that the black hole’s life and death are governed by general relativity, then the information is gone for good—crushed into the singularity along with everything else that ever fell through the event horizon.

But you got a contradictory answer if you assumed that the formation and evaporation of a black hole is governed by quantum physics. Because information can neither be created nor destroyed in a quantum process, just transformed, it has to wind up in the radiation; there’s nothing else left. Yet the mathematics of Hawking radiation is very clear on this point: the quantum state of any one radiation particle is random, and carries no useful information.

Physicists have spent the past four decades trying to resolve this contradiction. By the mid-1990s, Brown’s senior colleague at Stanford, Leonard Susskind, and others came up with an apparent resolution of the paradox. Susskind realized that even though individual Hawking particles must have random quantum states, the quantum state of all the radiation particles as a whole can contain subtle correlations known as ’entanglement’—meaning that a measurement made on one particle will immediately influence the quantum state of its partners. And that entanglement, Susskind argued, is what might carry the missing information.

Monogamy of Entanglement

This quickly became the dominant view of how to resolve the black hole information paradox. Even Hawking was convinced. But in 2012, four physicists in California, widely referred to by their initials, AMPS (for Ahmed Almheiri, Donald Marolf, Joe Polchinski, and James Sully), published a powerful challenge. In Susskind’s scenario, the AMPS team pointed out, black hole information is preserved only if each radiation particle is entangled with all the radiation that emerged before it. But each such radiation particle is also supposed to be entangled with its twin that fell into the event horizon. Both those statements cannot be true, said the AMPS team: an iron rule of quantum mechanics known as ’the monogamy of entanglement’ says that no particle can be entangled with more than one thing at a time.

Something had to give, and AMPS argued that it had to be the radiation particles’ twins. Einstein’s general relativity traditionally says that the event horizon is just an ordinary patch of space, and so—according to his theory—the infalling twin would pass through unperturbed en route to the singularity. But AMPS proposed a dramatically different scenario, if quantum rules hold: the infalling twin would be destroyed by an unimaginable blast of energy at the horizon, which would be generated as its entanglement to the outgoing radiation was severed. "In effect, there is no inside" to the horizon, says Brown. Everything just burns up at a firewall located at the horizon. The suggestion preserved quantum rules, but at the expense of general relativity’s predictions of a featureless event horizon.

This ’firewall paradox’ was a modern—"more vivid"—recasting of the information paradox, says Brown. It roiled the community of theoretical physicists, who were faced with sacrificing a key tenet of general relativity if they wanted to maintain that quantum laws hold everywhere. And Brown, who was just then moving to Stanford to start a postdoctoral appointment, found himself in the thick of it.

For him and many others, the most interesting take on the firewall paradox came in a 2013 paper by Daniel Harlow, now at MIT, and Stanford’s Patrick Hayden. Harlow and Hayden couldn’t definitively rule out the possibility that firewalls are real—and that, in turn, general relativity is wrong. But they were able to offer some reassurance to those physicists who prefer to hold on to general relativity anyway: they showed that it is logically consistent to believe there is no firewall at the horizon, without having to run into the quantum paradox raised by AMPS.

Jumping into the Hole

Harlow and Hayden’s argument hinges on what a real person could ever actually measure. The two physicists imagined an insanely curious observer—’Alice’—who is determined to see for herself whether a firewall really exists at the black hole’s edge, or whether the monogamy of entanglement breaks down there. Alice’s plan is to station herself outside the black hole while she identifies some of the emerging Hawking particles and measures whether they are entangled. Then she will jump into the hole to track their infalling twins. Assuming that no firewall exists, she will then be able to monitor if the twins remain entangled with their outgoing Hawking partners, as she drifts alongside them toward the black hole’s singularity. (If the black hole is big enough, Alice could have weeks or even years to make her measurements before hitting the singularity.) Of course, if the firewall does exist, Alice will get her answer in a more gruesome way—when she is burned alive at the horizon.

Although that is a fine plan in theory, Harlow and Hayden found that things get stickier in practice. In the pre-jump phase, they pointed out, Alice can’t confirm that the outgoing Hawking particles are entangled until she has captured roughly half of them. And even then, she would have to decode her data with a quantum computer—a step that is a show-stopper all by itself. Harlow and Hayden showed that any such decoding process would have an inconceivably vast ’computational complexity,’ meaning that it would require a horrendous number of computational steps to complete—something like e¹⁰⁵⁰. The black hole would evaporate long before Alice was ready to jump in.

"It’s like pouring a cup of coffee in the ocean, then coming back in ten years to try to extract the coffee molecules," says Brown—except that that would be exponentially easier than Alice’s task.

In short, says Brown, "there’s no need for there to be a firewall, because the paradoxical experiment from which the firewall is meant to save you cannot actually be enacted without seriously changing the system under study."

For Susskind, the Harlow-Hayden analysis was something genuinely new. "You talk to computer scientists and they go, ’Complexity—of course’," he says. "But these ideas were very unfamiliar to physicists." Likewise for Juan Maldacena, a physicist at the Institute for Advanced Study (IAS) in Princeton, New Jersey: "They showed that we have to think about quantum complexity when we think about black hole information."

Not everyone thinks that the Harlow-Hayden argument is watertight, however. "The idea that practical limits on computation mean that you can’t discuss certain things—I’m not sure I like it," says Douglas Stanford, also at IAS. "You can’t ever be sure that the limits are real, and won’t be shattered as soon as you find a cleverer algorithm," he notes. Maybe physics should stick to asking what is possible, not what is hard to compute.

Fair enough, says Brown: if you believe that there is a firewall, there’s no need to follow the Harlow-Hayden line of argument at all. "But I don’t want to believe in firewalls, because they bring a host of problems of their own," he says. So with his FQXi grant, he is trying to tie up the loose ends in the Harlow-Hayden argument and "find a reason why it’s consistent not to believe in a firewall."

Uncertainty Principle

Brown’s idea is to reframe the Harlow-Hayden argument as a statement about the nature of physical law. In physics, he says, the traditional approach is that nature doesn’t care whether computations are hard: processes unfold anyway. "But I think the right model to compare it to is quantum mechanics in the early 20th century, when the moral was that you couldn’t measure both position and momentum at the same time." Physicists had to accept that this ’uncertainty principle’ wasn’t just a practical limitation of their measuring apparatus, but a fundamental limitation on the kinds of questions they could ask experimentally.

By analogy, says Brown, "the moral for quantum gravity in the 21st century will be that nature is not required to give a well-posed answer to exponentially complicated questions."

That brings us back to Brown’s thought experiment about whether a clever enough simulation of a black hole should be thought of as being as real as the entity it is modeling. In the case of Alice, he explains, she would have to do an exponentially complicated simulation of all the possible things she could see once she jumped into the black hole. But if she could do that, rendering every quantum detail with sufficiently high fidelity, says Brown, then all the virtual Alices and black holes that live inside her quantum computer would be as real as she is. And yet the life course of each would be different: "You would have situations where Alice sees a firewall, but also where she doesn’t see a firewall," he says—"which renders the actual existence of the firewall meaningless."