Quantum computation vs. black-hole firewalls

The source, passage by passage

1. u1 Abstract
2. u2 In this paper we discuss quantum computational restrictions on the types of thought experiments recently used by Almheiri, Marolf, Polchinski, and Sully to argue against the smoothness of black hole horizons. We argue that the quantum computations required to do these experiments would take a time which is exponential in the entropy of the black hole under study, and we show that for a wide variety of black holes this prevents the experiments from being done. We interpret our results as motivating a broader type of nonlocality than is usually considered in the context of black hole thought experiments, and claim that once this type of nonlocality is allowed there may be no need for firewalls. Our results do not threaten the unitarity of of black hole evaporation or the ability of advanced civilizations to test it.
3. u3 1 Introduction
4. u4 The recently proposed firewall phenomenon [1] has dramatically emphasized the extent to which black holes remain interesting and mysterious in quantum gravity. Using “reasonable” assumptions about the structure of the quantum theory of black holes, the authors of [1], henceforth referred to as AMPS, have argued that unitarity of black hole evaporation, along with some limited form of locality, is inconsistent with a smooth horizon for an observer falling into an ‘‘old’’ black hole.1 There has been significant discussion of this claim in the literature, but in our view none of the followup work so far has decisively challenged the original argument.
5. u5 We will review the AMPS argument in section 2 below, but a key point in motivating their setup is a claim that an infalling observer is able to extract information from the Hawking radiation of a black hole prior to falling in.2 The model black hole of Hayden and Preskill [3], also partially reviewed below, suggests that this should be possible provided that the observer is able to perform a sophisticated nonlocal measurement on the Hawking radiation that has come out so far. In this paper we will argue using methods from the theory of quantum computation that this measurement can almost certainly not be done fast enough and thus that the AMPS experiment is not operationally realizable even in principle.
6. u6 As a simple example, consider a Schwarzschild black hole in $3+1$ dimensions. Its entropy is proportional to $M^{2}$ in Planck units, and it evaporates in a time proportional to $M^{3}$ . A would-be AMPS experimentalist thus has to extract information from $n\sim M^{2}$ bits of Hawking radiation in a time $T\sim n^{3/2}$ to be able to jump in before the black hole evaporates. From a computer science point of view this is very special: the decoding needs to be accomplished in a time that scales as a low-order polynomial in $n$ . In order to get at the information our experimentalist would need to apply a unitary transformation to the Hawking radiation which ‘‘unscrambles’’ the desired information by putting it into an easily accessible subfactor of the Hilbert space.3 As we will review below in section 3.2, applying a generic unitary transformation to an $n$ -bit Hilbert space requires time that is exponential in $n$ . Only very special unitary transformations can be implemented faster, and in this paper we will argue that the decoding operation relevant to AMPS is unlikely to be special in this way. In fact we conjecture, but cannot rigorously prove, that the decoding time for Hawking radiation will in general be exponential in the entropy of the remaining black hole.4
7. u7 In light of our discussion, a firewall enthusiast might nonetheless argue that even though the decoding cannot be done the information is still “there”. It has been clear for some time however that operational constraints are important in understanding the structure of the Hilbert space used in describing black hole evaporation, and we view our results in this context. More concretely the real issue at stake is for which types of situations we should trust effective field theory (EFT). Traditionally EFT was viewed as holding away from local regions with high energy density or spacetime curvature. If this were the only way in which EFT could break down however, then we would seem to be led inexorably to information loss [4]. If we wish to maintain belief in unitarity, as AdS/CFT strongly suggests we should, then there must be a more broad set of criteria for when EFT is not be valid. It is not trivial however to find such criteria which do not flagrantly violate the extraordinary level to which EFT has been experimentally tested. Careful analysis of thought experiments near black holes in the mid 1990’s [5, 6, 7] led to an additional criterion involving causality:
8. u8 Two spacelike-separated low-energy observables which cannot both be causally accessed by some single observer do not need to be realized even approximately as distinct and commuting operators on the same Hilbert space.
9. u9 This criterion was claimed to preclude the apparent contradiction between unitarity and local EFT in Hawking’s argument. It is clear that it does not lead to obvious testable violations of EFT, and it was also claimed to avoid more subtle problems like quantum cloning and unacceptably large baryon number violation. The key point for us however is that this criterion, which is a profound statement about the structure of the Hilbert space of quantum gravity, was motivated by operational constraints. It says that whether or not quantum information is ‘‘there’’ is indeed related to its practical accessibility.5
10. u10 The deep insight of AMPS is that even with this stronger causal restriction on when we may use effective field theory there is still a paradox that seems to require more modification of the rules, either by having firewalls or by further violating effective field theory. We interpret our results as supporting a new criterion for the validity of effective field theory:
11. u11 Two spacelike-separated low-energy observables which are not both computationally accessible to some single observer do not need to be realized even approximately as distinct and commuting operators on the same Hilbert space.
12. u12 By computationally inaccessible we mean that one or both of them is so quantum-mechanically nonlocal that measuring it would require more time and/or memory than the observer fundamentally has available. This criterion clearly implies the previous one, but it is stronger: as we will see, it can apply even if both observables are within the past lightcone of some observer. In Minkowski space this criterion (and also the causality criterion) is irrelevant, but in spacetimes with singularities there are observers whose available time is fundamentally limited. This is also true in spacetimes where the fundamental Hilbert space is effectively finite, for example the de Sitter static patch. In that case recurrence phenomena limit how much time is available for low-energy observation rather than a singularity.6 Our proposal violates what AMPS call postulate II, and we will see below that it seems to remove the contradiction that led AMPS to argue for firewalls.
13. u13 Lest the reader worry we are throwing the baby out with the bathwater, we here point out that a traditional asymptotic observer at infinity, whom we will refer to as Charlie, has all the time and memory needed to measure the Hawking radiation as carefully as he likes. Our arguments are thus no threat to the unitarity of black hole evaporation as a precise quantum mechanical process; there will be new restrictions on the validity of effective field theory only for an observer we call Alice who falls into the black hole before it evaporates.7
14. u14 Both the weaker “causality” criterion and the stronger “computational” criterion are negative statements; they tell us what the Hilbert space is not. It is of course very important to understand what the structure of the Hilbert space is, and there are two interesting proposals. The first, sometimes called ‘‘strong complementarity’’, takes the point of view that each observer has her own quantum mechanical theory, which is precise for some special observers and approximate in general.8 There are then consistency conditions between the different theories to ensure that observers who can communicate with each other agree on the results of low-energy experiments visible to them both. Within this framework it was argued [14, 15] that if the AMPS experiment cannot be done, the firewall argument breaks down.9 The basic point is that physical restrictions on what measurements can be done weaken the overlap conditions, allowing for more “disagreement” between Alice and Charlie’s quantum mechanical descriptions of what is going on.
15. u15 The other proposal for the Hilbert space structure, which might be called “standard complementarity”, claims that there is a single Hilbert space in which states undergo exact unitary evolution. The quantum physics of various observers are embedded into this single Hilbert space in such a way that each observer has for each time slice a set of distinct operators that approximately commute. The semiclassical interpretation of an operator according to one observer can be quite different from that of another observer however, and in particular things which are inside the horizon according to one observer might be outside from the point of view of another. This viewpoint is essentially that of [5, 6, 7], and in the context of firewalls it is sometimes called “ $A=R_{B}$ ’’ for reasons we will soon see. It has been suggested by several people10 as a way out of firewalls, but it has so far run into various paradoxes involving apparent cloning and acausality [14, 18]. We postpone further discussion of these two options until after we present the firewall argument, but it seems that in either framework our computational breakdown of EFT may be sufficient to avoid the paradoxes without any need for firewalls.11
16. u16 It is also interesting to think about whether more general types of black holes have firewalls. For example Reissner-Nordstrom black holes semiclassically seem to take an infinite amount of time to evaporate, apparently allowing ample time for quantum computation prior to jumping in. We will explain however that the well-known “fragmentation” phenomenon [20, 21] destroys the black hole well before the computation can be completed. Big AdS black holes do not evaporate at all, so the AMPS argument does not directly apply to them, but arguments have been put forward suggesting that they nonetheless have firewalls. In particular Don Marolf has argued that one could simply mine the black hole until half of its entropy is gone, after which the mining equipment would play the role of the Hawking radiation in the original AMPS argument. If the decoding time is indeed exponential in the entropy of the black hole, as we argue it is, then it becomes comparable to the Poincaré recurrence time of the AdS-Schwarzschild space [22]; we argue that no observer or computer can isolate itself from a big black hole for so long in AdS space.
17. u17 The strictest test of our criticism of the AMPS experiment uses a setup suggested to us by Juan Maldacena, in which a large AdS black hole is placed very far down a throat whose geometry is asymptotically Minkowski. By putting the decoding apparatus out in the Minkowski region, it seems that one could use the redshift to arbitrarily speed up the decoding time compared to the evaporation time. We will explain in section 5 however that the decoupling which makes the decay slow in this situation also makes it very difficult to send the results of the computation back down the throat, and for a particular example we show that, for a wide variety of probes, the time required to successfully send a message down the throat is longer than the recurrence time of the black hole down the throat. So indeed it seems there is a fairly robust conspiracy preventing the AMPS experiment from being done. These results are consistent with a point of view expressed by Aaronson [23] that the laws of physics should not permit computational machines that radically alter the basic structure of complexity theory. At most, they should force some marginal changes around the edges, as in the case of Shor’s factoring algorithm.
18. u18 It is interesting to note that if our computational complexity argument is correct, it supersedes many of the classic black hole thought experiments [5, 6, 7, 3]. In particular the argument of [3] that the scrambling of information by a black hole in a time no faster than $M\log M$ is necessary to prevent observable cloning would be no longer be needed.
19. u19 An objection to our argument that we have sometimes encountered is the following: say that we have a quantum computer which is simulating some quantum gravity theory like $\mathcal{N}=4$ Super Yang-Mills theory. Somebody who is working the computer could decide to make a black hole in the simulation, let it evaporate for a while, pause the simulation, use the computer to decode the radiation while the simulation is paused, and then start the simulation again. In this way divine intervention from the outside is able to circumvent our claim that the radiation cannot be decoded in time for an infalling observer to see it. One can try to make this proposal sound somewhat less artificial by setting it in AdS, where the claim would be that, since the spacetime is not globally hyperbolic, these manipulations can be done by coupling the bulk to an arbitrary external system at the boundary and manipulating this coupling at will. From our point of view however the main question at stake here is whether or not nonsingular initial data on some Cauchy surface generate singularities (such as firewalls) beyond those predicted by low energy physics. We are less concerned about the question of what happens if some godlike entity, external to the system, disrupts it in some arbitrary way. In particular if something subtle like standard complementarity is going on in the structure of the Hilbert space, then outside manipulations which naively don’t affect the region behind the horizon might actually have rather drastic effects on it.12 We would be more concerned by this argument if the coupling of AdS to the external system were accomplished in a manner in which it were clear that low energy physics might be expected to hold throughout the joint system, and indeed one can interpret the throat geometry we discuss in section 5 as a realization of this. In that setup physical restrictions seem to prevent any observer from overcoming the computational complexity of decoding.
20. u20 This introduction has telegraphically sketched our main points. In the remainder of the paper we will make the case again in much more depth. Because of our expected audience we will try to keep our discussions of quantum computation and coding self-contained, but the same definitely cannot be said for our discussions of black holes and gravity. Other work on firewalls includes [25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35].
21. u21 2 The Firewall Argument
22. u22 We begin with a somewhat reorganized presentation of the original argument of [1]. Their argument rests on some basic assumptions about the quantum description of a black hole from the points of view of an external observer Charlie and an infalling observer Alice, and we will try to be clear about what these assumptions are. The argument has many fine technical points, and we will not address all of them. Our goal is to motivate equation (4), on which the rest of our paper will be based.
23. u23 2.1 A Quantum Black Hole from the Outside
24. u24 We’ll first discuss Charlie’s description, which is based on the following three postulates:
25. u25 According to Charlie, the formation and evaporation of the black hole is a unitary process. Moreover, in addition to an asymptotic S-matrix, we can also think about either continuous or discrete time evolution in which at any given time there is a pure quantum state $|\Psi\rangle$ in some Hilbert space $\mathcal{H}_{outside}$ .
26. u26 At any given time in this unitary evolution we can factorize $\mathcal{H}_{outside}$ into subfactors with simple semiclassical interpretations:
27. u27 Here $\mathcal{H}_{R}$ are the modes of the radiation field outside of the the black hole, roughly with Schwarzschild coordinate radius $r>3GM$ . $\mathcal{H}_{B}$ are the field theory modes in the near-horizon region, roughly with support over $2GM+\epsilon<r<3GM$ where $\epsilon$ is some UV cutoff. The geometry in this region is close to Rindler space. $\mathcal{H}_{H}$ are the remaining degrees of freedom in the black hole, which we can heuristically think of as being at the stretched horizon at $r=2GM+\epsilon$ . Clearly the distinctions between these subfactors are somewhat arbitrary. In particular, it will be convenient to restrict the modes in $\mathcal{H}_{B}$ to have Schwarzschild energy less than the black hole temperature $T=\frac{1}{4\pi GM}$ . Those with higher energy are not really confined to the near-horizon region and we will include them as part of $\mathcal{H}_{R}$ . The time evolution of $|\Psi\rangle$ does not respect this factorization and cannot be computed using low energy field theory, but for our purposes it is enough to consider the state at a given time.
28. u28 If $|H|$ and $|B|$ are the dimensionalities of $\mathcal{H}_{H}$ and $\mathcal{H}_{B}$ respectively, then $\log|H|$ and $\log|B|$ are both proportional to the area of the black hole horizon in Planck units at the time at which we study $|\Psi\rangle$ . Thus their size decreases with time. Naively $\mathcal{H}_{R}$ is infinite dimensional since all sorts of things could be going on far from the black hole, but we will restrict its definition to only run over the subfactor which in $|\Psi\rangle$ is nontrivially involved in the black hole dynamics. Thus the size of $\mathcal{H}_{R}$ grows with time.
29. u29 The third assumption leads to an interesting distinction between “young” and “old” black holes [3], with the separation based on whether $|R|$ is bigger or smaller than $|H||B|$ . When the black hole is young, $|R|$ is quite small and $B$ and $H$ are entangled significantly. As the black hole becomes old however, $|R|$ becomes large and $B$ and $H$ taken together become a small subsystem of the full Hilbert space $\mathcal{H}_{outside}$ . Page’s theorem [36] then suggests that the combined system $BH$ has a density operator which is close to being proportional to the identity operator:13
30. u30 The time beyond which this is true has come to be called the Page time. More carefully we would expect a thermal distribution in the Schwarzschild energy at the usual temperature $T=\frac{1}{4\pi GM}$ , but since we have put high-frequency modes in $\mathcal{H}_{R}$ the thermal density matrix for $\mathcal{H}_{H}\otimes\mathcal{H}_{B}$ is quite close to (2).14
31. u31 We can describe the state concisely by saying that $BH$ is maximally entangled with a subspace in $R$ . More precisely, there is a $|\Psi\rangle$ -dependent decomposition of $\mathcal{H}_{R}$
32. u32 with $|R_{H}|=|H|$ and $|R_{B}|=|B|$ , such that we can write the state of the full system, to a good approximation, as15
33. u33 Here $h$ and $b$ label orthonormal bases for $\mathcal{H}_{H}$ and $\mathcal{H}_{B}$ respectively, and we have chosen convenient complementary bases for $\mathcal{H}_{R_{H}}$ and $\mathcal{H}_{R_{B}}$ . $R_{H}$ and $R_{B}$ are called the purifications of $H$ and $B$ respectively. The state has zero projection onto $\mathcal{H}_{other}$ .
34. u34 This form of $|\Psi\rangle$ makes it clear that any measurement done on $B$ is perfectly correlated with some other measurement done on $R_{B}$ . This consequence of the entanglement was emphasized in [1]; in their language measurements done on $R_{B}$ project onto particular states in the basis $|b\rangle_{B}$ . We hope that it is clear however that the presence of this entanglement does not require any such measurement to be done; once we accept the three assumptions the entanglement follows directly. Indeed we would argue that Charlie’s ability to measure $R_{B}$ provides justification for accepting the Hilbert space structure of the model.16
35. u35 2.2 A Quantum Black Hole from the Inside
36. u36 We now consider Alice the infalling observer’s point of view. As mentioned in the introduction, it may be possible to “embed” Alice’s quantum mechanics into Charlie’s via some sort of nontrivial operator mapping. We will discuss this eventually but for the moment will just treat Alice’s theory as an independent construction. Here are the basic assumptions about it:
37. u37 Although Alice eventually hits the singularity, we imagine that well before that she has an approximately quantum mechanical description of her experiences in terms of a quantum state on a time slice like the one shown in figure 1. We will not insist that the state be pure.
38. u38 Alice’s Hilbert space also has a roughly semiclassical factorization of the form
39. u39 Here $\mathcal{H}_{B}$ and $\mathcal{H}_{R}$ are factors shared with Charlie, since they are outside the black hole horizon and are causally accessible to both Charlie and Alice. $\mathcal{H}_{A}$ are the field theory modes just inside the horizon, say with support over $GM<r<2GM-\epsilon$ . $\mathcal{H}_{H^{\prime}}$ are the remaining degrees of freedom having to do with Alice’s horizon (which is distinct from the black hole horizon). $\mathcal{H}_{H}$ is absent; the region $2GM-\epsilon<r<2GM+\epsilon$ is passed through by Alice in an extremely short period of time and does not have any operational meaning to her. Of course, at times long before she falls in, the black hole horizon is indistinguishable from her horizon, and $\mathcal{H}_{H}$ is roughly part of $\mathcal{H}_{H^{\prime}}$ . We emphasize however that the details of this accounting don’t matter.
40. u40 Because $\mathcal{H}_{B}$ and $\mathcal{H}_{R}$ are shared with Charlie, we must have $\rho^{\{Alice\}}_{BR}=\rho^{\{Charlie\}}_{BR}$ . This is sometimes called the overlap rule, and it is designed to prevent contradictions where Alice and Charlie disagree about the results of experiments they can communicate about.
41. u41 Figure 1: Alice’s quantum mechanics, compared to Charlie’s. The world inside her horizon is drawn in blue and the time slice she quantizes on is in red. For reference Charlie’s world is in yellow, and the overlap is green. We’ve chosen Charlie’s black slice to coincide closely with Alice’s near and .
42. u42 With these assumptions, one can now argue following AMPS that Alice must not see a smooth vacuum at the horizon. Recall that the modes in $\mathcal{H}_{B}$ and $\mathcal{H}_{A}$ are basically Rindler modes on two different sides of a Rindler horizon. In the Minkowski vacuum state such modes are close to maximally entangled:
43. u43 where $\beta\omega$ is the dimensionless Rindler energy; here it is just the ratio of Schwarzschild energy to the black hole temperature. This however is problematic from our discussion of Charlie. We argued that for an old black hole Charlie should see $B$ being close to maximally entangled with $R_{B}$ , and by the third assumption about Alice this must also be true for her. But entanglement in quantum mechanics is monogamous: such entanglement prevents $B$ from also being entangled with $A$ as in (6). One way to see this more precisely, again following AMPS, who themselves were motivated by a similar argument due to Mathur [37], is to note that strong subadditivity [38] requires
44. u44 By construction we have $S_{BR_{B}}=0$ , which also implies (for example by the Araki-Lieb triangle inequality) that $S_{ABR_{B}}=S_{A}$ . For (7) to be consistent with the subadditivity inequality $S_{A}+S_{B}\geq S_{AB}$ we then must have
45. u45 $I_{AB}$ is called the mutual information between $A$ and $B$ , and it is zero if and only if the density matrix $\rho_{AB}$ is actually a product $\rho_{A}\otimes\rho_{B}$ . This is clearly inconsistent with $A$ and $B$ being close to the highly entangled state (6). This concludes the AMPS argument; one possible interpretation is that the resolution of the contradiction is that there is a “firewall” of high energy quanta at the horizon of an old black hole which annihilates any infalling observer.
46. u46 2.3 A Way Out?
47. u47 A key step in the AMPS argument is that $B$ and $R_{B}$ are accessible to both Charlie and Alice and that therefore they must agree on the entanglement between them. But is this really true? In [15] it was argued that it is difficult for Alice to measure $B$ because she passes through it quickly, but the details of that argument have not worked out satisfactorily. The much more difficult measurement however is the one on $R_{B}$ . $R_{B}$ is defined as the subfactor of the Hawking radiation which is entangled with $B$ , but this subfactor is presumably very convoluted from the point of view of a basis of Hawking quanta that is easy to measure. Probing $R_{B}$ entails doing quantum measurements involving nonlocal quantum superpositions of large numbers of Hawking quanta. Such measurements need to be very carefully engineered, and one might expect that this engineering takes a significant amount of time. This is no problem for Charlie, who has all the time in the world to look at the Hawking radiation, but Alice needs to be able to make the measurement fast enough that she can then jump into the black hole before it evaporates. In this paper we will argue that Alice simply does not have time to do this.
48. u48 As a result one can consider modifying her postulated quantum mechanics, for example in one of the two directions described in the introduction. In the “strong complementarity” approach, Alice’s quantum mechanics has no direct relation to Charlie’s. They are related only insofar as they must agree on the results of experiments which are visible to both of them. Since operators acting on $\mathcal{H}_{R_{B}}$ are not accessible to Alice, our computational criterion for the breakdown of effective field theory allows us to either disentangle $\mathcal{H}_{R_{B}}$ from $\mathcal{H}_{B}$ in Alice’s theory (but not Charlie’s) or more perhaps simply to just remove $\mathcal{H}_{R_{B}}$ from her Hilbert space altogether. This then “frees up” $B$ to be entangled with $A$ , ensuring Alice a smooth journey across the horizon. In “standard complementarity” we instead think of Alice’s theory as being embedded in Charlie’s. To avoid firewalls one might try to arrange that operators on Alice’s $\mathcal{H}_{A}$ are really just her interpretations of operators acting on what Charlie would have called $\mathcal{H}_{R_{B}}$ . As mentioned in the introduction, this idea, which is essentially an enhanced version of the original proposal of [5, 6, 7], is referred to as “ $A=R_{B}$ ” since the entanglement will only work out consistently if we “build” interior operators out of exterior operators which already have the correct entanglement with operators acting on $\mathcal{H}_{B}$ . Without limitations on Alice’s ability to directly measure $R_{B}$ however it seems to lead to paradoxes and has thus been viewed with some skepticism. We view our work as potentially restoring the credibility of this proposal. We will discuss this a bit more concretely in section 6 below.
49. u49 3 The AMPS Experiment as a Quantum Computation
50. u50 We now begin our discussion of the decoding problem confronting Alice. We will phrase the discussion in terms of Charlie’s Hilbert space, since for the moment we are following AMPS and granting that Charlie and Alice must agree on the density matrix of $\mathcal{H}_{B}\otimes\mathcal{H}_{R}$ . For simplicity we will throughout model all Hilbert spaces using finite numbers of qubits. In the Schmidt basis the state of the old black hole she is interested in is given by equation (4), but this basis is very inconvenient for discussing Alice’s actions. From here on we will use exclusively a basis for the radiation field which is simple for Alice to work with, and whose elements we will write as
51. u51 Here there are $n\equiv\log_{2}|R|$ total qubits, each of which we assume Alice can manipulate easily. $b_{1}\ldots b_{k}$ are the first $k$ of these qubits, where $k$ is the number of bits in $\mathcal{H}_{B}$ , and $m$ is the number of bits in $\mathcal{H}_{H}$ . We can think of $k+m$ as the number of qubits remaining in the black hole; we will eventually argue that the decoding time is likely of order $2^{k+m+n}$ . The $r_{i}$ qubits make up the remainder of the modes which have non-trivial occupation from the Hawking radiation. Roughly we might expect that
52. u52 where $S_{initial}$ is the horizon area in Planck units of the original black hole prior to any evaporation. This is something of an underestimate because the computational basis is local while the information is nonlocal, but this “coarse-graining” enhancement isn’t large. The radiation mostly comes out in $s$ -wave quanta so it is effectively one-dimensional. It extends out to a distance $L\sim M^{3}$ and consists mostly of quanta whose energy is of order $1/M$ , so its thermal entropy is $n\approx LT\sim M^{2}$ , which is still of order the initial black hole entropy as we would conclude from (10).17 Perhaps surprisingly the black hole makes quite efficient use of the information storage capacity available to it.
53. u53 We will adopt standard terminology and refer to the basis (9) as the computational basis. In the computational basis we can write the state (4) as
54. u54 where $U_{R}$ is some complicated unitary transformation on $\mathcal{H}_{R}$ . What unitary transformation it is will depend on the details of quantum gravity, as well as the initial state of the black hole. For simplicity we have defined it to act on the state where all of the $r_{i}$ qubits are zero. Clearly the challenge Alice faces is to apply $U_{R}^{\dagger}$ to the Hawking radiation, after which it will be easy for her to confirm the entanglement between $\mathcal{H}_{B}$ and $\mathcal{H}_{R_{B}}$ . Engineering a particular unitary transformation to act on some set of qubits is precisely the challenge of quantum computation, and we will henceforth often refer to Alice’s task as a computation.
55. u55 So far we have been interpreting $\mathcal{H}_{B}$ as the thermal atmosphere of the black hole, but to actually test the AMPS entanglement it would be silly for Alice to try to decode all of the atmosphere. Indeed the separation between $\mathcal{H}_{B}$ and $\mathcal{H}_{H}$ is rather ambiguous, and we are free to push some of the atmosphere modes we are not interested in into $\mathcal{H}_{H}$ . So from here on we will mostly take $k$ to be $O(n^{0})$ . This ostensibly simplifies her computation, because in any event she only needs to implement $U_{R}$ up to an arbitrary element of $U(2^{n-k})$ acting on the last $n-k$ qubits of the radiation. This simplification turns out to be irrelevant since the dimensionality of the coset $U(2^{n})/U(2^{n-k})$ still scales like $2^{2n}$ for $k>0$ , but more importantly it is clear from (11) that $U_{R}$ has only really been defined acting on the $2^{k+m}$ -dimensional subspace of $\mathcal{H}_{R}$ spanned by states of the form $|bh0\rangle$ . Its action on the orthogonal subspace can be chosen freely to simplify the computation provided that it preserves orthogonality, and we will see below that this reduces the time of Alice’s computation from a naive $2^{2n}$ to only $2^{k+m+n}$ . Since the black hole is old we have $n>k+m$ , so this is at least $2^{2(k+m)}$ .
56. u56 Since the unitary group is continuous it is clear that Alice will not be able to do the computation exactly. We thus need a good definition of how “close” she needs to get to reliably test the entanglement. One standard way to quantify closeness of operators is the trace norm [39], which for an operator $A$ is defined as
57. u57 When $A$ is hermitian this is just the sum of the absolute values of its eigenvalues. The motivation for this definition is as follows: say $\rho_{1}$ and $\rho_{2}$ are two density matrices, and $\Pi_{a}$ is a projection operator for some measurement to give result $a$ . Then
58. u58 so if the trace norm of the difference of two density operators is less than $\epsilon$ then the probabilities they predict for any experimental result will differ by at most $\epsilon$ . The trace norm of their difference is clearly preserved by unitary evolution.
59. u59 If both states are pure then the trace norm of their difference has a simple interpretation. For any two pure states $|\Psi_{1}\rangle$ and $\Psi_{2}$ we can write that
60. u60 where $|\chi\rangle$ is orthogonal to $|\Psi_{1}\rangle$ , $\alpha$ is real, and $\delta$ is real and positive. A simple calculation then shows that
61. u61 3.1 Quantum Computing is Hard
62. u62 We begin with a rather formal discussion of Alice’s computation to illustrate some basic limitations on what is possible; we will take a more standard approach in the following subsection. In order to do her computation Alice needs to adjoin the radiation to some computer, whose initial state lives in a new Hilbert space $\mathcal{H}_{C}$ , and then wait for the natural unitary evolution $U_{comp}$ on $\mathcal{H}_{R}\otimes\mathcal{H}_{C}$ to undo $U_{R}$ and put the bits which are entangled with $B$ into an easily accessible form, let’s say the first $k$ qubits of the memory of the computer. We show this pictorially in figure 2.
63. u63 Figure 2: What the computer does. The connecting lines at the top and bottom indicate entanglement, and time goes up. The subsystem goes along for the ride, and after the computation its purification is split between and in some complicated way.
64. u64 For most of this subsection we will fix the amount of time that the computer runs for, meaning that we will take $U_{comp}$ to be determined by the laws of physics and thus unchangeable. The only way Alice has any hope of getting the computer to do what she wants is by carefully choosing its initial state. Without loss of generality she can take this initial state to be pure, perhaps at the cost of increasing the size of the computer. We will show that no matter how large she makes her computer, it is very unlikely that she will be able to find even one initial state which does the computation.
65. u65 More precisely what Alice would like to do is find a state $|\Psi\rangle_{C}$ which for all $b$ and $h$ evolves as
66. u66 where $|\mathrm{something}\rangle$ is any pure state of the computer and radiation minus the first $k$ bits of the memory. $|\mathrm{something}\rangle$ can and will be different for different $h$ . To estimate how likely it is that such a $|\Psi\rangle_{C}$ exists, we discretize the Hilbert space using the trace norm. In any Hilbert space $\mathcal{H}$ of dimension $d$ we can find a finite set $S_{\epsilon}\subset\mathcal{H}$ with the property that any pure state in $\mathcal{H}$ is within trace norm distance $\epsilon$ of at least one element of $S_{\epsilon}$ . Such a set is called an $\epsilon$ -net, and it is not too hard to get an estimate of how many elements it must have [40]. One first observes from (15) that half of the trace norm difference is weakly bounded by the Hilbert space norm:
67. u67 Thus an $\epsilon/2$ -net for the Hilbert space norm is also an $\epsilon$ -net for the trace norm. The minimal size of an $\epsilon/2$ -net for the Hilbert space norm is the number of balls of radius $\epsilon/2$ centered on points on the unit sphere in $\mathbb{R}^{2d}$ that are needed to cover it, which at large $d$ is proportional to some small power of $d$ times $\left(\frac{2}{\epsilon}\right)^{2d-1}$ .18 Intuitively we may just think of unitary evolution as an inner-product preserving permutation of the $\left(\frac{2}{\epsilon}\right)^{2d}$ states.
68. u68 Applying this now to our discussion of the computer, for fixed $b$ and $h$ the total number of possible states that could appear on the right hand side of (16) is $\left(\frac{2}{\epsilon}\right)^{2|C||R|}$ . The number of possible $|\mathrm{something}\rangle$ ’s is $\left(\frac{2}{\epsilon}\right)^{2|R||C|2^{-k}}$ . For a given $|\Psi\rangle_{C}$ , the probability over random choices of $U_{comp}$ that (16) holds for all $2^{k+m}$ values of $b$ and $h$ is then roughly $\left(\frac{2}{\epsilon}\right)^{-2|C||R|2^{m}(2^{k}-1)}$ . The number of available initial states is $\left(\frac{2}{\epsilon}\right)^{2|C|}$ , so the probability that Alice can find one for which (16) holds is no more than19
69. u69 For any nontrivial $k$ and $|R|=2^{n}$ , it is clear that this probability is extraordinarily small. Making the computer bigger just makes it even more unlikely that the computation can be done!
70. u70 What then is Alice to do? One might hope that, although the probability of success is small for any given computer size, by searching over many values of $|C|$ Alice might find one that works. This is a bad idea; summing (18) over $|C|$ produces a finite sum whose value remains exponentially small in $|R|$ . Alice can do better however by varying the running time of the computer. This lets her sample a variety of $U_{comp}$ ’s without increasing the size of the Hilbert space. If each $U_{comp}$ is different, then the longest she might have to wait to get a $U_{comp}$ that works is
71. u71 Although finite, this is unimaginably long for any reasonable system size. For an astrophysical black hole in our universe it is something like $10^{10^{10^{40}}}$ years.
72. u72 The timescale (19) has a simple physical interpretation; it is the quantum recurrence time. This is the timescale over which a quantum system comes close to any given quantum state, and as we found here is double-exponential in the entropy of the whole system. In doing the computation this way, Alice is simply waiting around for a quantum recurrence to do it by pure chance.
73. u73 Fortunately for civilization, these simple estimates are not the final word on quantum computing power. In particular, (19) does not really hold unless $U_{comp}$ is chosen randomly at each time step. To the extent that there is some structure in how $U_{comp}$ varies with time, as there is in our world, Alice can take advantage of it to speed up her computation. Similarly, if the way $U_{comp}$ changes with increasing $|C|$ also has structure, she can use that as well. The lesson of this section however is that without using special properties of the computer-radiation dynamics, no amount of preparation of the initial state of her computer will allow Alice to do her computation in any reasonable amount of time. In the following two sections we will see that by using such physical properties Alice is able beat the double exponential in computer entropy down to a single exponential in just the radiation entropy, but we will also argue that that is probably all she gets.
74. u74 As a tangential comment it is interesting to note that the result of this section is actually special to quantum mechanics; there is a somewhat analogous problem in classical coding which can easily be solved by making the computer bigger. Say that we have a classical bit string of length $n$ . There are $2^{n}$ such strings, but say we are interested in some subset of size $2^{k}$ . For example this could be the set with a $k$ -bit message in the first $k$ bits and zero for the rest. Acting with some random permutation on the space of $2^{n}$ strings, we can send these $2^{k}$ strings to a set of $2^{k}$ scrambled “code words”, which are analogous to some basis for $R_{B}$ in the quantum problem. We could then imagine adjoining one of our $n$ -bit strings to a $c$ -bit “computer” string, and then acting with a given permutation of the $2^{n+c}$ states of this larger system. This permutation is the analogue of our $U_{comp}$ . The question is then the following: given this larger permutation, can we find a single initial string for the computer such that, after the permutation is applied, it will send the set of codewords to a set for which the message is again displayed in the first $k$ qubits. It turns out that the answer to this question is yes; out of the
75. u75 possible sets of codewords there are $2^{(n+c-k)2^{k}}$ which have the message in the first $k$ bits. Thus for a given initial string for the computer the probability that the permutation sends a generic set of codewords to a “good” set is
76. u76 which for fixed $k$ we can easily beat by trying the various $2^{c}$ initial states for the computer. It does require an $c\sim 2^{k}$ -bit computer however.
77. u77 3.2 Implementing a General Unitary Transformation with Quantum Gates
78. u78 In our world, the result of the previous section, that doing a quantum computation at worst takes a time which is double exponential in the entropy of the computer, had better not be optimal if we are ever to do any quantum computation at all. It can be improved upon of course, and the reason is that locality of interactions makes the dependence of $U_{comp}$ on time and computer size very special indeed.20 Since no quantum computer has yet been built we do not know exactly how one might be implemented physically, but there is a widely accepted model for quantum computation called the quantum circuit model. In the quantum circuit model one imagines having a “quantum memory” consisting of $n$ qubits, on which one can easily act with some finite set of one- or two-qubit unitary transformations, called quantum gates, on any qubit or pair of qubits. The computer builds up larger unitary transformations by applying the various gates successively. Interestingly the number of different types of gates needed to generate arbitrary unitary transformations with high precision is quite small. In fact, one is sufficient provided it is generic enough and that it can be applied to any two of the qubits (and in either order on those two). A set of gates having this property is called universal. A specific set of three gates which is universal is the Hadamard gate, which acts on a single qubit as
79. u79 the $Z^{1/4}$ gate which acts on a single qubit as21
80. u80 and the CNOT gate $U_{cnot}$ , for “controlled not”, which acts on two qubits as
81. u81 with the addition being mod $2$ . This gate flips the second bit if and only if the first bit is $1$ . There is a standard graphical notation for representing circuits, which we have already used in figure 2, and we illustrate it some more in figure 3.
82. u82 Figure 3: The standard representations of the three gates described in the text, as well as a simple circuit that maps the product basis to a basis each element of which has the two qubits maximally entangled. In the CNOT gate the addition is done at the hollow circle.
83. u83 We can now ask how many gates are needed to make a complicated unitary transformation like $U_{R}$ in equation (11). This is a good measure of the amount of time/space needed to actually do the computation, since we can imagine that the gates can be implemented one after another in a time that scales at most as a small power of $n$ . For a set of $f$ fundamental gates, the number of circuits we can make which use $T$ total gates is clearly
84. u84 To proceed further we need some basic idea of size and distance for the unitary group. The unitary group on $n$ qubits is a compact manifold of dimension $2^{2n}$ , and we can parametrize its elements as
85. u85 Here $t^{a}$ are generators of the Lie algebra of $U(2^{n})$ , and we can very roughly think of the $c_{a}$ ’s as parametrizing a unit cube in $\mathbb{R}^{2^{2n}}$ . Also roughly we can think of linear distance in this unit cube as a measure of distance between the unitaries. For example say we wish to compute the difference between acting on some pure state $|\Psi\rangle$ with two different unitary matrices $U_{1}$ and $U_{2}$ and then projecting onto some other state $\chi$ :
86. u86 If the sum of the squares of the $\delta c_{a}$ ’s is less than $\epsilon^{2}$ , the right hand side will be at most some low order polynomial in $2^{n}$ times $\epsilon$ . This polynomial is irrelevant as we now see.
87. u87 Around each of our $(n^{2}f)^{T}$ circuits we can imagine a ball of radius $\epsilon$ in $\mathbb{R}^{2^{2n}}$ . The volume of all the balls together will be of order the full volume of the unitary group when
88. u88 Thus we see that in order to be able to make generic elements of $U(2^{n})$ we need at least
89. u89 gates, where we have kept only the leading dependence on $n$ and $\epsilon$ . As promised, because $\epsilon$ appears inside a logarithm the crude nature of our definition of distance has not mattered. More importantly, we see that the number of gates is now only a single exponential in (twice) the entropy. The fact that this crude counting bound can be achieved by an appropriate sequence of gates is known as the Solovay-Kitaev theorem. So the quantum circuit model is able to do arbitrary quantum computations much faster than our calculation of the previous section suggested; this is essentially because locality enables us to dynamically isolate parts of of the computer in such a way that we can push the chaos of the system into heating the environment (not explicitly modeled here) instead of messing up our computation.
90. u90 Given that we have so quickly beaten down a double exponential to a single exponential, one might be optimistic that further reduction in computing time is possible. Unfortunately, in our universe that does not seem to be the case. Simple modifications of the quantum circuit model such as changing the set of fundamental gates or considering higher spin fundamental objects instead of qubits, for example qutrits, make only small modifications to the analysis and don’t change the main $2^{2n}$ scaling. One could imagine trying to engineer gates that act on some finite fraction of the $n$ qubits all at once, perhaps by connecting them all together with wires or something, but it is easy to see that any such construction requires a number of wires exponential in $n$ . One could also try to parallelize by applying gates on non-overlapping qubits simultaneously whenever possible, as well as adding additional “ancillary” qubits. As long as the number of extra qubits scales like some power of $n$ , however, it is clear they cannot beat the $2^{2n}$ . Even with exponentially many ancilla or wires just the travel time between the various parts of the computer will be exponential in $n$ . In the face of these difficulties the reader might be tempted to try using some sort of exotic nonlocal system like a black hole to do the computation, but this would just give up what the circuit model accomplished and most likely return us to even worse situation of the previous section. In this paper we will adopt the widely held point of view that the quantum circuit model accurately describes what are physically realistic expectations for the power of a quantum computer.
91. u91 Thus if $U_{R}$ has no special structure, we do not expect Alice to be able to implement it (or its inverse) in time shorter than $2^{2n}$ . As discussed below equation (11) however, $U_{R}$ was defined only by its action on a subspace of dimension $2^{k+m}$ . In studying the complexity of $U_{R}$ we are free to quotient $U(2^{n})$ by multiplication on the right by a block diagonal matrix which acts as the identity on the subspace spanned by states of the form $|bh0\rangle$ . The dimensionality of this quotient is $2^{k+m+n}$ , and since it is good enough to find a circuit which produces any element of the coset containing $U_{R}$ the counting argument of this section suggests that Alice will be able to use a decoding circuit implementable in a time scaling like
92. u92 3.3 Why is Alice’s Computation Slower than the Black Hole Dynamics?
93. u93 We now turn to the question of whether or not the black hole dynamics constrain $U_{R}$ in any way that could help Alice implement it faster. One thing we know about the black hole is that it produces the state (11) relatively quickly, in a time that scales like $n^{3/2}$ for a Schwarzschild black hole. This seems to suggest that Alice might be able implement $U_{R}^{\dagger}$ quickly by some sort of time-reversal. This turns out not to be the case. To explain this we introduce a slightly more detailed model of the dynamics that produce the state (11).
94. u94 To describe the evaporation process it is clearly necessary to have a Hilbert space in which the we can have black holes of different sizes. We can write this as
95. u95 Here the subscripts $n$ and $n_{f}-n$ indicate the number of qubits in the indicated Hilbert spaces. The dimensionality of $\mathcal{H}$ is $n_{f}2^{n_{f}}$ . We can imagine starting in the subspace with $n=0$ and then in each time-step acting with a unitary transformation that increases $n$ by one. We will take the evolution on the radiation to be trivial. The black hole becomes old after $n_{f}/2$ steps. This “adiabatic” model of evaporation assumes equation (10) is exact and does not involve any energetics but, as discussed below equation (10), it is not a bad approximation for the decay of a Schwarzschild black hole: the number of Hawking quanta produced is of order the entropy of the black hole, and so is their coarse-grained entropy.
96. u96 An actual black hole formed in collapse will have some width in energy, which here means a width in $n$ , but by ignoring this we can make a further simplification. Starting in one of the $2^{n_{f}}$ states with $n=0$ , the evolution never produces superpositions of different $n$ . So we can actually recast the whole dynamics as unitary evolution on a smaller Hilbert space of dimension $2^{n_{f}}$ , but in which the interpretation of subfactors changes with time. We illustrate this with a circuit diagram in figure 4.
97. u97 Figure 4: The black hole dynamics for a 7-bit black hole. With each step the subfactor we interpret as the radiation gets larger.
98. u98 With this simplification we can now combine all of the timesteps together into one big unitary matrix $U_{dyn}$ acting on our $2^{n_{f}}$ dimensional Hilbert space. The matrix $U_{R}$ appearing in the state (11), which we now interpret as having been produced by $U_{dyn}$ , will (unlike $U_{dyn}$ ) depend rather sensitively on the initial state, and since Alice only needs to be able to do the computation for some particular initial state we will for simplicity choose it to just have all the bits set to zero. For $n>\frac{n_{f}}{2}$ we then expect
99. u99 So this equation tells us something about $U_{R}$ , whose complexity we are interested in understanding. To proceed further we need to make some sort of assumption about $U_{dyn}$ . This is a question about the dynamics of quantum gravity so we can’t say anything too precise, but for those black holes which are well understood in matrix theory [44] or AdS/CFT [45, 46, 24] the dynamics are always some matrix quantum mechanics or matrix field theory. Theories of this type can usually be simulated by polynomial-sized quantum circuits [47, 48, 49, 50], so it seems quite reasonable to assume that $U_{dyn}$ can be generated by a polynomial number of gates.22 Such circuits are usually called “small”, so more precisely we want to know the following: does the existence of a small circuit for $U_{dyn}$ imply the existence of a small circuit for $U_{R}$ ? If the answer is yes, then our model would imply that Alice can decode $R_{B}$ out of the Hawking radiation fairly easily.
100. u100 It is clear that acting on the state $|00000\rangle_{init}$ we can easily decompose $U_{dyn}$ into $U_{R}U_{mix}$ , where $U_{mix}$ is a simple circuit that entangles the first four subfactors in $|00000\rangle_{init}$ :
101. u101 $U_{mix}$ is very easy to implement, we can just use the circuit on the right in figure 3 $n_{f}-n$ times for a total of $2(n_{f}-n)$ gates. We can then define a new operator
102. u102 which has the property that
103. u103 $\tilde{U}_{R}$ can obviously be implemented with a small circuit, and it apparently seems to be exactly what Alice needs; she can just apply the inverse circuit to the state (11) and the decoding is accomplished. Unfortunately for her this does not work. Although the operator $\tilde{U}_{R}$ appears to only act on the radiation, the circuit this construction provides involves gates that act on all of the qubits. While she is doing the decoding Alice does not have access to the qubits in $B$ and $H$ , so she cannot directly use them. Of course, if the circuit really acted as the identity operator on $B$ and $H$ for any initial state this would not matter, she could just throw in some ancillary qubits in an arbitrary state to replace those in $B$ and $H$ and still use the $\tilde{U}_{R}^{\dagger}$ to undo $U_{R}$ . The problem is that (35) holds only when $\tilde{U}_{R}$ acts on the particular state $\frac{1}{\sqrt{|B||H|}}\sum_{b,h}|b\rangle_{B}|h\rangle_{H}|bh0\rangle_{R}$ . This can be traced back to the fact that the definition of $U_{R}$ in the first place depended on the initial state of the black hole on which $U_{dyn}$ acts.
104. u104 Although Alice cannot use these small circuits to decode the entanglement, she can move it around. For example acting with a CNOT gate three times on two qubits, switching which qubit is the “control” qubit each time, exchanges the pair:
105. u105 so by adjoining a set of $n$ ancillary qubits to the state $|\Psi\rangle$ , Alice can use this operation to achieve
106. u106 This trivializes the state of the radiation, but of course doesn’t really accomplish much since testing the entanglement still requires undoing $U_{R}$ . It does show however that Alice can move the quantum information from the radiation to a more “stable” quantum memory in a short amount of time.
107. u107 The lesson of this section is that because Alice does not have access to all of the qubits in the system, she is unable to simply time-reverse the black hole dynamics and extract $R_{B}$ in a time that is polynomial in the entropy. Without such a simple construction, she will in general be left with no option but to brute-force her construction of $U_{R}^{\dagger}$ using of order $2^{n+k+m}$ gates.23 It is still possible that some yet-unknown special features of black hole dynamics will conspire to provide a simple circuit for $U_{R}$ , but it would be rather surprising. After all there are many ways a unitary could be atypical, and most still require exponentially many gates. In the following section we will see that for some analogous questions in the theory of error-correcting codes, within the context of simple circuits with $O(n^{2})$ gates it is possible to run into problems which almost certainly take exponential time to solve. These results will unfortunately not be directly applicable here, but by recasting Alice’s decoding task as an error correction problem we will be able to get more intuition about how the exponential arises. We will also see that being able to efficiently perform a decoding very similar to $U_{R}$ would have very unlikely implications for the complexity class Quantum Statistical Zero-Knowledge.
108. u108 3.4 Two Counting Arguments
109. u109 So far we have mostly restricted ourselves to thinking about a particular black hole microstate, which in the previous section we took to be an element of the basis where $U_{dyn}$ can be constructed out of a polynomial-size quantum circuit. By considering more general initial states we can prove that for a generic initial state the decoding necessarily takes exponential time. Restating the setup of the previous section, we can think of the black hole as a polynomial-size circuit $U_{dyn}$ which acts on a set of microstates $|i\rangle$ as
110. u110 The point here is that we must be able to recover any initial state from the final state, so the unitaries $U_{R}(i)$ must all be distinct elements of the coset $U(2^{n})/U(2^{n}-2^{m+k})$ . But how many initial states are there? If we ignore the coarse-graining that made equation (10) only approximate, then there is a basis of size $2^{n+k+m}$ for the total number of initial states of the black hole. The full set of initial states includes superpositions however, and we can count them by constructing an $\epsilon$ -net like that discussed around equation (17). The total number of initial states then is roughly $\left(\frac{1}{\epsilon}\right)^{2^{n+k+m}}$ . The point then is that this is comparable to the total number of elements in the coset, which also scales like $\left(\frac{1}{\epsilon}\right)^{2^{n+k+m}}$ . Since each state $|i\rangle$ must have its own distinct $U_{R}(i)$ , the vast majority of initial microstates must be decoded by generic $U_{R}$ ’s which necessarily take time of order $2^{n+k+m}$ to implement. Being more careful about the coarse-graining decreases the number of initial states somewhat, but the number is still much too large for anything more than a vanishingly small fraction to be decodable in polynomial time.
111. u111 Proponents of the AMPS experiment could still hope for a basis of initial states where each basis element is easy to decode. A natural basis to try is the one in which $U_{dyn}$ is polynomial size, but we will present arguments in the following section that even in this basis the decoding is hard. One could however try to construct such a basis by taking a basis of final states where the decoding is trivial and then evolving it back with $U_{dyn}^{\dagger}$ .24 This construction can be disrupted however by taking into account the coarse-graining in equation (10) more carefully. More explicitly, let’s say that $n+k+m=S_{initial}/\log 2+\Delta n$ for some $\Delta n>0$ . The number of initial states is then double exponential in $n+k+m-\Delta n$ . It is then not hard to see that even when $\Delta n=1$ , this set of initial states produces a set of $U_{R}$ ’s which form a doubly-exponential small fraction of the coset $U(2^{n})/U(2^{n}-2^{m+k})$ . If each $U_{R}$ were chosen at random and independently, it is doubly exponentially unlikely that even one of these states would produce a $U_{R}$ which can be implemented with a polynomial-size circuit. The initial states constructed by time reversal of trivial decoding states would not correspond to black holes; they would be states in some larger Hilbert space involving entanglement between the black hole and the radiation field.
112. u112 4 Quantum Coding and Error Correction
113. u113 The theory of quantum error correcting codes has interesting implications for the AMPS experiment, which we discuss in this section.25 We will review the main points of this theory assuming no prior experience with the subject. This will be something of a sidetrip from our main exposition, so casual readers may want to skip over this section in a first reading. For the impatient the conclusions of relevance for AMPS are summarized at the end of the section.
114. u114 4.1 Review of Error Correcting Codes
115. u115 Typically quantum systems cannot be isolated from their environment. It is interesting to understand to what extent a system which began in an unknown state can be restored to that state after it has interacted nontrivially with its environment. Usually this is done by introducing another ancillary system and transferring the entanglement with the environment from the system whose state we want to restore to the ancillary system. We show this pictorially in figure 5.
116. u116 Figure 5: Quantum error correction. Here is the system whose state we want to restore, is the environment it becomes entangled with via the interaction , and is the ancilla it interacts with via . At the end the environment is entangled with the ancilla and the system is in the same quantum state it started in.
117. u117 Error correction is not always possible. For example, say that the transformation $U_{noise}$ from figure 5 is such that it results in the system $S$ being maximally entangled with the environment $E$ . There is no information about its initial state remaining in $S$ , and no choice of $U_{correct}$ will allow recovery. What is perhaps surprising is that it is ever possible to restore the initial state after a nontrivial $U_{noise}$ has acted. To see that this can be done, following Shor [53] we consider an arbitrary superposition $|\Psi\rangle=a_{+}|+\rangle+a_{-}|-\rangle$ of the following two nine-qubit states:
118. u118 As a crude model of interaction with the environment, we can imagine that the state $|\Psi\rangle$ will be acted on randomly by a single Pauli operator $X$ , $Y$ , or $Z$ on one of its nine qubits. After this can we restore the state $|\Psi\rangle$ without destroying it? As Shor explained in [53], we can. The idea is to measure the following set of eight “check” operators:
119. u119 Since the states $|\pm\rangle$ are both eigenstates of eigenvalue one for all eight of these operators, this measurement will do nothing to the state $\Psi$ . Let’s say however that interaction with the environment has caused the state to be acted on by $X_{1}$ . This commutes with the last seven check operators, so their eigenvalues are unaffected, but it will change the result of measuring $Z_{1}Z_{2}$ to from $1$ to $-1$ for both states $|\pm\rangle$ . It is easy to see that none of the other possible single-Pauli errors will give this signature as a result of measuring the check operators. We can then “repair” the error up to an overall irrelevant phase by acting with $X_{1}$ . Similarly say that the error acts with $Z_{1}$ . This will now flip the eigenvalue of $X_{1}X_{2}X_{3}X_{4}X_{5}X_{6}$ without affecting any of the other check operators. There are now two other single-Pauli errors with the same signature, $Z_{2}$ and $Z_{3}$ , but we can correct any of the three up to an overall phase by acting with $Z_{1}$ on the state. In this manner it is easy to see that any single-Pauli error can be corrected.26 This protocol is called the Shor code, and it was the first quantum error correcting code to be discovered.
120. u120 The Shor code works for two reasons. One is that it is redundant, meaning that the number of bits of information it protects is significantly fewer than the number of physical bits present. This allows “room” for noise to creep in without disrupting the message. The other reason is that it is nonlocal; the information is carried in the entanglement between multiple qubits, which protects it against local decoherence and depolarization. These observations motivate the general definition of a quantum code as a code subspace - a $k$ -qubit subspace of a larger $n$ -qubit Hilbert space out of which we can build states we wish to protect. In the Shor code the code subspace is spanned by the states $|\pm\rangle$ . Given a code subspace $\mathcal{H}_{C}\subseteq\mathcal{H}$ we can always define an encoding transformation $U_{enc}$ with the property that
121. u121 with $|\bar{c}\rangle$ a complete basis for $\mathcal{H}_{C}$ .
122. u122 To describe error correction more generally, we first need to say more about how to understand the noise generated in a quantum system $S$ interacting with an environment. In such a situation we can always write
123. u123 where $|e\rangle$ is an orthonormal basis for the environment and the operators $M_{e}$ are called Kraus operators [54]. They act only on the system $S$ , have matrix elements
124. u124 and obey
125. u125 A set of operators $M_{e}$ obeying (44) is sometimes called a quantum channel, or occasionally a superoperator.
126. u126 The Kraus operators can be awkward to work with in practice because their definition depends on the details of the interaction with the environment, which we usually do not know. It is therefore convenient to expand them in a standard basis $E_{\alpha}$ of operators such as the $2^{2n}$ distinct products of the Pauli operators
127. u127 and rewrite
128. u128 Here we have defined $|\alpha\rangle\equiv\sum_{e}C_{\alpha e}|e\rangle$ , which are no longer necessarily orthonormal.
129. u129 In this language there is a necessary and sufficient condition for when exact error correction is possible for a given code [55, 56]. A set $\mathcal{E}$ of errors $E_{\alpha}$ is exactly correctable if and only if
130. u130 for any $|\bar{c}\rangle$ , $|\bar{c}^{\prime}\rangle$ in some orthonormal basis for the code space, for any $E_{\alpha},E_{\beta}\in\mathcal{E}$ , and with the coefficents $C_{\alpha\beta}$ independent of $c$ . If the Kraus operators produced by the interaction with the environment can be written only in terms of $E_{\alpha}$ ’s in a set $\mathcal{E}$ with this property, then a generalization of the procedure described above for the Shor code will always allow the state to be recovered perfectly.
131. u131 To build some intuition for this criterion, consider the trivial code $U_{enc}=1$ . The codespace is spanned by states of the form
132. u132 There is an obvious set of $n-k$ “check” operators acting on this code space with eigenvalue one; the spin $Z$ operators acting on the last $n-k$ qubits. As suggested above we can take the $E_{\alpha}$ ’s to be some subset of the $2^{2n}$ distinct products of Pauli matrices, which in general we can write as
133. u133 The parameters $\alpha_{1},\beta_{1},\ldots$ take the values $0$ or $1$ . This set of errors has the special property that each element either commutes or anticommutes with each of the check operators, so the condition (47) implies that the matrix $C_{\alpha\beta}$ will be zero for any two errors $E_{\alpha}$ , $E_{\beta}$ in $\mathcal{E}$ unless they commute with the same set of check operators. Moreover it further implies that in the event that $C_{\alpha,\beta}\neq 0$ then the product $E_{\alpha}^{\dagger}E_{\beta}$ is equal to a product of check operators. Now say we have a channel
134. u134 with all $E_{\alpha}$ with $|\alpha\rangle\neq 0$ in a set $\mathcal{E}$ obeying (47). Channels with this property are called exactly correctable. By measuring the check operators we can collapse this state to one where all remaining $E_{\alpha}$ ’s commute with the same with the same set of check operators. We may then pick any one of the remaining $E_{\alpha}$ ’s and apply $E_{\alpha}^{\dagger}$ to restore the state $|\bar{c}\rangle$ , since in each term this produces some product of check operators which acts trivially on the code space. This correction procedure is easily extended to the general case of nontrivial $U_{enc}$ . We can simply take the set $\mathcal{E}$ of correctable errors for the trivial code and conjugate it by $U_{enc}$ to define $\mathcal{E^{\prime}}=U_{enc}\mathcal{E}U_{enc}^{\dagger}$ . The check operators can be taken to be $U_{enc}Z_{i}U_{enc}^{\dagger}$ for the last $n-k$ Pauli spin Z operators. This construction is not unique since for a given code subspace there will be many $U_{enc}$ ’s which satisfy (41). Of course channels are not always exactly correctable, and when they are not a would-be quantum repair-person needs to look at the set of possible corrections consistent with the result of the check operator measurements and then make her best guess about which one to apply based on her understanding of which errors are most likely. This procedure is sometimes called Maximal Likelihood Decoding.
135. u135 The correction protocol just described is not necessarily the best one in general situations. The transformation $U_{enc}$ relates the “logical” basis in which the code is trivial to the “computational” basis in which the interactions with the environment are simple. The set of conjugated Pauli errors we just discussed is simple from the point of view of the logical basis, but depending on the complexity of $U_{enc}$ it could be quite unnatural from the point of view of the computational basis. In particular we usually expect the Kraus operators to be simple in the computational basis, and insisting on expanding them in the conjugated Pauli basis will lead to more nonzero $|\alpha\rangle$ ’s than are really necessary. A simple example of this that we will use below is the depolarizing channel, which acts on a single qubit coupled to a $4$ -state environment as
136. u136 The Kraus operators for this channel are $I/2,X/2,Y/2,Z/2$ , and it is not hard to verify that it maximally entangles the qubit with the environment, erasing any information about the initial state $|\Psi\rangle$ . More generally, the erasure channel is defined as applying this channel to some known set of $l$ out of our $n$ total qubits. The total set of errors appearing in the channel is then $2^{2l}$ , but if we conjugate them by $U_{enc}$ and re-expand in the Pauli basis we in general find more. Moreover even if the set of $2^{2l}$ erasures obey the correctability condition (47), it will not in general be possible to find some set of conjugated Pauli’s that do. For stabilizer codes [57], a widely studied set of codes that we review briefly in the following subsection, the encoding transformation sends Pauli errors to Pauli errors and we can use the check operator correction procedure described above. For more general $U_{enc}$ we need to do something else.27
137. u137 4.2 Computational Complexity, Stabilizer Codes, and NP-Hardness
138. u138 One obvious source of computational hardness in the error correction procedure described in the previous section is that in measuring the check operators and applying corrections, we need to repeatedly use the encoding transformation $U_{enc}$ . If this unitary is difficult to implement as a quantum circuit, the error correction procedure will be very time-consuming. In our discussion of the AMPS experiment below however, $U_{enc}$ will always be implementable with a small circuit. The rest of the correction procedure seems straightforward, but there is one crucial point where after measuring the check operators we need to pick a correction $E_{\alpha}^{\dagger}$ to apply. In general there are $2^{2n}$ possible errors, out of which $2^{n+k}$ are consistent with any given result for the check operator measurements. For a general channel it might be quite hard to decide which of these $2^{n+k}$ corrections to apply. Since there are $2^{n-k}$ possible results for measuring the check operators, it is impractical to carry around a list of which correction to apply for each syndrome. Without such a list however, it will generally take exponential time in $n$ to determine which check operator to apply since one will just have to go through the list of $2^{n+k}$ potential corrections and compute the probability for each that it is the correct one to apply. In this section we sketch some known results about the hardness of this step for a widely studied set of quantum error correcting codes, the stabilizer codes.
139. u139 Stabilizer codes [57] are defined by the property that the $n-k$ check operators in the computational basis are all just products of Pauli operators of the form (49). Clearly both the Shor code and the trivial code are stabilizer codes. The reason for the name is that the check operators generate a $2^{n-k}$ -element abelian subgroup $\mathcal{S}$ of the full group $\mathcal{G}$ of $2^{2n}$ products of Pauli operators, with the property that with respect to the action of $\mathcal{G}$ on the $n$ -qubit Hilbert space $\mathcal{S}$ is the stabilizer subgroup of the $k$ -qubit code subspace. Thus rather than giving the codespace explicitly we can instead define it by picking some Abelian subgroup of the Pauli group; in practice this is a much more convenient way of defining an error correcting code. Stabilizer codes are fairly easy to encode: for any stabilizer code there is a relatively simple construction [57] of a circuit of size $O(n^{2})$ which implements $U_{enc}$ exactly.
140. u140 Stabilizer codes have the special property that we can expand the errors in Pauli products of the form (49) in the computational basis instead of the logical basis and still have each error commute or anticommute with each check operator. This enables an elegant way of describing the relation of the errors to the results of the check operator measurements. For each check operator we can define a $2n$ component row vector where the first $n$ components are its $\alpha$ ’s from the parametrization (49) and the last $n$ are its $\beta$ ’s. We can then assemble these row vectors into an $(n-k)\times 2n$ matrix $H$ which is often called the parity check matrix. For each error we can make a $2n$ -component column vector $e$ whose first $n$ elements are the $\beta$ ’s for the error and whose last $n$ components are its $\alpha$ ’s. Finally we can define the syndrome $s$ of the error as an $n-k$ component column vector whose $i$ th element is $0$ if the error commutes with the $ith$ check operator and is $1$ if it anticommutes. It is then not hard to check that $He=s$ , with the matrix multiplication done in the field $\mathbb{Z}_{2}$ . Thus the set of errors $e$ consistent with the syndrome $s$ are just the solutions of this linear equation.
141. u141 One simple channel in which one could study the hardness of stabilizer error correction is the erasure channel defined in the previous subsection. In this case the possible error vectors $e$ are nonzero only for a known set of $l$ out of the $n$ qubits. We are then free to remove the $2(n-l)$ columns from $H$ which correspond to qubits which are never erased, finding a new matrix $H^{\prime}$ which is only $(n-k)\times 2l$ . When the inequality $2l<n-k$ is satisfied the matrix equation $H^{\prime}e^{\prime}=s$ is overdetermined and can always be solved by Gaussian elimination in polynomial time unless no solution exists. Indeed this inequality characterizes the channel capacity of the erasure channel, since it can be shown that when it is violated it is impossible for the conditions (47) to be satisfied, while when it is satisfied (47) will also be satisfied for a typical stabilizer code [42]. Thus stabilizer codes in the erasure channel can be corrected in polynomial time. We emphasize however that this matrix structure is special to stabilizer codes, and that for more general codes with polynomial size $U_{enc}$ this procedure will not work. The procedure described in the footnote at the end of the last section will work, but it requires a time $2^{2l}$ which will be quite large when $l$ is order $n$ .
142. u142 This result may not seem so promising from the point of view of the goal of this article, but in fact there is a slightly more complicated channel in which it is possible to show that stabilizer decoding is NP-complete [58, 59]. This is the gold standard in evidence that a classical computation cannot be performed in polynomial time. Good reviews of the basic properties of NP-completeness and its possible relevance for physics are [60, 23]. Unfortunately the technical details of this argument restrict it to showing NP-completeness only if $k$ grows nontrivially with $n$ , since the exponential search which arises involves a search through $2^{k}$ things. This is an assumption we’d like to drop in the context of Alice’s experiment, since we’d like her to be unable to verify the entanglement even when $k$ is order one, but the result is still indicative of our main point since it shows quite convincingly how exponential time may be required for error correction even when $U_{noise}$ and $U_{enc}$ are both polynomial size.28 The channel studied by [59] is one in which $X$ or $Z$ errors can occur on any qubit with probability $p$ . The probability for a general error $E_{\alpha}$ is
143. u143 where $w_{\alpha}$ is called the weight of the error and is defined as as the number of $\alpha_{i}$ ’s and $\beta_{i}$ ’s in the parametrization (49) which are nonzero.29 In order to correct this channel one needs to find the most likely set of errors, all fixable by a single correction, which is consistent with the syndrome $s$ . As explained in [59], the ability to answer this question for general stabilizer codes in polynomial time in $n$ would allow polynomial time in $k$ solution of the following question about matrices:
144. u144 Say we are given an integer $w>0$ , an $(n-k)\times n$ matrix $A$ , and a vector $y$ with $n-k$ components, with the components of the latter two being elements of the finite field $\mathbb{Z}_{2}$ . Is there a vector $x$ with $n$ components in $\mathbb{Z}_{2}$ , of which at most $w$ are nonzero, with the property that $Ax=y$ ?
145. u145 This problem is called the Coset Weights problem; it appears in classical coding theory and was long ago shown to be NP-complete [58]. Since Coset Weights is NP-complete, this then would allow polynomial time solution of any size $k$ problem in the computational class NP. This is still not known to be impossible, but the very widely believed conjecture $\textsf{P}\neq\textsf{NP}$ precludes it. For a discussion of the vast support for this conjecture, see for example [61].
146. u146 4.3 Alice’s Task as Error Correction
147. u147 Having reviewed all this formalism we now see what it has to tell us about Alice’s computing task. There is a straightforward way to recast what Alice is trying to do as a quantum coding problem [3]. We can write the state (11) of the black hole as
148. u148 where
149. u149 is a basis for a $k$ dimensional subspace of $\mathcal{H}_{H}\otimes\mathcal{H}_{R}$ . We can obviously interpret this subspace as a quantum code, with encoding transformation
150. u150 Here $U_{mix,H}$ is a simple entangling transformation analogous to $U_{mix}$ from equation (33), but here entangling only the $m$ qubits of $H$ and the $n+1$ to $n+m$ th qubits of $R$ . For later convenience we will take $U_{mix,H}$ to act on each pair of qubits as
151. u151 which is not quite the transformation given by the circuit in figure 3; to implement it we need to act with an extra CNOT gate prior to the Hadamard transformation and CNOT gates in figure 3. In this language, we can think of Alice not having access to $H$ as putting this code through an erasure channel that erases all qubits in $H$ .
152. u152 This simple recasting unfortunately does not allow us to learn anything about the computational complexity of $U_{R}$ , since the state $|\Psi\rangle$ has the special property that it can be decoded just by acting with $U_{R}^{\dagger}$ . The error correction is no harder than the encoding, whose complexity we don’t know a priori. We can do better by recalling the discussion of section 3.3, where we interpreted the state $|\Psi\rangle$ as arising from the action of a polynomial size circuit $U_{dyn}$
153. u153 We’d like to interpret $U_{dyn}$ as an encoding transformation and $U_{R}$ as a correction operation, but this is not quite manifest here since $U_{dyn}$ always acts on the same state so the code space appears one dimensional whereas we’d like it to be $2^{k}$ dimensional. We can fix this by introducing an additional system $B^{\prime}$ , with the same number of qubits as $B$ , and then entangle it with $B$ by acting with a transformation $U_{mix,B^{\prime}}$ which acts as (56) on the $ith$ qubits of $B^{\prime}$ and $B$ for all $i\in 1,\ldots,k$ . We can then define a $k$ -qubit code subspace of this $2k+m+n$ qubit Hilbert space via the encoding transformation $U_{enc}\equiv U_{mix,B^{\prime}}U_{dyn}$ such that
154. u154 The errors introduced by the environment we again take to be erasures, now acting on both $B$ and $H$ . With $B$ and $H$ erased, the only way to extract $b^{\prime}$ and restore the initial state is to unscramble the entanglement between $B^{\prime}$ and $R$ , which effectively requires being able to implement $U_{R}^{\dagger}$ . More concretely, say that we have a polynomial size circuit for $U_{R}$ . We may use it to act on the state (58) with $U_{R}^{\dagger}$ . We may then act with $U_{mix,B^{\prime}}$ , now with the second element of each pair of qubits taken from the first $k$ qubits of $R$ instead of from $B$ , which we no longer have access to. This produces a state
155. u155 so we have recovered the information $b^{\prime}$ . From here we can explicitly restore the initial state in polynomial time by using ancilla to return $BHR$ to the state $|0\rangle_{BHR}$ and then using $U_{enc}$ to get back to the state (58) as desired. We may thus apply the lesson of the previous section, which is that in general doing error correction for codes with small encoding circuits requires exponential sized circuits. For stabilizer codes in the erasure channel we saw that this was not true, but there is no reason to expect that the encoding map (58) produces a stabilizer code. For more general $U_{enc}$ the only known correction procedure even in the erasure channel is the one described in the footnote at the end of section 4.1, which takes a time $2^{2l}$ where $l$ is the number of erased qubits.3031
156. u156 So far we have only discussed errors arising from Alice not having access to $B$ and $H$ . There are of course other errors that can occur, having to do with the practical difficulty of controlling the Hawking radiation. In particular an order one fraction of the radiation will be gravitons, which are very hard to detect at all, never mind coherently manipulate. It was shown long ago by Page [62] that the rate of Hawking radiation into a field of spin $s$ decreases as $s$ increases, so for Schwarzschild black holes in our universe the fraction will be small. The question of how many bits can be lost without losing the ability to error correct with high probability of success has been studied in the literature, and as discussed in the previous subsection for the erasure channel the number of bits which are lost must be less than $\frac{n-k}{2}$ . For a typical stabilizer code any smaller number of erasures can be corrected with high probability of success [42]. This will typically be true for more general codes like the one discussed here as well since they should protect information at least as well as stabilizer codes. For the channel just constructed, what was called $n$ in our general discussion of error correction is $2k+m+n$ in terms of the parameters of our black hole model, so we can lose at most $\frac{k+m+n}{2}$ bits. $k+m$ have already been lost since Alice does not have access to $B$ and $H$ , so she can lose $\frac{n-k-m}{2}$ more and still be able to error correct. Say that the fraction of the radiation which is gravitons is $\alpha$ . Since $\alpha<\frac{1}{2}$ , this means that if Alice waits long enough she can lose all of the gravitons and still be able extract the entanglement accurately with room to spare for correcting additional errors. Of course doing this error correction can be an additional source of computational hardness, which will only make it even harder to complete the decoding before the black hole evaporates. This discussion shows however that without taking into account computational complexity, the difficulty of measuring gravitons does not prevent the AMPS experiment from being done.
157. u157 4.4 Error Correction and Zero-Knowledge Proofs
158. u158 We’ve seen that the known NP-hardness results about decoding quantum error correcting codes, although suggestive, break down for technical reasons when $k$ is order one and thus unfortunately can’t be invoked directly to draw any firm conclusions about $U_{R}$ in that case. Moreover one might worry that the appearance of the NP-complete problem Coset Weights in the argument of [59] was a consequence of their particular decoding strategy; perhaps some more exotic correction procedure could somehow do the error correction without having an intermediate step that allowed solution of Coset Weights. We find this unlikely, but both of these concerns can be addressed somewhat by observing that the difficulty of implementing $U_{R}$ is actually closely related to another complexity class known as Quantum Statistical Zero-Knowledge (QSZK). The idea of a zero-knowledge proof is best explained by example.
159. u159 Consider the problem of determining whether two graphs $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ are isomorphic, that is, whether there exists a permutation $\pi$ of the vertices of $G_{2}$ turning $G_{2}$ into $G_{1}$ . There is currently no polynomial time classical or quantum algorithm known for the graph isomorphism problem. Suppose, however, that some inventive computer scientist claimed to be able to solve the graph isomorphism but jealously guarded his secret abilities. Would he be able to convince you that two $G_{1}$ and $G_{2}$ are isomorphic without revealing any information about the isomorphism? Yes! The computer scientist begins by randomly permuting the vertices of $G_{1}$ , sending you the resulting graph $G_{3}$ . At that point, you flip a coin and, depending on the outcome, challenge him to exhibit an isomorphism to either $G_{1}$ or $G_{2}$ . He will be able to succeed if the graphs really were isomorphic but will necessarily fail half the time otherwise. After a few repetitions of the process, you will become convinced of the existence of the isomorphism between $G_{1}$ and $G_{2}$ without learning anything at all about its structure.
160. u160 There are different ways to formalize the idea of a zero-knowledge proof, leading to potentially different complexity classes. The version relevant here is known as the class Statistical Zero-Knowledge (SZK) [63]. In the quantum mechanical analogue, the two participants, usually known as the prover and the verifier, would exchange qubits rather than bits, with the resulting class called QSZK [64]. There is absolutely no constraint on the computational power of the prover, but the verifier can only perform polynomial time quantum computations. Moreover, only a statistically negligible amount of information should leak from the prover to the verifier. QSZK is the set of computational problems with yes/no answers for which such a prover can always convince the verifier of yes instances but will fail with high probability for no instances. It is known that the quantum model is at least as powerful as the classical one: $\textsf{SZK}\subseteq\textsf{QSZK}$ [65]. QSZK also trivially contains BQP, the class of problems that can be solved on a quantum computer: for such problems, the verification can be done directly using the computer itself without any need for a clever discussions with a prover. QSZK should therefore be understood as the set of problems whose yes instances can be reliably identified using a quantum computer with the help of an all-powerful prover, albeit one who is both secretive and dishonest. To assert that all the problems in QSZK can be solved in quantum polynomial time, that QSZK = BQP, is to assert that the prover is ultimately no help at all.
161. u161 Given some arbitrary polynomial-sized quantum circuit $U_{dyn}$ acting on three systems $B$ , $H$ and $R$ such that $|\psi\rangle_{BHR}=U_{dyn}|000\rangle_{BHR}$ with $|\psi\rangle_{BHR}$ maximally entangled between $B$ and $HR$ , determining whether maximal entanglement with $B$ can be decoded from $R$ is a well-defined computational problem. Call it the Error Correctability problem.32 Note that Error Correctability has a quantum statistical zero-knowledge proof, which simply consists of having the prover implement the quantum error correction operation on $R$ (not caring that it might take exponential time) and having the verifier check the result. In fact, the problem of determining whether noise is correctable in this sense is complete for QSZK, meaning that any other problem in QSZK can be efficiently mapped onto a version of the error correction problem [66] (see also section 7 of [67]).
162. u162 Suppose now that, given a circuit for an arbitrary correctable $U_{dyn}$ , it were possible to efficiently find and implement the error correction procedure. In that case, the entire zero-knowledge proof for Error Correctability described above could be implemented efficiently on a quantum computer. In the case of yes instances, the procedure would produce verifiable maximal entanglement with $B$ . In the case of no instances, no such entanglement could be produced regardless of the decoding procedure attempted. Moreover, since Error Correctability is QSZK-complete, that means that every problem in QSZK could be solved on a quantum computer: being able to efficiently decode noise whenever it is correctable would imply that QSZK = BQP. (It is important to remember, however, that simply determining whether some errors are correctable could be much easier than actually correcting them.)
163. u163 Crucially, Error Correctability remains QSZK-complete even if $B$ consists of only a single qubit, unlike the NP-hardness result for stabilizer decoding discussed earlier. The question at the core of this article is whether the decoding can be performed in time polynomial in the size of the circuit for $U_{dyn}$ . We have seen that being able to do so would imply that QSZK = BQP if $U_{dyn}$ represented arbitrary correctable noise.
164. u164 Since the real $U_{dyn}$ describing black hole evaporation is very special, we could ask whether its known properties are so unusual as to undermine the argument. Specifically, for sufficiently late times, we expect maximal entanglement between $BH$ and $R$ . It is possible to a certain extent to achieve the same thing using arbitrary $|\psi\rangle_{BHR}=U_{noise}|000\rangle_{BHR}$ by simply working with $k$ copies of $|\psi\rangle$ . The resulting state $|\psi\rangle^{\otimes k}$ rapidly converges to one with near-maximal entropy concentrated in the “typical subspace” of $B^{\otimes k}H^{\otimes k}$ [68]. This property is similar to true maximal entanglement generated by $U_{dyn}$ , albeit slightly weaker.
165. u165 The conviction that $\textsf{P}\neq\textsf{NP}$ has developed over several decades of research in algorithm design and complexity theory. The belief that QSZK-complete problems cannot be solved efficiently on a quantum computer is admittedly less well-founded but does have some algorithmic and complexity theoretic support.
166. u166 Researchers have been working for twenty years on the design of efficient quantum algorithms and some problems have stubbornly resisted attack. In particular, Shor’s factoring algorithm naturally extends to an efficient quantum algorithm for the more general Abelian Hidden Subgroup problem [69]. Researchers have been trying consistently since then to attack the non-Abelian version of the problem but with only very limited success [70, 71, 72]. (Note that the non-Abelian version includes the graph isomorphism problem discussed above as a special case [73].) Large classes of strategies based on Shor’s Fourier-sampling approach are known to fail [74, 75].
167. u167 Given all the fruitless effort that has gone into trying to find an efficient quantum algorithm for solving the non-Abelian Hidden Subgroup problem, researchers have begun to suspect that no such algorithm exists. Moore, Russell and Vazirani (MRV) took one step further and defined a classical invertible function that is efficient to evaluate but hard to invert on a quantum computer under the assumption that there is no efficient quantum algorithm for non-Abelian Hidden Subgroup [76]. Their construction is easily adapted to rule out efficient quantum algorithms for decoding efficiently encoded quantum error correcting codes under the same assumption. Structurally, the function is parametrized by a list of $m$ vectors $V$ over $\mathbb{F}_{q}^{n}$ . The MRV function $f_{V}$ takes a matrix $M\in\text{GL}_{n}(\mathbb{F}_{q})$ to $MV$ , with the output returned as an unordered list. ( $m$ is selected to be only slightly larger than $n$ , which is sufficient to ensure that the function is injective with high probability.)
168. u168 Instead of returning an unordered list, however, the output vectors could equivalently be ordered but permuted by an unknown permutation $\pi$ , which can be used to define the following isometry:
169. u169 Then $(I_{B}\otimes U)$ acting on a state maximally entangled between $A$ and $B$ efficiently generates a state maximally mixed on $BH$ with the property that the purification of $B$ can be recovered by a unitary acting on $R$ alone, precisely mimicking the key properties of $\sum_{b,h}|b\rangle_{B}|h\rangle_{H}U_{R}|bh0\rangle_{R}$ . If $f_{V}$ is hard to invert on a quantum computer, however, the decoding unitary can’t be implemented in polynomial time. Under the assumption that there is no efficient algorithm for non-Abelian hidden subgroup, however, $f_{V}$ is hard to invert, even for $V$ chosen uniformly at random.
170. u170 At the level of complexity theory, there is some evidence that QSZK-complete problems cannot be solved using small quantum circuits. (An efficient quantum algorithm corresponds to a small circuit that can itself be laid out efficiently, a further requirement that should arguably be relaxed in discussions of the AMPS paradox.) It is known that determining whether a function is 1-to-1 or 2-to-1 requires exponentially many calls to the function, even for a quantum computer [77]. It is easy to construct a statistical zero-knowledge protocol for the problem, however, in the setting in which the prover knows the function and the verifier is making queries to try and distinguish the 1-to-1 and 2-to-1 cases. Since $\textsf{SZK}\subseteq\textsf{QSZK}$ , the protocol lifts to a quantum statistical zero-knowledge proof as well. In this model, therefore, an exponentially large number of queries is required to solve the problem using a quantum computer even though it has a zero-knowledge protocol. Any demonstration that QSZK has small circuits would somehow have to be reconciled with that fact, which essentially rules out any strategy which just directly transforms a zero-knowledge protocol directly into a small circuit. Instead, the demonstration would need to make essential use of some subtle internal structure of the problems contained in QSZK.33
171. u171 The conclusion of this section is that by recasting Alice’s problem as quantum error correction, we have set it into a framework where there are general arguments that such problems likely take exponential time to solve. Moreover the practical difficulties of doing the experiment, in particular the problems associated with measuring gravitons, further increase the difficulty of this computational task. We did not quite manage to prove that her task is NP-hard at fixed $k$ , but it is almost certainly at least QSZK-hard and there are strong reasons to believe that such problems can’t be solved in polynomial time on a quantum computer. From the computer science point of view, it would be extremely surprising if implementing $U_{R}^{\dagger}$ did not require exponential time.
172. u172 5 More General Black Holes
173. u173 For a Schwarzschild black hole the evaporation time scales like the entropy to the $3/2$ power, which is clearly much too fast for Alice to complete a computational task that requires time that is exponential in the entropy. In this section we consider the AMPS experiment for some more general classes of black holes.
174. u174 5.1 Schwarzschild in a Box
175. u175 In order for Alice to have any chance of doing the AMPS experiment given our claim of exponential decoding time, she will clearly need some way of slowing down the evaporation of the black hole. The simplest thing she could imagine is letting the black hole become old and then putting it inside of some sort of reflecting box to prevent it from evaporating.
176. u176 Closed finite entropy systems however behave very strangely over times of order $e^{S}$ . For example over that kind of timescale a gas of particles in a room sometimes finds itself collected up in the corner of the room, and other times find itself spontaneously assembling into a puddle of liquid on the floor. This is the phenomenon of Poincaré recurrence [22]. Indeed $e^{S}$ is sometimes called the “classical recurrence time”, to be contrasted with the “quantum recurrence time” $e^{e^{S}}$ which we encountered in section 3.1. This nomenclature is a little misleading; after all, quantum mechanics is the reason that the entropy of the gas is finite in the first place, but what it really means is the following: $e^{S}$ is the time scale over which some finite entropy quantum mechanical system will be “classically close” to an order one fraction of some orthogonal basis for its Hilbert space, up to conservation laws. In other words the probability that repeated measurements in that basis over a time of order $e^{S}$ at some point give any particular result allowed by conservation laws is order one. The significantly longer quantum recurrence time, by contrast, is the time it takes for the system to get close in the trace norm to any particular quantum state. The basic distinction here is that the number of elements in a basis of the Hilbert space is $e^{S}$ , while the number of elements in an $\epsilon$ -net of the type discussed in section 3.1 is $e^{e^{S}}$ .
177. u177 This means that it will be very difficult to confine the black hole in a box for such a long period of time. For example there is an order one probability that the black hole will produce a gigantic nuclear warhead and fire it at the side of the box. Or another black hole. The black hole will also itself crash into the box every now and then. Making the box big to try to avoid such things is not allowed because then the black hole will just evaporate into a diffuse gas of particles inside the box and there will be no black hole left when Alice finishes her computation and opens the box.
178. u178 Of course every string theorist knows how to avoid the problems with putting a black hole in a box in Minkowski space: we just put it in Anti de Sitter space! As long as the black hole is large enough the reflecting boundary of AdS space will feed its own radiation back into it fast enough to prevent it from evaporating. Of course to make the AMPS argument at all we need the black hole to become maximally entangled with some external system, so following a suggestion of Don Marolf we imagine this is done by mining the black hole down to less than half of its initial entropy.34 But this setup brings with it a new problem; we now need to put Alice, her mining equipment, and her computer in the box as well! Since the calculation still takes of order the recurrence time, this means that both Alice and her assorted paraphernalia now need to be resistant to nuclear warheads/mini black holes/etc. Alice could try to avoid this by staying very far away from the black hole, namely exponentially near the boundary, so that from her point of view the recurrences become effectively low energy enough not to affect her. In doing so however she will be fighting against an effective potential pulling her back to the center. To do this for enough time to accomplish the computation would require exponentially large amounts of rocket fuel, and the exhaust from burning all that fuel would fall back into the black hole anyway and pollute her experiment. Trying to use angular momentum to stabilize her orbit would not work because over such long time scales her orbit would rapidly decay via gravitational radiation.
179. u179 In fact there is a way to avoid these problems as well, which was suggested to us by Juan Maldacena. It involves putting a big AdS black hole in a throat geometry where the near horizon region is asymptotically AdS but there is also an asymptotically Minkowski region. In this way the geometry provides a box with the benefits of both the Minkowski box and the AdS box without the problems of either. There is still a problem with this setup, but it is more subtle and we return to it later in this section.
180. u180 5.2 Reissner-Nordstrom
181. u181 Another way Alice could try to extend the lifetime of her black hole is by giving it some charge. The Reissner-Nordstrom black hole of mass $M$ and charge $Q$ has metric
182. u182 where
183. u183 and
184. u184 Its entropy is
185. u185 and its temperature is
186. u186 We see when $M\ell_{P}=Q$ , the black hole is extremal and the temperature is zero. If we start the black hole with mass above extremality, it will radiate and gradually approach extremality. The relevant point here is that as it does this, the temperature decreases and semiclassically it appears that the decay takes an infinite amount of time. More precisely if we define the energy above extremality to be
187. u187 the energy-temperature relation is
188. u188 and a simple calculation tells us that, for a black hole which starts with energy $E_{0}\leq Q\ell_{p}^{-1}$ , we have
189. u189 Here $\alpha$ is some order one numerical constant. Thus it appears that the black hole takes an infinite amount of time to reach extremality. There is a well-known problem with this argument however [20, 21], which is that from (67) we see that when the temperature reaches
190. u190 the remaining energy $E$ above extremality is no longer bigger than the temperature $T$ . At this point the semiclassical description of the evaporation process breaks down, and quantum gravity is necessary to understand what happens next. This is related to an instability of $AdS_{2}$ called fragmentation [21], and in the cases where it can be understood in string theory it is always true that the geometry breaks apart into something that has little resemblance to the original Reissner-Nordstrom geometry.
191. u191 It is easy to see that no matter whether we start with $E$ near extremality or much larger, this instability always sets in well before the exponential of the initial entropy. For example, say that we start with $E_{0}\leq Q$ (setting $\ell_{p}=1$ ). The initial entropy is of order $Q^{2}$ , while the time to reach the instability is of order $Q^{7}$ . Alternatively if we start with $E_{0}\gg Q$ then we are back to the Schwarzschild situation where evaporating back down to $E\approx Q\ell_{P}^{-1}$ takes a time of order $E_{0}^{3}\approx S_{0}^{3/2}$ , and the additional time to get down to the instability is $Q^{7}\ll S_{0}^{7/2}$ . The total evaporation time is always bounded by a polynomial in $S_{0}$ . Thus charged black holes, near extremal or otherwise, are of no use to Alice.
192. u192 5.3 Near Extremal AdS Throat
193. u193 Recall the $AdS_{d}$ Schwarzschild geometry
194. u194 with
195. u195 A scalar field on this background feels an effective potential. In particular if we look for solutions of the Klein-Gordon equation of the form
196. u196 it is not hard to see that $\Psi_{\omega\ell}$ must obey a Schrodinger-type equation
197. u197 Here $r_{*}$ is a “tortoise” type coordinate obeying
198. u198 and the effective potential is
199. u199 The details of this potential do not matter, but we see that it vanishes linearly at the only real positive root of $f(r)$ , that is at the horizon, and that it grows quadratically with $r$ at large $r$ . Near the horizon the solution then behaves as $\Psi_{\omega\ell}\sim e^{i\omega(\pm r_{*}-t)}$ , while at large $r$ we have $\phi\sim r^{-\Delta_{\pm}}$ with the usual AdS/CFT formula
200. u200 The idea of this section is to cut off this geometry at some large value of $r$ and sew it onto Minkowski space, after which the effective potential (75) would go back to zero provided we set the scalar field mass $m^{2}$ to zero. The black hole would then be able to decay via massless quanta tunneling out of this potential into the Minkowski region, and by choosing the crossover value of $r$ to be large we could adjust the decay time independently of the entropy of the black hole. We can also “outsource” the computation by putting the computer out in the Minkowski region, which allows us to buy a large redshift factor enhancement in the time it takes to do the computation from the point of view of Alice living down by the black hole.
201. u201 There is a new problem with this construction however, which is that any attempt to send the result of the computation from the Minkowski region back down the throat to the vicinity of the black hole has to get back through the potential barrier. The signal the computer sends down the throat will need to be very low energy, so its absorption probability will be exponentially small. Nonetheless one could imagine trying to send the signal repeatedly, hoping that eventually one of the times it will get through. This approach gets much harder as the size of the signal we wish to send increases, but unlike the previous examples it is not obvious that it cannot be done and we need to analyze it more carefully.
202. u202 5.3.1 The Brane Setup
203. u203 To quantitatively test the feasibility of using a throat to evade the computational hardness of decoding, we need a specific example of this type of geometry. In string theory there is a standard way of producing throat geometries with the desired properties by stacking branes; for example D3 branes in type IIB string theory or M5 branes in M-theory. To realize the geometry (70) explicitly we would need a configuration of branes which is spherically symmetric and stable. Spherical symmetry is a bit inconvenient because branes in spherical configurations tend to collapse under their own tension unless there is something else supporting them. A simple thing we could do is start with the $AdS_{3}\times S^{3}\times T^{4}$ solution of IIB supergravity with RR flux, itself the near horizon limit of the $D1-D5$ system, and then wrap some $D3$ branes on the $S^{3}$ . This throat would not be asymptotically Minkowski, but we could easily arrange for the curvature radius of the $AdS_{3}$ to be much larger than the curvature radius of the $AdS_{5}$ near the $D3$ branes. Rather than try to make this construction work in detail, we will instead consider a simpler setup in which the black hole has planar symmetry instead of spherical symmetry.
204. u204 One of the best-known solutions of ten-dimensional IIB supergravity is the extremal planar black 3-brane [80], with metric
205. u205 Here
206. u206 and $R$ is a parameter of the solution. The string theory interpretation of this solution is that it gives the backreacted geometry in the presence of $N$ D3 branes, with
207. u207 where $g$ is the string coupling, $\ell_{s}$ is the string length, and $\ell_{p}$ is the ten-dimensional Planck length. By looking at $Z(r)$ we see that this geometry indeed has the property that for $r\ll R$ it behaves like $AdS_{5}$ in Poincaré coordinates, times an extra $S^{5}$ of constant radius, while for $r\gg R$ it becomes ten dimensional Minkowski space.
208. u208 To get something like a black hole down the throat we need to put this solution at finite temperature, and to get the entropy to be finite we need to compactify the spatial $\vec{x}$ directions. Although it will not be explicit in our equations, we will choose anti-periodic boundary conditions for the fermions around the compact dimensions.35 To add some temperature we just need to consider the non-extremal version of the solution [81]:
209. u209 where $Z(r)$ is now
210. u210 with
211. u211 and
212. u212 To put the black hole far down the throat we clearly want $\frac{r_{0}}{R}\ll 1$ , and in this limit the entropy of the black hole is
213. u213 and the temperature is
214. u214 Here $\Omega_{5}$ is the volume of a unit $\mathbb{S}^{5}$ and $L$ is the periodicity of the $\vec{x}$ directions. In the same limit the ADM energy 36 is
215. u215 One can check that when $r_{0}\to 0$ this reproduces the correct D3-brane tension. The energy above extremality is
216. u216 It is straightforward to check that the instability encountered in Reissner-Nordstrom does not happen here; in fact we have
217. u217 so the energy will be bigger than the temperature until the black hole has Planckian area. We may then worry that the black hole evaporation time is independent of the intial entropy, as we worried with Reissner-Nordstrom, but there is now a new phenomenon which comes to the rescue.
218. u218 5.3.2 Hawking-Page Transition for Toroidal Black Holes
219. u219 For spherical black holes in AdS with metric (70), it is well known [83, 84] that for small enough values of $\alpha$ the black hole is unstable to decay by Hawking radiation. The crossover point is when the temperature is of order $R^{-1}$ .37 This phenomenon provides a natural endpoint for the type of decay we discussed in the previous section; the black hole will very slowly radiate energy up the throat and into Minkowski space until it reaches the critical temperature, after which it will decay essentially immediately into low energy quanta in the AdS-region of the throat. Does something similar occur for our toroidal black hole as well? The answer is yes, but as we now describe the analysis has a few details that differ from the spherical case. This transition has been previously discussed by [85].
220. u220 Far down the throat, our geometry becomes a compactified version of a general solution called a black AdS brane. In $AdS_{d}$ the metric for this solution is38
221. u221 with
222. u222 In the spherical case the action of the Euclidean version of the solution (70) can be compared to the action of another Euclidean solution which has the form (70) again but with $\alpha=0$ . In both cases the Euclidean time $\tau=it$ is compactified. The competition between these two solutions is the source of the Hawking-Page transition. In the toroidal setting there is an analogous construction of a second solution, where we set $\alpha=0$ , but it turns out always be subdominant to the black brane solution (89). There is another solution however with the same boundary conditions; we can take the “emblackening factor” $f(r)$ and move it from in front of $-dt^{2}$ to one of the planar coordinates:39
223. u223 This geometry is sometimes called the AdS Soliton. It has no region behind the “horizon” at $r=r_{0}$ , instead it caps off smoothly provided that we choose the correct value of $r_{0}$ as a function of the periodicity $L$ . When we continue to Euclidean time we can set the $\tau$ periodicity of the AdS soliton (91) freely, but for the black brane (89) we must choose $r_{0}$ to be consistent with the $\tau$ periodicity for the Euclidean geometry to be smooth. An important subtlety is that for a given periodicity of the circle at the boundary, the correct value of $r_{0}$ and also the coordinate periodicity of $\tau$ are different in the two solutions.40 The Euclidean action is
224. u224 where $\gamma$ is the determinant of the induced metric at the boundary and $K$ is the trace of the extrinsic curvature. Making the action finite involves cutting off the geometry at some large $r=r_{c}$ , and then carefully matching the boundary geometry on the regulator surface in the two cases. We will not present the details explicitly here since they are fairly standard in the literature. (See [84, 86] for examples.) The result is that the finite parts of the actions are
225. u225 for the black brane and
226. u226 for the AdS soliton. Thus at high temperatures compared to $L^{-1}$ the black brane wins while at low temperatures the AdS soliton wins. This then is the effect that we want; as the black hole radiates it will eventually undergo a transition to some other type of geometry with no horizon and Alice will no longer be able to test AMPS. The dual field theory interpretation of this is clear; it is the same large $N$ phase transition as in the spherical case, just studied with different spatial topology.41
227. u227 5.3.3 Time Scales
228. u228 In this section we work out the time scales for sending signals down the throat from the Minkowski region to the vicinity of the black hole horizon at $r_{0}$ in (80), as well as the time to evaporate down to the transition temperature just discussed in the previous section. Since we will ultimately compare these time scales to the computation and recurrence times, both of which are exponential in the entropy of the black hole, we will be focused on extracting only the pieces of them which are exponential in entropy. Specifically we will write $S_{0}$ to mean the entropy of the black hole just after the Page time, so that it is also roughly the size of the radiation and one half of the entropy of the original black hole. If we had started the computer any later it would just have made the task more difficult, and we want to give Alice a fair shot.
229. u229 We will see shortly that for the decay to be slow enough for Alice to have a chance at computing, we will need the temperature to be exponentially small in the entropy, perhaps with some coefficient in front of $S_{0}$ in the exponent. From equation (85) this means we will need $r_{0}$ to be exponentially small. From equation (84) we see that to keep the entropy fixed in the same limit we will need $L$ to be exponentially large such that $Lr_{0}$ is fixed. Looking at (87) we see that the energy above extremality will then be exponentially small througout the decay process. Having fixed $S_{0}$ we can also derive an interesting bound on the AdS radius $R$ in Planck units: we know that we must have $T>L^{-1}$ to avoid starting the computation below the phase transition discussed in the previous section, so we must have
230. u230 Thus the AdS radius in Planck units is bounded by a polynomial in $S_{0}$ and we can neglect it in most equations.
231. u231 To understand how hard it is to send some particular quanta down the throat, we need to compute its absorption probability $P_{abs}$ . This probability will be a function of the frequency $\omega$ of the quanta of interest, and in the limit $\omega R\ll 1$ it can often be computed analytically [87]. For massless scalars in the extremal black three brane (77) this problem was studied by Klebanov in [88].42 A simple generalization of his result shows that for quanta with frequency $\omega$ , angular quantum number $\ell$ on the $\mathbb{S}^{5}$ , and momentum $k$ in the planar direction, the absorption probability is
232. u232 In sending signals down the throat, we need to use low enough energy to avoid our signals backreacting significantly on the throat. Certainly a necessary condition is that we need $\omega<E$ , and looking at (88) this means we need $\omega\sim T$ up to a power of the entropy, which as usual we ignore. This means that we must use quanta of exponentially low energy to send any messages; the absorption probability (96) will thus be exponentially small. It is still possible to send a message, but we must try many times. Since it takes an energy $\omega^{-1}$ just to produce a message of energy $\omega$ , to have any chance of success sending the message we need a time of order
233. u233 Clearly we have the best chance of sending a message using scalars if we set $k=\ell=0$ . Other types of communication will have different absorption probabilities. For example, we show in appendix A that the absorption probability for sending messages down a string threading the throat by moving the string along the $\mathcal{S}^{5}$ is proportional to $(\omega R)^{2}$ . Apparently this is a better method of communication than the massless scalar, although we will see it is still not good enough to be of use to Alice.43 In general we will parametrize low-energy absorption probabilities as
234. u234 so neglecting all factors polynomial in $S_{0}$ we can estimate
235. u235 The units here are provided either by powers of $\ell_{p}$ or $R$ , it doesn’t much matter. To be concrete we can evaluate the temperature at the same time that we defined $S_{0}$ , which was just after the Page time.
236. u236 Absorption probabilities are also important in understanding how long it takes for the black hole to evaporate. As Hawking showed in his original paper [89] the energy flux out of a black hole is
237. u237 where the sum on $n$ is over different modes. It is often the case that only a particular mode contributes significantly, for example for Schwarzschild black holes it is only the $\ell=0$ mode. The low energy absorption cross section for Schwarzschild is proportional to $(2GM\omega)^{2}$ , from which one can use (100) to motivate the usual “Stefan-Boltzmann” assumption for the decay rate. In that case the low energy approximation breaks down before the peak of the integrand and numerical analysis is necessary to compute the prefactor correctly [62], but for us the temperature is very low compared to $R^{-1}$ so using the low energy approximation for $P_{abs}$ throughout is justified. The intuition of (100) is quite simple; the thermal factor is just the expected occupation number of the near horizon modes, and by a basic fact about one-dimensional scattering theory the probability of absorption in from the outside is the same as the probability of transmission out from the inside.
238. u238 For the absorption probability (96) the decay is dominated by $\ell=0$ modes, but it is necessary to include modes of low but finite $k$ . Roughly $k$ is quantized in units of $1/L$ , and since we are interested in the region where $TL\gg 1$ we will have $\omega\gg L^{-1}$ . We can then convert the sum over discrete modes into an integral over $k$ and write
239. u239 More generally we can write
240. u240 where the parameter $b$ is the same as in (98) and the parameter $a$ accounts the phenomenon just encountered for the scalar. For the string we discuss in appendix A we have $a=0$ , $b=2$ .
241. u241 To find the evaporation time we need to integrate (102) to find the energy as a function of time. As the decay proceeds $L$ cannot change because it is fixed by the boundary conditions at $r\to\infty$ , so it will be $r_{0}$ that gradually decreases. We integrate from initial energy $E=S_{0}T$ down to final energy $E=\left(\frac{R}{\ell_{p}}\right)^{8}L^{-1}$ . The details of the integral depend on whether $a+b-2$ is positive, negative, or zero, but the final power of $T$ does not. Indeed we find
242. u242 where again we can make up the dimensions with either $R$ or $\ell_{p}$ without affecting the exponent in the entropy. By comparing (103) to (99) we see that the evaporation time is always the same order in $T$ as is the time to send any signal at all!44 Which one is bigger depends on the prefactors we omitted, but there are definitely cases where $t_{msg}<t_{evap}$ so this fact by itself, although certainly troubling, is not enough to kill the experiment.
243. u243 In section 3.2 we argued that Alice’s quantum computation takes a time of order $e^{2S_{0}}$ .45 For now we will be a little more general and write this as
244. u244 The recurrence time is basically $e^{S_{0}}$ , but we need to include a red-shift factor to account for the extremely low energy of the states involved in the recurrences. Thus
245. u245 With these estimates we are finally in a position to assess the viability of Alice’s experiment. For the computation to finish before the black hole evaporates we need $t_{comp}<t_{evap}$ , which implies
246. u246 This confirms our earlier claim that the temperature needs to be exponentially small in the entropy. To be able to send a message down the throat in less than a recurrence time we need $t_{msg}<t_{rec}$ , which implies
247. u247 The condition that $t_{comp}<t_{rec}$ gives
248. u248 It is straightforward to see that all three of these can be satisfied only if
249. u249 In the text we saw that if $U_{R}$ is completely general then $\alpha=2$ , in which case the experiment can be done only if $b<1$ . Neither the string nor the free scalar field are close to this, and actually there is a simple argument that no scalar field of any kind can satisfy this inequality. The coefficient $b$ in the absorption factor is related to the conformal dimension of the operator that the scalar couples to in the CFT dual as $b=2\Delta$ [90], so the unitarity bound $\Delta>1$ in four dimensions precludes $b<2$ . A similar argument can perhaps be constructed for the defect operators that couple to the ends of general strings but we have not tried to do so.
250. u250 It is interesting that were the computer able to decrease $\alpha$ it would make it easier to satisfy these inequalities. In fact we don’t see any particular reason why improved algorithms shouldn’t be able to use special features of the black hole dynamics to decrease $\alpha$ by some order one factor. If $\alpha$ could be decreased below $3/2$ , the string might become an effective method for communicating down the throat. We stress however that this is not sufficient for doing the AMPS experiment, it is only necessary. For one thing even if the “true” $\alpha$ could be decreased by algorithms, our discussion below equation (10) suggests that, because of coarse-graining, $\alpha$ should be increased by some order one factor. More significantly, being able to send one piece of classical information is not enough to do the strongest version of the AMPS experiment. That requires us to send a particular quantum state which purifies $B$ . Preserving the coherence of this state would presumably require some sort of apparatus (also made out of fluctuations on the string) which would also have to make it through the barrier, and even without the apparatus we probably want $k$ to be at least a little bit bigger than one to be able to build up any kind of statistics. Getting all of these things to make it through the barrier at once probably requires us to raise $t_{msg}$ by some order one power, which would help compensate for an $\alpha$ that has been decreased by clever algorithms. Even this is not enough however; the purification of $B$ is more likely to be partially reflected than to get all the way through, which means that it will be partially reflected many times before most of it gets through. In fact getting slightly more than half of it through is enough since somebody living down the throat can do error correction to restore the other half, but each time that more than half of it is reflected the person outside will need to do error correction before trying to send it again. This will usually succeed, but there is a small $S_{0}$ -independent probability it will fail. Since we need the correction procedure to work every time in order to continue sending the correct state, this means that eventually it will fail. For these reasons we are quite confident that the “strong” AMPS experiment where Alice carries the purification of the black hole in with her can’t be done in this setup.
251. u251 There is a weaker version of the AMPS experiment where the state of $R_{B}$ is measured out in the Minkowski region at the end of the quantum computation and what is sent down the throat to Alice is just a classical record of the result of that measurement. This would be sufficient, for example, to implement a Bell inequality test using the state entangled between $B$ and $R_{B}$ . Because classical information can be cloned, sending the record of the measurement outcome to Alice is easier than sending $R_{B}$ itself; she doesn’t have to worry about error correction and she can send multiple copies at once. Sending exponentially many copies of the information down the throat at once is dangerous from a back-reaction point of view however. For example, to do this using strings would require an exponential number of strings, all parallel and located at different values of $x$ , which would become extremely dense down the throat; the distances between the strings would become exponentially sub-Planckian. For massless scalars the total number of modes we can use without backreaction is, at the level of exponential factors, of order $(LT)^{3}$ . Since $L\sim T^{-1}$ , using all of these modes at once is of no help in trying to beat the exponential in $t_{msg}$ .
252. u252 Given the possibility of $\alpha<2$ we are not decisively able to rule out this ‘weak’’ AMPS experiment, but at a minimum we are comfortable interpreting this section as casting serious doubt on the feasibility of using an AdS throat to facilitate an AMPS experiment.46
253. u253 6 The Structure of the Hilbert Space
254. u254 The main argument of this paper is now complete, and although the paper is already long, we can’t resist making a few comments about the possible implications of our results for how to think about the interior of a black hole. In the introduction we briefly discussed two alternatives, “strong complementarity” and “standard complementarity”, for how to think about Alice the infalling observer’s quantum mechanics. It is very important to decide which, if either, of these frameworks is the correct way to think about black hole interiors. In this section we assess the status of each in turn in light of our computational arguments. This section has substantial overlap with a paper by Susskind [91] appearing simultaneously with this one, and which explains some of these ideas in more detail.
255. u255 The least restrictive idea for how to think about Alice is to imagine that she has her own quantum mechanics, possibly approximate since she encounters a singularity later, which is a priori independent of the quantum mechanics of an observer at infinity like Charlie. This type of theory has been argued for by Banks and Fischler for a while, who attempt to realize it precisely as quantum mechanics with no approximations for anybody, in a formalism called “holographic spacetime” [10, 11]. The basic idea will be discussed using as illustration figure 1 above. In this framework it seems necessary for consistency [14, 15] for Alice and Charlie to agree about the results of measurements in the green region of the figure. It is fairly clear in this setup that if Alice indeed cannot decode the radiation before jumping in, we are free to change her state in a way that produces no observable contradiction with the fact that Charlie, who is able to decode, will later conclude that that $R_{B}$ was entangled with $B$ . Charlie, not having access to the degrees of freedom behind the horizon, will not be able to check that $B$ is entangled with $A$ . Moreover a previous objection to strong complementarity [1], that it required some sort of discontinuity in the experiences of a sequence of observers who jump in at different times, is not relevant since the only thing that determines whether or not $R_{B}$ can be decoded is whether or not the observer ever falls in. So Alice’s inability to decode apparently to allows strong complementarity to be consistent without firewalls.
256. u256 Although strong complementarity is in some sense straightforward, it is rather unsatisfying. Each observer having her own description of the universe, approximate or not according to taste, and with no clear precise relationship between them, seems to us like a rather inelegant fundamental framework. In particular it is to be contrasted with AdS/CFT [45, 46, 92], where there is a single Hilbert space and set of operators which is conventionally understood to describe all of the physics in AdS space within a single sharp framework. It would be reassuring if strong complementarity could be set into such a framework, in which its ambiguities would be understood as arising from measurements that are not precisely well-defined. Without such an embedding, it would seem like strong complementarity would amount to a step backwards; even in AdS space the CFT would not be a complete description of the physics of an infalling observer.47 As we discussed above this embedding has been called $A=R_{B}$ in the context of firewalls; in the remainder of this section we sketch a basic proposal for how it could work more precisely.
257. u257 We imagine that there is a single Hilbert space $\mathcal{H}$ , which we will think of as the CFT Hilbert space in an AdS setup to be concrete. To understand Charlie’s physics on some spatial slice like the black one in figure 1, we need to compute expectation values of some set of operators $C_{n}$ , which approximately commute.48 Indeed there is a fairly well-known construction [51] for constructing these operators in some cases, which we illustrate in figure 6.
258. u258 Figure 6: The construction of bulk operators by Kabat, Lifschytz, and Lowe for an AdS black hole. Here the yellow region is a lightcone ending on the operator and extending out to the boundary, and the operator is constructed by integrating a CFT operator over the boundary of the yellow region against a kernel that depends on the position of the operator. Note that as the operator approaches the horizon the operator becomes sensitive to the entire history on the boundary and thus to the details of the quantum state.
259. u259 Our proposal for the interior is then that there is another set of operators, which we will call $A_{n}$ ’s, which are also mutually commuting with each other and whose expectation values in the same (Heisenberg picture) state used by Charlie describe Alice’s experience on the red slice in figure 1. Some of the $A_{n}$ ’s are interpreted by Alice as being outside the horizon, and she can also try to construct them using the method of [51]. Consistency then requires that these $A_{n}$ ’s are equal to the appropriate $C_{n}$ ’s to prevent disagreement between Alice and Charlie about events in the green region of figure 1. Others of the $A_{n}$ ’s are interpreted by Alice as being behind the horizon and, as shown in the figure the construction of [51], breaks down in that case. These $A_{n}$ ’s naively do not seem to have low energy interpretations for Charlie. From the AMPS argument however we know that to have a smooth horizon it must be that there are some operators just outside the horizon, which act on what we’ve been calling $B$ , measurements of which need to be close to perfectly correlated measurements of some of the behind-the-horizon $A_{n}$ ’s. Before the Page time, none of Charlie’s $C_{n}$ ’s are expected to have this correlation with the $B$ operators, and as recently argued by Susskind, Verlinde, and Verlinde [18, 52] Charlie can then interpret the $A_{n}$ ’s as just being some complicated mess acting on the remaining black hole. After the Page time, however, Charlie expects the operators acting on $B$ to be perfectly correlated with nonlocal $C_{n}$ ’s acting on what we’ve called $R_{B}$ in the radiation. So it must be that from Charlie’s point of view the appropriate $A_{n}$ ’s now act on the complicated subfactor of the radiation which purifies $B$ . Hence the name $A=R_{B}$ . This clearly is rather nonlocal, but as shown in the figure the breakdown of the construction of [51] suggests that the construction of operators behind the horizon does indeed depend on sensitive details of the state.
260. u260 This idea is very confusing to interpret however if Alice is able to decode the Hawking radiation, because she then has two low energy observables which she wants to identify with the same quantum mechanical operator on the same Hilbert space. This is sometimes called cloning, although it isn’t really because the theory is quantum mechanical and thus doesn’t clone, but it seems like a rather serious problem for the physical interpretation of quantum mechanics. By doing low-energy manipulations of the Hawking radiation Alice would be able to construct a situation where looking at some localized piece of the Hawking radiation far from the black hole is indistinguishable from looking behind the horizon. At a minimum this type of observable bizarreness would allow acausal communication, and in any event it doesn’t seem particularly less crazy than the idea that there is a firewall. In the context of the discussion of this paper however, if Alice in principle cannot decode $R_{B}$ then there does not seem to be any such problem with interpreting $A_{n}$ as being behind the horizon from Alice’s point of view and out in the radiation from Charlie’s point of view. This is something like strong complementarity, but now realized in a single quantum theory.
261. u261 Acknowledgements
262. u262 We have benefited enormously from discussions with many people about firewalls. In particular Juan Maldacena was of invaluable help in discussing many aspects of this work from its inception to its completion. We are also grateful Igor Klebanov for technical assistance with the brane setup and Joe Polchinski for suggesting using strings and in general being a good sport. We additionally thank Scott Aaronson, Nima Arkani-Hamed, Tom Banks, Alex Belin, Adam Brown, Raphael Bousso, Borun Chowdhury, Xi Dong, Liam Fitzpatrick, Ben Freivogel, Daniel Gottesman, Tom Hartman, Simeon Hellerman, Jared Kaplan, Don Marolf, Alex Maloney, Jonathan Maltz, Jonathan Oppenheim, Don Page, Kyriakos Papadodimas, Greg Prisament, Suvrat Raju, Grant Salton, Steve Shenker, Eva Silverstein, Douglas Stanford, Leonard Susskind, Brian Swingle, Erik Verlinde, Herman Verlinde, John Watrous, Edward Witten and all of the participants of the Stanford Firewall Alert meeting for providing a stimulating and chaotic environment for discussing the ideas in this paper and many others as well. Finally we both especially thank John Preskill, to whom we dedicate this paper on his 60th birthday. DH spent several months at the beginning of this project studying John’s excellent lecture notes, without which he would have been able to contribute little. DH is supported by the Princeton Center for Theoretical Science. PH is supported by the Canada Research Chairs program, the Perimeter Institute, CIFAR, NSERC and ONR through grant N000140811249. The Perimeter Institute is supported by Industry Canada and Ontario’s Ministry of Economic Development & Innovation.
263. u263 Appendix A The Absorption Probability for a Nambu-Goto String
264. u264 In this section we compute the low-energy absorption probability for transverse oscillations of a string stretching down the extremal black three brane geometry (77). This has been previously been computed by Maldacena and Callan [93]; our method is the same as in [88] for a massless scalar. The Nambu-Goto action is
265. u265 and parametrizing the string in static gauge and considering only oscillations in the $\mathbb{S}^{5}$ direction we have
266. u266 Linearizing the action in $\theta$ we find
267. u267 and looking at modes of definite frequency $\omega$ the equation of motion is
268. u268 Defining $\rho=\omega\sigma$ , the equation becomes
269. u269 For $\rho\gg\omega R$ the solution is approximately
270. u270 while for $\rho\ll\omega R$ the solution is approximately
271. u271 When $\omega R\ll 1$ we can also find an approximate solution for $(\omega R)^{4/3}\ll\rho\ll 1$ by keeping only the derivative terms in (113):
272. u272 Since this range overlaps with the other two ranges, we can use this solution to connect them together. Since we are computing an absorption probability we want $\tilde{B}=0$ , which means that matching the two “inner” regions gives
273. u273 Matching the “outer” two regions gives
274. u274 so when $\omega R\ll 1$ we have
275. u275 Finally to compute the absorption probability we inspect equations (114) and (115), switching back from $\rho$ to $r$ , and compute the square of the ratio of the coefficients of the waves. The result is
276. u276 consistent with [93]. One could also study oscillations along the brane direction, according to [94] these give an absorption probability proportional to $(\omega R)^{4}$ .