Black holes, paradoxes, and computational complexity

(Thanks so much to Scott Aaronson for giving me many pointers, insights, explanations, and corrections that greatly improved this post. As I’m a beginner to physics, the standard caveat holds doubly here: Scott is by no means responsible to any of my remaining technical mistakes and philosophical misconceptions.)

One of the interesting features of physics is the prevalence of “thought experiments”, including Maxwell’s demon, Einstein’s Train, Schrödinger’s cat, and many more. One could think that these experiments are merely “verbal fluff” which obscures the “real math” but there is a reason that physicists return time and again to these types of mental exercises. In a nutshell, this is because while physicists use math to model reality, the mathematical model is not equal to reality.

For example, in the early days of quantum mechanics, several calculations of energy shifts seemed to give out infinite numbers. While initially this was viewed as a sign that something is deeply wrong with quantum mechanics, ultimately it turned out that these infinities canceled each other, as long as you only tried to compute observable quantities. One lesson that physicists drew from this is that while such mathematical inconsistencies may (and in this case quite possibly do) indicate some issue with a theory, they are not a reason to discard it. It is OK if a theory involves mathematical steps that do not make sense, as long as this does not lead to an observable paradox: i.e., an actual “thought experiment” with a nonsensical outcome.

A priori, this seems rather weird. An outsider impression of the enterprise of physics is that it is all about explaining the behavior of larger systems in terms of smaller parts. We explain materials by molecules, molecules by atoms, and atoms by elementary particles. Every term in our mathematical model is supposed to correspond to something “real” in the world.

However, with modern physics, and particular quantum mechanics, this connection breaks down. In quantum mechanics we model the state of the world using a vector (or “wave function”) but the destructiveness of quantum measurements tells us that we can never know all the coordinates of this vector. (This is also related to the so called “uncertainty principle”.) While physicists and philosophers can debate whether these wave functions “really exist”, their existence is not the reason why quantum mechanics is so successful. It is successful because these wave functions yield a mathematically simple model to predict observations. Hence we have moved from trying to explain bigger physical systems in terms of smaller physical systems to trying to explain complicated observations in terms of simpler mathematical models. (Indeed the focus has moved from “things” such as particles to concepts such as forces and symmetries as the most fundamental notions.) These simpler models do not necessarily correspond to any real physical entities that we’d ever be able to observe. Hence such models can in principle contain weird things such as infinite quantities, as long as these don’t mess up our predictions for actual observations.

Nevertheless, there are still real issues in physics that people have not been able to settle. In particular the so called “standard model” uses quantum mechanics to explain the strong force, the weak force, and the electromagnetic force, which dominate over short (i.e., subatomic) distances, but it does not incorporate the force of gravity. Gravity is explained by the theory of general relativity which is inconsistent with quantum mechanics but is predictive for phenomena over larger distances.

By and large physicists believe that quantum mechanics will form the basis for a unified theory, that will involve incorporating gravity into it by putting general relativity on quantum mechanical foundations. One of the most promising approaches in this direction is known as the AdS/CFT correspodence of Maldacena, which we describe briefly below.
Alas, in 2012, Almheiri, Marolf, Polchinski, and Sully (AMPS) gave a description of a mental experiment, known as a the “firewall paradox” that showed a significant issue with any quantum-mechanical description of gravity, including the Ads/CFT correspondence. Harlow and Hayden (see also chapter 6 of Aaronson’s notes and this overview of Susskind) proposed a way to resolve this paradox using computational complexity.

In this post I will briefly discuss these issues. Hopefully someone in Tselil’s and my upcoming seminar will present this in more detail and also write a blog post about it.

The bulk/boundary correspondence

Edwin Abbott’s 1884 novel “Flatland”, describes a world in which people live in only two dimensions. At some point a sphere visits this world, and opens the eye of one of its inhabitants (the narrator, which is a square) to the fact its two-dimensional world was merely an illusion and the “real world” actually has more dimensions.


Cover of first edition of “Flatland”. Image from Wikipedia, *EC85 Ab264 884f, Houghton Library, Harvard University.


