Quantum computation vs. firewalls
Open accessThe DOI matches its Crossref record; 81 of the 81 references it cites were found in a registry or an index.
Abstract
A bstractIn 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 black hole evaporation or the ability of advanced civilizations to test it.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“In fact, for evaporating black holes, there is good reason to think that it is exponentially complicated [65,66].”
From Replica wormholes and the black hole interior (2022) · cites this paper as [65]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Essentially this argument states that in order to distill the factor E R from E needed to purify R, it would take time which is exponential in the entropy of the black hole (at the time when R was emitted).”
From Holographic spacetime, black holes and quantum error correcting codes: a review (2022) · cites this paper as [256]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“A simple way to resolve this paradox is to invoke the philosophy of black hole complementarity [254,255] which postulates that the violation cannot be observed operationally via a quantum complexity conjecture due to Harlow and Hayden [256]”
From Holographic spacetime, black holes and quantum error correcting codes: a review (2022) · cites this paper as [256]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The large $N$ limit of superconformal field theories and supergravity
Maldacena, J. (1998) · Advances in Theoretical and Mathematical Physics · doi:10.4310/atmp.1998.v2.n2.a1 · Cited by 14,524
Particle creation by black holes
Hawking, S. W. (1975) · Communications In Mathematical Physics · doi:10.1007/bf02345020 · Cited by 13,106 · cited 1×
“As Hawking showed in his original paper [84] the energy flux out of a black hole is”
BackgroundAnti de Sitter space and holography
Witten, E. (1998) · Advances in Theoretical and Mathematical Physics · doi:10.4310/atmp.1998.v2.n2.a2 · Cited by 13,070 · cited 5×
“Near the horizon the solution then behaves as Ψω` ∼ eiω(±r∗−t), while at large r we have φ ∼ r−∆± with the usual AdS/CFT formula ∆± = d− 1 2 ± 1 2 √ (d− 1)2 + 4R2m2.”
MethodInfluentialGauge theory correlators from non-critical string theory
Gubser, S. S., Klebanov, I. R., & Polyakov, A. M. (1998) · Physics Letters B · doi:10.1016/s0370-2693(98)00377-3 · Cited by 9,307 · cited 5×
“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 [24, 45, 46] the dynamics are always some matrix quantum mechanics or matrix field theory.”
MethodInfluentialGauge Theory Correlators from Non-Critical String Theory
Gubser, S. S., Klebanov, I. R., & Polyakov, A. M. (1998) · arXiv · doi:10.48550/arxiv.hep-th/9802109 · Cited by 9,307 · cited 1×
“ise relationship between them seems to us like a rather inelegant fundamental framework. To quote Douglas Stanford it seems like \making it up". In particular it is to be contrasted with AdS/CFT [27,28,69], where there is a single Hilbert space and set of operators which is conventionally understood to describe a…”
BackgroundQuantum Computation and Quantum Information: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2012) · doi:10.1017/cbo9780511976667 · Cited by 8,436
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Mixed-state entanglement and quantum error correction
Bennett, C. H., DiVincenzo, D. P., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review A · doi:10.1103/physreva.54.3824 · Cited by 5,272 · cited 1×
“In this language there is a necessary and sufficient condition for when exact error correction is possible for a given code [49, 50].”
BackgroundScheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479 · cited 13×
“In the Shor code the code subspace is spanned by the states |±〉.”
InfluentialAnti-de Sitter space, thermal phase transition, and confinement in gauge theories
Witten, E. (1998) · Advances in Theoretical and Mathematical Physics · doi:10.4310/atmp.1998.v2.n3.a3 · Cited by 3,915
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285 · cited 18×
“Even for fixed k, however, the decoding problem 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.”
BackgroundInfluentialLloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088
Thermodynamics of black holes in anti-de Sitter space
Hawking, S. W., & Page, D. N. (1983) · Communications in Mathematical Physics · doi:10.1007/bf01208266 · Cited by 3,045 · cited 1×
“10), it is well known [78, 79] that for small enough values of α the black hole is unstable to decay by Hawking radiation.”
BackgroundM Theory As A Matrix Model: A Conjecture
Banks, T., Fischler, W., Shenker, S. H., & Susskind, L. (1996) · arXiv · doi:10.48550/arxiv.hep-th/9610043 · Cited by 2,748 · cited 1×
“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 [37] or AdS/CFT [38–40] the dynamics are always some matrix quantum mechanics or matrix field theory.”
BackgroundM theory as a matrix model: A conjecture
Banks, T., Fischler, W., Shenker, S. H., & Susskind, L. (1997) · Physical Review D · doi:10.1103/physrevd.55.5112 · Cited by 2,748 · cited 1×
“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 [24, 45, 46] the dynamics are always some matrix quantum mechanics or matrix”
BackgroundStates, Effects, and Operations Fundamental Notions of Quantum Theory
(1983) · Lecture Notes in Physics · doi:10.1007/3-540-12732-1 · Cited by 1,928
Theory of quantum error-correcting codes
Knill, E., & Laflamme, R. (1997) · Physical Review A · doi:10.1103/physreva.55.900 · Cited by 1,593
Average entropy of a subsystem
Page, D. N. (1993) · Physical Review Letters · doi:10.1103/physrevlett.71.1291 · Cited by 1,578 · cited 1×
“Page’s theorem [30] then suggests that the combined system BH has a density operator which is close to being”
BackgroundAverage Entropy of a Subsystem
Page, D. N. (1993) · arXiv · doi:10.48550/arxiv.gr-qc/9305007 · Cited by 1,578 · cited 1×
“Page’s theorem [30] then suggests that the combined system BH has a density operator which is close to being”
BackgroundEternal black holes in anti-de Sitter
Maldacena, J. (2003) · Journal of High Energy Physics · doi:10.1088/1126-6708/2003/04/021 · Cited by 1,555 · cited 1×
“Its gravity dual is two CFT’s which are entangled in just the way that seems necessary to produce a smooth horizon [40].”
BackgroundOn the inherent intractability of certain coding problems (Corresp.)
Berlekamp, E., McEliece, R., & van Tilborg, H. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055873 · Cited by 1,523
Black Holes: Complementarity or Firewalls?
Almheiri, A., Marolf, D., Polchinski, J., & Sully, J. (2012) · arXiv · doi:10.48550/arxiv.1207.3123 · Cited by 1,471 · cited 5×
“the black hole dynamics between the near-horizon eld theory modes and the horizon degrees of freedom. Such a decopuling seems rather implausible, especially in the context of the mining operations of [1,13]. 9In [15] one of us tried to argue, for a reason having nothing to do with computation, that the experiment cann…”
BackgroundResultInfluentialBlack holes: complementarity or firewalls?
Almheiri, A., Marolf, D., Polchinski, J., & Sully, J. (2013) · Journal of High Energy Physics · doi:10.1007/jhep02(2013)062 · Cited by 1,470 · cited 5×
“the black hole dynamics between the near-horizon eld theory modes and the horizon degrees of freedom. Such a decopuling seems rather implausible, especially in the context of the mining operations of [1,13]. 9In [15] one of us tried to argue, for a reason having nothing to do with computation, that the experiment cann…”
BackgroundResultInfluentialClassical and Quantum Computation
Kitaev, A., Shen, A., & Vyalyi, M. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/047 · Cited by 1,387
Black holes as mirrors: quantum information in random subsystems
Hayden, P., & Preskill, J. (2007) · Journal of High Energy Physics · doi:10.1088/1126-6708/2007/09/120 · Cited by 1,332 · cited 5×
“We will review the AMPS argument in section 2 below, but a key point in moti- vating 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.1 The model black hole of Hayden and Preskill [2], also partially reviewed below, suggests…”
BackgroundInfluentialSelf-citationHorowitz, G. T., & Strominger, A. (1991) · Nuclear Physics B · doi:10.1016/0550-3213(91)90440-9 · Cited by 1,227 · cited 1×
“One of the best-known solutions of ten-dimensional IIB supergravity is the extremal planar black 3-brane [75], with metric ds(2) = Z(r)−1/2 ( −dt(2) + d~x(2) ) + Z(r) ( dr(2) + r(2)dΩ(2)5 ) .”
BackgroundSchumacher, B. (1995) · Physical Review A · doi:10.1103/physreva.51.2738 · Cited by 1,090 · cited 1×
“The resulting state |ψ〉⊗k rapidly converges to one with near-maximal entropy concentrated in the “typical subspace” of B⊗kH⊗k [63].”
The information paradox: a pedagogical introduction
Mathur, S. D. (2009) · Classical and Quantum Gravity · doi:10.1088/0264-9381/26/22/224001 · Cited by 975 · cited 2×
“One way to see this more precisely, again following AMPS, who themselves were motivated by a similar argument due to Mathur [31], is to note that strong subadditivity requires”
BackgroundProof of the strong subadditivity of quantum-mechanical entropy
Lieb, E. H., & Ruskai, M. B. (1973) · Journal of Mathematical Physics · doi:10.1063/1.1666274 · Cited by 831 · cited 1×
“ing entangled with Aas in (2.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 S ABR B + S B S AB+ S BR B : (2.7) By construction we have S BR B = 0, which also implies (for example by…”
InfluentialStabilizer Codes and Quantum Error Correction
Gottesman, D. (1997) · arXiv · doi:10.48550/arxiv.quant-ph/9705052 · Cited by 753 · cited 3×
“The most widely studied quantum error correcting codes are the stabilizer codes [56], which are defined by the property that the n − k check operators are all just products of Pauli operators of the form (4.”
BackgroundSimulation of Many-Body Fermi Systems on a Universal Quantum Computer
Abrams, D. S., & Lloyd, S. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.2586 · Cited by 745 · cited 1×
“Theories of this type can usually be simulated by polynomial-sized quantum circuits [47–50], so it seems quite reasonable to assume that Udyn can be generated by a polynomial number of gates.”
BackgroundBrane dynamics from the Born-Infeld action
Callan, C. G., & MALDACENA, J. M. (1998) · Nuclear Physics B · doi:10.1016/s0550-3213(97)00700-1 · Cited by 679
Maldacena, J., Michelson, J., & Strominger, A. (1999) · Journal of High Energy Physics · doi:10.1088/1126-6708/1999/02/011 · Cited by 548 · cited 3×
“We will explain however that the well-known “fragmentation” phenomenon [17, 18] destroys the black hole well before the computation can be completed.”
BackgroundCoordinate Invariance and Energy Expressions in General Relativity
Arnowitt, R., Deser, S., & Misner, C. W. (1961) · Physical Review · doi:10.1103/physrev.122.997 · Cited by 547 · cited 1×
“For an asymptotically flat geometry, in coordinates where the metric is ημν + hμν with hμν small, the ADM energy is defined [77] as limr→∞ 1 16πG ∫ dAn ( ∂jhij − ∂ihjj ) .”
Quantum Algorithms for Quantum Field Theories
Jordan, S. P., Lee, K. S. M., & Preskill, J. (2012) · Science · doi:10.1126/science.1217069 · Cited by 517
FAULT-TOLERANT QUANTUM COMPUTATION
PRESKILL, J. (1998) · Introduction to Quantum Computation and Information · doi:10.1142/9789812385253_0008 · Cited by 466
Better Late than Never: Information Retrieval from Black Holes
Braunstein, S. L., Pirandola, S., & Życzkowski, K. (2013) · Physical Review Letters · doi:10.1103/physrevlett.110.101301 · Cited by 460 · cited 1×
“We recently found out that a similar argument was made by Braunstein, later joined by Pirandola and Życzkowski, back in 2009 [2], who called the firewall an “energetic curtain”.”
ResultAnti De Sitter Space And Holography
Witten, E. (1998) · arXiv · doi:10.48550/arxiv.hep-th/9802150 · Cited by 374 · cited 5×
“Near the horizon the solution then behaves as Ψω` ∼ eiω(±r∗−t), while at large r we have φ ∼ r−∆± with the usual AdS/CFT formula ∆± = d− 1 2 ± 1 2 √ (d− 1)2 + 4R2m2.”
MethodInfluentialMoore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
Kuperberg, G. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539703436345 · Cited by 347 · cited 1×
“Researchers have been trying consistently since then to attack the non-Abelian version of the problem but with only very limited success [70–72].”
BackgroundRandomizing Quantum States: Constructions and Applications
Hayden, P., Leung, D., Shor, P. W., & Winter, A. (2004) · Communications in Mathematical Physics · doi:10.1007/s00220-004-1087-6 · Cited by 345 · cited 1×
“Such a set is called an -net, and it is not too hard to get an estimate of how many elements it must have [33].”
BackgroundSelf-citationUniversality of Low Energy Absorption Cross Sections for Black Holes
Das, S. R., Gibbons, G., & Mathur, S. D. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.417 · Cited by 344 · cited 1×
“This probability will be a function of the frequency ω of the quanta of interest, and in the limit ωR 1 it can often be computed analytically [87].”
BackgroundDisturbing Implications of a Cosmological Constant
Dyson, L., Kleban, M., & Susskind, L. (2002) · Journal of High Energy Physics · doi:10.1088/1126-6708/2002/10/011 · Cited by 338 · cited 2×
“This is the phenomenon of Poincaré recurrence [19].”
BackgroundMethodThe Black Hole Singularity in AdS/CFT
Fidkowski, L., Hubeny, V., Kleban, M., & Shenker, S. (2004) · Journal of High Energy Physics · doi:10.1088/1126-6708/2004/02/014 · Cited by 330
Absorption by branes and Schwinger terms in the world volume theory
Gubser, S. S., & Klebanov, I. R. (1997) · Physics Letters B · doi:10.1016/s0370-2693(97)01099-x · Cited by 294 · cited 1×
“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∆ [85], so the unitarity bound ∆ > 1 in four dimensions precludes b < 2.”
BackgroundLIMITATIONS ON THE STATISTICAL DESCRIPTION OF BLACK HOLES
PRESKILL, J., SCHWARZ, P., SHAPERE, A., TRIVEDI, S., & WILCZEK, F. (1991) · Modern Physics Letters A · doi:10.1142/s0217732391002773 · Cited by 287 · cited 2×
“We will explain however that the well-known “fragmentation” phenomenon [17, 18] destroys the black hole well before the computation can be completed.”
BackgroundHorowitz, G. T., & Maldacena, J. (2004) · Journal of High Energy Physics · doi:10.1088/1126-6708/2004/02/008 · Cited by 270 · cited 1×
“Another interesting proposal, raised again recently in the firewall discussion by John Preskill and Alexei Kitaev, is the Maldacena/Horowitz “black hole final state” scenario [19].”
BackgroundWorld-volume approach to absorption by non-dilatonic branes
Klebanov, I. R. (1997) · Nuclear Physics B · doi:10.1016/s0550-3213(97)00235-6 · Cited by 253 · cited 2×
“r transverse oscillations of a string stretching down the extremal black three brane geometry (5.17). This has been previously been computed by Maldacena and Callan [70]; our method is the same as in [66] for a massless scalar. The Nambu-Goto action is S NG= 1 2ˇ‘2 s Z d2˙ p det(G MN@ iXM@iXN); (A.1) and parametrizing…”
BackgroundMethodInfluentialGuest Column: NP-complete problems and physical reality
Aaronson, S. (2005) · ACM SIGACT News · doi:10.1145/1052796.1052804 · Cited by 227
Distinguishability and Accessible Information in Quantum Theory
Fuchs, C. A. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9601020 · Cited by 192 · cited 1×
“do the computation exactly. We thus need a good denition of how \close" she needs to get to reliably test the entanglement. One standard way to quantify closeness of operators is the trace norm [21], which for an operator Ais dened as jjAjj 1 Tr p AyA : (3.4) When Ais hermitian this is just the sum of the absolut…”
BackgroundInfluentialConstructing local bulk observables in interacting AdS/CFT
Kabat, D., Lifschytz, G., & Lowe, D. A. (2011) · Physical Review D · doi:10.1103/physrevd.83.106009 · Cited by 189 · cited 5×
“being outside the horizon, and she can also try to construct them using the method of [51].”
BackgroundMethodInfluentialZero-Knowledge against Quantum Attacks
Watrous, J. (2009) · SIAM Journal on Computing · doi:10.1137/060670997 · Cited by 188
Holographic superconductor/insulator transition at zero temperature
Nishioka, T., Ryu, S., & Takayanagi, T. (2010) · Journal of High Energy Physics · doi:10.1007/jhep03(2010)131 · Cited by 169 · cited 1×
“This transition has been previously discussed by [80].”
BackgroundNP-complete Problems and Physical RealityPreprint
Aaronson, S. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0502072 · Cited by 153 · cited 2×
“These results are consistent with a point of view expressed by Aaronson [20] that the laws of physics should not permit computational machines that radically alter the basic structure of complexity theory.”
BackgroundResultComputational complexity of the landscape: Part I
Denef, F., & Douglas, M. R. (2007) · Annals of Physics · doi:10.1016/j.aop.2006.07.013 · Cited by 138 · cited 1×
“,54], which is the gold standard in evidence that a classical computation requires exponential time. Good reviews of the basic properties of NP-completeness and its possible relevance for physics are [20,55]. It will be important later that this additional source of computational diculty is relevant only if kis large.…”
BackgroundQuantum lower bound for the collision problem
Aaronson, S. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509999 · Cited by 135 · cited 1×
“) 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 [72].”
BackgroundBousso, R. (2013) · Physical Review D · doi:10.1103/physrevd.87.124023 · Cited by 115 · cited 3×
“d \A= R B" for reasons we will soon see. It has been suggested by several people10 as a way out of rewalls, 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 rewall argument, but it seems t…”
BackgroundInfluentialNon-extremal black hole microstates: fuzzballs of fire or fuzzballs of fuzz?
Bena, I., Puhm, A., & Vercnocke, B. (2012) · Journal of High Energy Physics · doi:10.1007/jhep12(2012)014 · Cited by 86 · cited 1×
“Other work on firewalls includes [25–35].”
String Theory and Black Hole ComplementarityPreprint
Polchinski, J. (1995) · arXiv (Cornell University) · doi:10.48550/arxiv.hep-th/9507094 · Cited by 79 · cited 1×
“the experiment. 5The authors of [7] also attempted to give a less operational reason for the break down of EFT involving large integrated boosts, although aspects of this claim were later questioned [8]. It remains to be seen whether a similar argument might exist for the breakdown we advocate here. { 3 { more modicat…”
BackgroundIs the firewall consistent? Gedanken experiments on black hole complementarity and firewall proposal
Hwang, D.-I., Lee, B.-H., & Yeom, D.-H. (2013) · Journal of Cosmology and Astroparticle Physics · doi:10.1088/1475-7516/2013/01/005 · Cited by 73
The Transfer of Entanglement: The Case for Firewalls
Susskind, L. (2012) · arXiv · doi:10.48550/arxiv.1210.2098 · Cited by 73 · cited 2×
“ed \A= R B" for reasons we will soon see. It has been suggested by several people8 as a way out of rewalls, but it has so far run into various paradoxes involving apparent cloning and acausality [12,16]. We postpone further discussion of these two options until after we present the rewall argument, but it seems t…”
BackgroundCrunches, Hats, and a ConjecturePreprint
Harlow, D., & Susskind, L. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.5302 · Cited by 73
Self-citationNP-hardness of decoding quantum error-correction codes
Hsieh, M.-H., & Le Gall, F. (2011) · Physical Review A · doi:10.1103/physreva.83.052331 · Cited by 71 · cited 11×
“As explained in [52] either of these strategies can embed the following question about matrices:”
BackgroundInfluentialComplementarity endures: no firewall for an infalling observer
Nomura, Y., Varela, J., & Weinberg, S. J. (2013) · Journal of High Energy Physics · doi:10.1007/jhep03(2013)059 · Cited by 70
Black Hole Complementarity and the Harlow-Hayden Conjecture
Susskind, L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.4505 · Cited by 66
Holographic Space-Time: The TakeawayPreprint
Banks, T. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.2435 · Cited by 65 · cited 2×
“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 gure1above. In this framework it seems necessary for con…”
BackgroundBanks, T., & Fischler, W. (2001) · arXiv (Cornell University) · doi:10.48550/arxiv.hep-th/0111142 · Cited by 64 · cited 2×
“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" [8,9]. The basic idea is illustrated in gure1above. In this framework it seems necessary for consistency [11,12] for Ali…”
BackgroundString theory versus black hole complementarity
Giveon, A., & Itzhaki, N. (2012) · Journal of High Energy Physics · doi:10.1007/jhep12(2012)094 · Cited by 57 · cited 1×
“Other work on firewalls includes [25–35].”
The Symmetric Group Defies Strong Fourier Sampling
Moore, C., Russell, A. C., & Schulman, L. J. (2008) · SIAM Journal on Computing · doi:10.1137/050644896 · Cited by 52 · cited 1×
“) Large classes of strategies based on Shor’s Fourier-sampling approach are known to fail [69, 70].”
BackgroundA Quantum Observable for the Graph Isomorphism ProblemPreprint
Ettinger, M., & Høyer, P. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9901029 · Cited by 47 · cited 1×
“(Note that the non-Abelian version includes the graph isomorphism problem discussed above as a special case [68].”
BackgroundHorowitz, G., Lawrence, A., & Silverstein, E. (2009) · Journal of High Energy Physics · doi:10.1088/1126-6708/2009/07/057 · Cited by 45 · cited 1×
“Interesting previous work on the interior of AdS black holes includes [73, 74]; it would be illuminating to understand how to ask the firewall question in either of these frameworks.”
BackgroundAn Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups
Ivanyos, G., Sanselme, L., & Sántha, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78773-0_65 · Cited by 42
Holographic Space-Time Does Not Predict Firewalls
Banks, T., & Fischler, W. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1208.4757 · Cited by 36
Hyper-entropic gravitational fireballs (grireballs) with firewalls
Page, D. N. (2013) · Journal of Cosmology and Astroparticle Physics · doi:10.1088/1475-7516/2013/04/037 · Cited by 31
Comment on the black hole firewall
Hossenfelder, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1210.5317 · Cited by 27
On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
Moore, C., Russell, A. C., & Śniady, P. (2010) · SIAM Journal on Computing · doi:10.1137/080724101 · Cited by 20
Complementarity, not FirewallsPreprint
Harlow, D. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.6243 · Cited by 17
Self-citationNeumann boundary conditions from Born–Infeld dynamics
Savvidy, K. G., & Savvidy, G. K. (1999) · Nuclear Physics B · doi:10.1016/s0550-3213(99)00504-0 · Cited by 16 · cited 1×
“One could also study oscillations along the brane direction, according to [89] these give an absorption probability proportional to (ωR)(4).”
BackgroundAnti-de Sitter Space, Thermal Phase Transition, And Confinement In Gauge Theories
Witten, E. (1998) · arXiv · doi:10.48550/arxiv.hep-th/9803131 · Cited by 3
Black Hole Complementarity vs. Locality
Lowe, D. A., Polchinski, J., Susskind, L., et al. (1995) · CERN Document Server (European Organization for Nuclear Research) · doi:10.48550/arxiv.hep-th/9506138 · Cited by 1 · cited 1×
“(5)The authors of [7] also attempted to give a less operational reason for the break down of EFT involving large integrated boosts, although aspects of this claim were later questioned [8].”
BackgroundComputational complexity of the landscape I
Denef, F., & Douglas, M. R. (2006) · CERN Document Server (European Organization for Nuclear Research) · doi:10.48550/arxiv.hep-th/0602072 · cited 1×
“,54], which is the gold standard in evidence that a classical computation requires exponential time. Good reviews of the basic properties of NP-completeness and its possible relevance for physics are [20,55]. It will be important later that this additional source of computational diculty is relevant only if kis large.…”
Background
Research works printed but not linked: 23
- S. Hawking, Breakdown of Predictability in Gravitational Collapse, Phys. Rev. D 14 (1976) 2460 [ INSPIRE ].
- L. Susskind, L. Thorlacius and J. Uglum, The stretched horizon and black hole complementarity, Phys. Rev. D 48 (1993) 3743 [ hep-th/9306069 ] [ INSPIRE ]. · arXiv
- L. Susskind and L. Thorlacius, Gedanken experiments involving black holes, Phys. Rev. D 49 (1994) 966 [ hep-th/9308100 ] [ INSPIRE ]. · arXiv
- A.R. Brown, Tensile Strength and the Mining of Black Holes, arXiv:1207.3342 [ INSPIRE ]. · arXiv
- K. Papadodimas and S. Raju, An Infalling Observer in AdS/CFT, arXiv:1211.6767 [ INSPIRE ]. · arXiv
- T. Jacobson, Boundary unitarity without firewalls, arXiv:1212.6944 [ INSPIRE ]. · arXiv
- S.D. Mathur and D. Turton, Comments on black holes I: The possibility of complementarity, arXiv:1208.2005 [ INSPIRE ]. · arXiv
- B.D. Chowdhury and A. Puhm, Is Alice burning or fuzzing?, arXiv:1208.2026 [ INSPIRE ]. · arXiv
- S.G. Avery, B.D. Chowdhury and A. Puhm, Unitarity and fuzzball complementarity: ‘Alice fuzzes but may not even know it!’, arXiv:1210.6996 [ INSPIRE ]. · arXiv
- K. Larjo, D.A. Lowe and L. Thorlacius, Black holes without firewalls, arXiv:1211.4620 [ INSPIRE ]. · arXiv
- S.B. Giddings, Nonviolent nonlocality, arXiv:1211.7070 [ INSPIRE ]. · arXiv
- E. Verlinde and H. Verlinde, Black Hole Entanglement and Quantum Error Correction, arXiv:1211.6913 [ INSPIRE ]. · arXiv
- K.-Y. Kuo and C.-C. Lu, On the hardness of decoding quantum stabilizer codes under the depolarizing channel, in 2012 International Symposium on Information Theory and its Applications (ISITA) 2012, pg. 208-211.
- D.N. Page, Particle Emission Rates from a Black Hole: Massless Particles from an Uncharged, Nonrotating Hole, Phys. Rev. D 13 (1976) 198 [ INSPIRE ].
- J. Watrous, Limits on the power of quantum statistical zero-knowledge, in proceedings of The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pg. 459-468.
- P. Hayden, K. Milner and M.M. Wilde, Two-message quantum interactive proofs and the quantum separability problem, arXiv:1211.6120 . · arXiv
- A.Y. Kitaev, Quantum measurements and the Abelian stabilizer problem, quant-ph/9511026 [ INSPIRE ]. · arXiv
- D. Bacon, A. Childs and W. Van Dam, From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, in FOCS 2005 - 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pg. 469-478.
- C. Moore, A. Russell and U. Vazirani, A classical one-way function to confound quantum adversaries, quant-ph/0701115 . · arXiv
- D.N. Page, Thermodynamics of near extreme black holes, hep-th/0012020 [ INSPIRE ]. · arXiv
- S.P. Kim and D.N. Page, Magnetic black holes are also unstable, J. Korean Phys. Soc. 45 (2004) S59 [ gr-qc/0403005 ] [ INSPIRE ]. · arXiv
- S. Gubser, I.R. Klebanov and A. Peet, Entropy and temperature of black 3-branes, Phys. Rev. D 54 (1996) 3915 [ hep-th/9602135 ] [ INSPIRE ]. · arXiv
- D. Anninos, F. Denef and D. Harlow, The Wave Function of Vasiliev’s Universe - A Few Slices Thereof, arXiv:1207.5517 [ INSPIRE ]. · arXiv
Cited by
Cool horizons for entangled black holes
Maldacena, J., & Susskind, L. (2013) · arXiv · doi:10.48550/arxiv.1306.0533 · Cited by 1,310
“These are the operators that Harlow and Hayden [18] identify as computationally difficult to access.”
BackgroundInfluentialEntanglement wedge reconstruction and the information paradox
Penington, G. (2020) · Journal of High Energy Physics · doi:10.1007/jhep09(2020)002 · Cited by 968
“The publication of [10] provoked a flood of responses, including [12–17].”
BackgroundEntanglement as Topology: Hopf Linking as the Geometric Origin of Quantum Correlation
Novickis, A. (2026) · doi:10.5281/zenodo.20549411 · Cited by 821
Replica wormholes and the black hole interior
Penington, G., Shenker, S. H., Stanford, D., & Yang, Z. (2019) · arXiv · doi:10.48550/arxiv.1911.11977 · Cited by 809
“In fact, for evaporating black holes, there is good reason to think that it is exponentially complicated [66, 67].”
BackgroundBulk locality and quantum error correction in AdS/CFT
Almheiri, A., Dong, X., & Harlow, D. (2015) · Journal of High Energy Physics · doi:10.1007/jhep04(2015)163 · Cited by 802
Self-citation
Metadata
- Authors
- Harlow, D., & Hayden, P.
- Affiliations
- Princeton University (US)
- McGill University (CA)
- Corresponding author
- Harlow, Daniel
- Venue
- Journal of High Energy Physics
- Published
- 2013-06
- Volume
- 2013
- Issue
- 6
- ISSN
- 1029-8479 (ISSN-L)
- OpenAlex
- W2156785825
- Semantic Scholar
- 0aad2a4521ad01694c8ec5c02f11ac06107e8f49
- Cited by
- 310
- References
- 60
- Citations by year
- 2026: 23 · 2025: 21 · 2024: 23 · 2023: 25 · 2022: 24 · 2021: 20 · 2020: 38 · 2019: 16 · 2018: 10 · 2017: 26 · 2016: 21 · 2015: 17 · 2014: 32 · 2013: 14
- FWCI
- 11.51
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Journal of High Energy Physics (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Canadian Institute for Advanced Research
- Canada Research Chairs
- Industry Canada
- Ministero dello Sviluppo Economico
- Institut Périmètre de physique théorique
- Natural Sciences and Engineering Research Council of Canada
- Office of Naval Research (N000140811249)
- Topics
- Physical Sciences › Physics and Astronomy › Nuclear and High Energy Physics › Black Holes and Theoretical Physics
- Physical Sciences › Physics and Astronomy › Nuclear and High Energy Physics › Noncommutative and Quantum Gravity Theories
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Electrodynamics and Casimir Effect
- Keywords
- black hole firewalls, event horizon, black hole entropy, quantum computing, computational complexity, nonlocality, black hole information paradox, black hole evaporation, unitarity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.