However, modern physics suggest that things might be the other way around: we might actually be living in flatland ourselves. That is, it might be that the true description of our world has one less spatial dimension than what we perceive. For example, though we think we live in three dimensions, perhaps we are merely shadows (or a “hologram”) of a two dimensional description of the world. One can ask how could this be? After all, if our world is “really” two dimensional, what happens when I climb the stairs in my house? The idea is that the geometry of the two-dimensional world is radically different, but it contains all the information that would allow to decode the state of our three dimensional world. You can imagine that when I climb the stairs in my house, my flatland analog goes from the first floor to the second floor in (some encoding of) the two-dimensional blueprint of my house. (Perhaps this lower-dimensional representation is the reason the Wachowskis called their movie “The Matrix” as opposed to “The Tensor”?)


The main idea is that in this “flat” description, gravity does not really exist and physics has a pure quantum mechanical description which is scale free in the sense that the theory is the same independently of distance. Gravity and our spacetime gemoetry emerge in our world via the projection from this lower dimensional space. (This projection is supposed to give rise to some kind of string theory.) As far as I can tell, at the moment physicists can only perform this projection (and even this at a rather heuristic level) under the assumption that our universe is contracting or in physics terminology an “anti de-Sitter (AdS) space”. This is the assumption that the geometry of the universe is hyperbolic and hence one can envision spacetime as being bounded in some finite area of space: some kind of a d+1 dimensional cylinder that has a d-dimensional boundary. The idea is that all the information on what’s going on in the inside or bulk of the cylinder is encoded in this boundary. One caveat is that our physical universe is actually expanding rather than contracting, but as the theory is hard enough to work out for a contracting space, at the moment they sensibly focus on this more tractable setting. Since the quantum mechanical theory on the boundary is scale free (and also rotation invariant) it is known as a Conformal Field Theory (CFT). Thus this one to one mapping of the boundary and the bulk is also known as the “AdS/CFT correspondence”.

The firewall paradox

If it is possible to carry over this description, in terms of information it would be possible to describe the universe in purely quantum mechanical terms. One can imagine that the universe starts at some quantum state |x_0 \rangle, and at each step in time progresses to the state |x_{i+1} \rangle = U|x_i \rangle where U is some unitary transformation.

In particular this means that information is never lost. However, black holes pose a conundrum to this view since they seem to swallow all information that enters them. Recall that the “escape velocity” of earth – the speed needed to escape the gravitational field and go to space – is about 25,000 mph or Mach 33. In a black hole the “escape velocity” is the speed of light which means that nothing, not even light, can escape it. More specifically, there is a certain region in spacetime which corresponds to the event horizon of a black hole. Once you are in this event horizon then you have passed the point of no return since even if you travel in the speed of light, you will not be able to escape. Though it might take a very long time, eventually you will perish in the black hole’s so called “singularity”.


New Yorker magazine, August 27, 2018


Entering the event horizon should not feel particularly special (a condition physicists colorfully refer to as “no drama”). Indeed, as far as I know, it is theoretically possible that 10 years from now a black hole would be created in our solar system with a radius larger than 100 light years. If this future event will happen, this means that we are already in a black hole event horizon even though we don’t know it.

The above seems to mean that information that enters the black hole is irrevocably lost, contradicting unitarity. However, physicists now believe that through a phenomenon known as Hawking radiation black holes might actually emit the information that was contained in them. That is, if the n qubits that enter the event horizon are in the state |x\rangle then (up to a unitary tranformation) the qubits that are emitted in the radiation would be in the state |x \rangle as well, and hence no information is lost. Indeed, Hawking himself conceded the bet he made with Preskill on information loss.
Nevertheless, there is one fly in this ointment. If we drop an n qubit state |x\rangle in this black hole, then they are eventually radiated (in the same state, up to an invertible transformation), but the original n qubits never come out. (It is a black hole after all.) Since we now have two copies of these qubits (one inside the black hole and one outside it), this seems to violate the famous “no cloning principle” of quantum mechanics which says that you can’t copy a qubit. Luckily however, this seemed to be one more of those cases where it is an issue with the math that could never effect an actual observer. The reason is that an observer inside the black hole event horizon can never come out, while an observer outside can never peer inside. Thus, even if the no cloning principle is violated in our mathematical model of the whole universe, no such violation would have been seen by either an outside or an inside observer. In fact, even if Alice – a brave observer outside the event horizon – obtained the state |x\rangle of the Hawking radiation and then jumped with it into the event horizon so that she can see a violation of the no-cloning principle then it wouldn’t work. The reason is that by the time all the n qubits are radiated, the black hole fully evaporates and inside the black hole the original qubits have already entered the singularity. Hence Alice would not be able to “catch the black hole in the act” of cloning qubits.
What AMPS noticed is that a more sophisticated (yet equally brave) observer could actually obtain a violation of quantum mechanics. The idea is the following. Alice will wait until almost all (say 99 percent) of the black hole evaporated, which means that at this point she can observe 0.99n of the qubits of the Hawking radiation |R \rangle, while there are still about 0.01n qubits inside the event horizon that have not yet reached the singularity. So far, this does not seem to be any violation of the no cloning principle, but it turns out that entanglement (which you can think of as the quantum analog of mutual information) plays a subtle role. Specifically, for information to be preserved the radiation will be in a highly entangled state, which means that in particular if we look at the qubit |A \rangle that has just radiated from the event horizon then it will be highly entangled with the 0.99n qubits |R \rangle we observed before.

On the other hand, from the continuity of spacetime, if we look at a qubit |B\rangle that is just adjacent to |A \rangle but inside the event horizon then it will be highly entangled with |A \rangle as well. For our classical intuition, this seems to be fine: a \{0,1\}-valued random variable A could have large (say at least 0.9) mutual information with two distinct random variables R and B. But quantum entanglement behaves differently: it satisfies a notion known as monogamy of entanglement, which implies that the sum of entanglement of a qubit |A \rangle with two disjoint registers can be at most one. (Monogamy of entangelement is actually equivalent to the no cloning principle, see for example slide 14 here.)

Specifically, Alice could use a unitary transformation to “distill” from |R\rangle a qubit |C\rangle that is highly entangled with |A\rangle and then jump with |A\rangle and |C\rangle into the event horizon to observe there a triple of qubits (|A\rangle, |B\rangle, |C \rangle) which violates the monogamy of entanglement.

One potential solution to the AMPS paradox is to drop the assumption that spacetime is continuous at the event horizon. This would mean that there is a huge energy barrier (i.e., a “firewall”) at the event horizon. Alas, a huge wall of fire is as close as one can get to the definition of “drama” without involving Omarose Manigault Newman.

The “firewall paradox” is a matter of great debate among physicists. (For example after the AMPS paper came out, a “rapid response workshop” was organized for people to suggest possible solutions.) As mentioned above, Daniel Harlow and Patrick Hayden suggested a fascinating way to resolve this paradox. They observed that to actually run this experiment, Alice would have to apply a certain “entanglement distillation” unitary D to the 0.99n qubits of the Hawking radiation. However, under reasonable complexity assumptions, computing D would require an exponential number of quantum gates!. This means that by the time Alice is done with the computation, the black hole is likely to completely evaporate, and hence there would be nothing left to jump into!


The above is by no means the last word of this story. Other approaches for resolving this paradox have been put forward, as well as ways to poke holes in the Harlow-Hayden resolution. Nor is it the only appearance of complexity in the AdS/CFT correspondence or quantum gravity at large. Indeed, the whole approach places much more emphasis on the information content of the world as opposed to the more traditional view of spacetime as the fundamental “canvas” for our universe. Hence information and computation play a key role in understanding how our spacetime can emerge from the conformal picture.


In the fall seminar, we will learn more about these issues, and will report here as we do so.

16 thoughts on “Black holes, paradoxes, and computational complexity

  1. This is a very nice post, Boaz, and it is especially useful to put side by side the “old” no cloning paradox and newer AMP paradox. The analogy with the old version helps clarifying why we need to distill C and move A and B beyond the horizon to get a paradox, and hence the relevance of Harlow and Hayden proposed solution.

    One way (perhaps) to look at the situation is the following. After the black hole vaporized completely we have n+m qubits describing a Hilbert space H. When we describe the unitary evolution and the state of the combined world we realize that with this description when the black hole existed we had on H a structure of two non interacting quantum computers. Moving from the computational basis of the black hole QC to the computational basis of the tensor power structure on H represents a random unitary operator (which is out of reach for quantum computers).

  2. A small critique on an ambitious article. Instead of

    “Perhaps this lower-dimensional representation is the reason the Wachowski brothers called their movie “The Matrix” as opposed to “The Tensor”?”

    (Which I certainly think is false as stated.) I might have phrased it as

    “Perhaps the Wachowski brothers, by titling their movie The Matrix as opposed to The Tensor, stumbled upon the truth?”

    You might also find it more appropriate to refer to them as “the Wachowskis”, since they have change their genders.

      1. P.s. the joke does have an educational goal, in the sense that the focus in this lower dimensional representation is on *encoding* the information in our observed space-time just like the memory of a computer would encode it if we were living in a simulation.The fact that we could run a simulation of k dimensional space using a computer with memory that is arranged in some d<k dimensions shows why such a lower dimensional embedding is not immediately absurd.

  3. Very interesting and educational post. One thing confused me and I wonder if you could elaborate. You write

    If we drop an n qubit state |x\rangle in this black hole, then they are eventually radiated (in the same state, up to an invertible transformation), but the original n qubits never come out.

    What s the meaning of “they” in this sentence? It is not the “original” n cubits but the word seems to refer to the state that went in?

    1. From the point of view of an outside observer it would be equivalent to the case that these are the original qubits transformed in some way. However the mechanism of the Hawking radiation is that they are not the same objects (since nothing can leave the black hole). Maybe however the model is that the state of the radiated qubits is supposed to be some unitary (and hence in particular invertible) transformation of the ingoing qubits which means that no information was lost.

  4. Like the post but I’d nitpick a little about the idea that there has been some shift from explaining physical systems in terms of physical components to mathematical models.

    I mean is there some operational sense in which atoms differ from wavefunctions in terms of our observational practice? In the case of atoms their supposed realness is merely deduced from their usefulness in making observational predictions about the world and wavefunctions and other aspects of modern physics are no different in that regard. Operationally, it seems the only difference is that the atomic model doesn’t seem highly weird (i.e. divorced from our daily experience of the world) while the quantum model does. But if this is really all there is to the distinction why dress up the well known fact about qm weirdness in these terms.

    On the other hand if you really meant to express some deep, non-operational, metaphysical claim about the nature of reality then you really ought to specify the metaphysical principles that render atoms obviously ‘real’ but raise doubts about wavefunctions as well as specifying what sense of real you even mean. I mean such claims depend critically on one’s metaphysical assumptions. For instance, if one is an idealist (ultimately the only thing that’s ‘real’ is conscious experience and the external world is merely a certain kind of regularity in those experiences) then there is absolutely no difference at all between explaining how gasses and liquids work in terms of atoms and explaining how subatomic particles work in terms of wavefunctions. In contrast, others might even take issue with the coherence of such a distinction between real aspects of the world and mere mathematical models.

    1. Thanks Peter. I was talking about the enterprise of physics as a science and human activity rather than trying to make an ontological statement about wavefunctions.

      I was referring to the following observations about physics, which as far as I know are true:

      1) Wavefunctions are the standard model for states of systems in quantum mechanics as taught in undergraduate courses and used in physics research.

      2) There is no universal agreement among physicists if wavefunctions “really exist” or not. Wavefunction realism is one interpretation of quantum mechanics but there are other interpretations as well.

      3) The issue of interpretation is largely considered a matter for philosophy and not for physics. The reason that wavefunctions are widely used and successful is because they are a clean mathematical model to predict observations. You don’t have to believe they exist to do that, and to a large extent physicists don’t care.

      There are of course important reasons (corresponding to both “quantum weirdness” and actual experiments with atoms) why physicists don’t normallly talk about the interpretation of atoms and debate whether they really exist.

      But what I find interesting is that by essentially deciding that the interpretation question is irrelevant, physics implicitly changed its goal. (Or perhaps physicists realized that their goal all along was to find mathematical models to predict observations, rather than to find mathematical models that have a direct correspondence with reality.)

      1. p.s. Scott Aaronson has a very nice discussion on various interpretations of quantum mechanics here:

        once again, I didn’t try to take a side in this debate, but just to point out that the debate exists, and the fact of its existence shows a shift in the value-system of physics. (Moreover, arguably the majority of working physicists implicitly take the SUAC side of it, which says that such questions are a topic for blog posts or pub discussion over drinks, but they are not part of the main working agenda.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s