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
Research works printed but not linked: 23
- [4] S. Hawking, Breakdown of Predictability in Gravitational Collapse , Phys.Rev. D14 (1976) 2460-2473. -
- [5] L. Susskind, L. Thorlacius, and J. Uglum, The Stretched Horizon and Black Hole Complementarity , Phys.Rev. D48 (1993) 3743-3761, [ hep-th/9306069 ]. - · arXiv
- [6] L. Susskind and L. Thorlacius, Gedanken Experiments Involving Black Holes , Phys.Rev. D49 (1994) 966-974, [ hep-th/9308100 ]. - · arXiv
- [13] A. R. Brown, Tensile Strength and the Mining of Black Holes , arXiv:1207.3342 . - · arXiv
- [16] K. Papadodimas and S. Raju, An Infalling Observer in AdS/CFT , arXiv:1211.6767 . - · arXiv
- [17] T. Jacobson, Boundary Unitarity Without Firewalls , arXiv:1212.6944 . - · arXiv
- [26] S. D. Mathur and D. Turton, Comments on black holes I: The possibility of complementarity , arXiv:1208.2005 . - · arXiv
- [29] B. D. Chowdhury and A. Puhm, Is Alice burning or fuzzing? , arXiv:1208.2026 . - · arXiv
- [30] S. G. Avery, B. D. Chowdhury, and A. Puhm, Unitarity and fuzzball complementarity: 'Alice fuzzes but may not even know it!' , arXiv:1210.6996 . - · arXiv
- [33] K. Larjo, D. A. Lowe, and L. Thorlacius, Black holes without firewalls , arXiv:1211.4620 . - · arXiv
- [35] S. B. Giddings, Nonviolent nonlocality , arXiv:1211.7070 . - · arXiv
- [52] E. Verlinde and H. Verlinde, Black Hole Entanglement and Quantum Error Correction , arXiv:1211.6913 . - · 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.
- [62] D. N. Page, Particle Emission Rates from a Black Hole: Massless Particles from an Uncharged, Nonrotating Hole , Phys.Rev. D13 (1976) 198-206. -
- [64] 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) , pp. 459-468, IEEE, 2002. -
- [67] P. Hayden, K. Milner, and M. M. Wilde, Two-message quantum interactive proofs and the quantum separability problem , arXiv preprint arXiv:1211.6120 (2012). - · arXiv
- [69] A. Kitaev, Quantum measurements and the abelian stabilizer problem , arXiv preprint quant-ph/9511026 (1995). - · arXiv
- [70] 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 46th Annual IEEE Symposium on Foundations of Computer Science, 2005. FOCS 2005. , pp. 469-478, IEEE, 2005. -
- [76] C. Moore, A. Russell, and U. Vazirani, A classical one-way function to confound quantum adversaries , arXiv preprint quant-ph/0701115 (2007). - · 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
- [81] S. Gubser, I. R. Klebanov, and A. Peet, Entropy and Temperature of Black 3-branes , Phys.Rev. D54 (1996) 3915-3919, [ hep-th/9602135 ]. - · arXiv
- [86] D. Anninos, F. Denef, and D. Harlow, The Wave Function of Vasiliev's Universe - A Few Slices Thereof , arXiv:1207.5517 . - · 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-citationReplica wormholes and the black hole interior
Penington, G., Shenker, S. H., Stanford, D., & Yang, Z. (2022) · Journal of High Energy Physics · doi:10.1007/jhep03(2022)205 · Cited by 807
Time evolution of entanglement entropy from black hole interiors
Hartman, T., & Maldacena, J. (2013) · Journal of High Energy Physics · doi:10.1007/jhep05(2013)014 · Cited by 761
“9 It has been claimed that it is impossible to construct such a computer [52].”
BackgroundComplexity and shock wave geometries
Stanford, D., & Susskind, L. (2014) · Physical Review D · doi:10.1103/physrevd.90.126007 · Cited by 748
“Until recently this difference between classical and quantum complexity has not played a large role in formulating physical principles, but this may be changing (see also [7]).”
BackgroundComplexity, action, and black holes
Brown, A. R., Roberts, D. A., Susskind, L., Swingle, B., & Zhao, Y. (2016) · Physical Review D · doi:10.1103/physrevd.93.086006 · Cited by 640
“Quantum complexity entered black hole physics to help quantify the difficulty of decoding Hawking radiation [2], but it appears to also shed light on physics behind the horizon.”
BackgroundComputational complexity and black hole horizons
Susskind, L. (2016) · Fortschritte der Physik · doi:10.1002/prop.201500092 · Cited by 767
Jerusalem lectures on black holes and quantum information
Harlow, D. (2016) · Reviews of Modern Physics · doi:10.1103/revmodphys.88.015002 · Cited by 480
Self-citationChaos and complexity by design
Roberts, D. A., & Yoshida, B. (2017) · Journal of High Energy Physics · doi:10.1007/jhep04(2017)121 · Cited by 455
“In the context of holography, computational complexity was “introduced” [70] as a possible resolution to the firewall paradox of [71, 6].”
BackgroundSusskind, L. (2016) · Fortschritte der Physik · doi:10.1002/prop.201500095 · Cited by 427
Echoes from the abyss: Tentative evidence for Planck-scale structure at black hole horizons
Abedi, J., Dykaar, H., & Afshordi, N. (2017) · Physical Review D · doi:10.1103/physrevd.96.082004 · Cited by 409
Diving into traversable wormholes
Maldacena, J., Stanford, D., & Yang, Z. (2017) · Fortschritte der Physik · doi:10.1002/prop.201700034 · Cited by 358
“This is surprising because, in general, the Hayden-Preskill decoding operation is very difficult [34].”
BackgroundInfluentialBlack hole remnants and the information loss paradox
Chen, P., Ong, Y. C., & Yeom, D.-H. (2015) · Physics Reports · doi:10.1016/j.physrep.2015.10.007 · Cited by 298
Almheiri, A., Marolf, D., Polchinski, J., Stanford, D., & Sully, J. (2013) · eScholarship (California Digital Library) · Cited by 300
State-dependent bulk-boundary maps and black hole complementarity
Papadodimas, K., & Raju, S. (2014) · Physical Review D · doi:10.1103/physrevd.89.086010 · Cited by 267
Chaos, complexity, and random matrices
Cotler, J., Hunter-Jones, N., Liu, J., & Yoshida, B. (2017) · Journal of High Energy Physics · doi:10.1007/jhep11(2017)048 · Cited by 264
“More recently, it was asked whether the AMPS thought experiment can be carried out in a physically reasonable amount of time and resources by considering the computational complexity of decoding the Hawking radiation [53].”
BackgroundChaos, complexity, and random matrices
Cotler, J. S. (2023) · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · doi:10.1007/jhep11%282017%29048 · Cited by 207
The black hole information problem: past, present, and future
Marolf, D. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa77cc · Cited by 205
Action growth for AdS black holes
Cai, R.-G., Ruan, S.-M., Wang, S.-J., Yang, R.-Q., & Peng, R.-H. (2016) · Journal of High Energy Physics · doi:10.1007/jhep09(2016)161 · Cited by 196
Remarks on the necessity and implications of state-dependence in the black hole interior
Papadodimas, K., & Raju, S. (2016) · Physical Review D · doi:10.1103/physrevd.93.084049 · Cited by 138
“For a precursor of the firewall paradox, see [21] and for approaches using complexity see [22].”
Quantum computational complexity from quantum information to black holes and back
Chapman, S., & Policastro, G. (2022) · The European Physical Journal C · doi:10.1140/epjc/s10052-022-10037-1 · Cited by 173
“A connection was in fact already suggested in [95] in relation to the problem of decoding the information contained in the Hawking radiation.”
BackgroundBarren Plateaus Preclude Learning Scramblers
Holmes, Z., Arrasmith, A., Yan, B., Coles, P. J., Albrecht, A., & Sornborger, A. T. (2021) · Physical Review Letters · doi:10.1103/physrevlett.126.190501 · Cited by 125
“Related complexity theoretic arguments precluding learning black hole unitaries depend on Alice’s restricted access to the full unitary [57].”
BackgroundThe Python’s Lunch: geometric obstructions to decoding Hawking radiation
Brown, A. R., Gharibyan, H., Penington, G., & Susskind, L. (2020) · Journal of High Energy Physics · doi:10.1007/jhep08(2020)121 · Cited by 124
“Computational complexity is relevant to the study of quantum gravity in (at least) two ways: in its traditional role as a measure of the difficulty of carrying out tasks [1]; and as a possible holographic dual for properties of the spacetime behind horizons [2, 3, 4].”
BackgroundMethodInfluentialThe typical‐state paradox: diagnosing horizons with complexity
Susskind, L. (2016) · Fortschritte der Physik · doi:10.1002/prop.201500091 · Cited by 104
“1 Computational complexity was first introduced into black hole physics by Harlow andHayden [10] in a somewhat different context.”
BackgroundUnitarity of black hole evaporation in final-state projection models
Lloyd, S., & Preskill, J. (2014) · Journal of High Energy Physics · doi:10.1007/jhep08(2014)126 · Cited by 100
The potential impact of quantum computers on society
de Wolf, R. (2017) · Ethics and Information Technology · doi:10.1007/s10676-017-9439-z · Cited by 158
Nonviolent information transfer from black holes: A field theory parametrization
Giddings, S. B. (2013) · Physical Review D · doi:10.1103/physrevd.88.024018 · Cited by 90
“1 In contrast, more recent proposals to save a version of complementarity[11,12] may involve a breakdown of locality to beyond the Andromeda galaxy, for a solar mass black hole located here.”
BackgroundThe black hole interior from non-isometric codes and complexity
Akers, C., Engelhardt, N., Harlow, D., Penington, G., & Vardhan, S. (2024) · Journal of High Energy Physics · doi:10.1007/jhep06(2024)155 · Cited by 75
Self-citationQuantum information in holographic duality
Chen, B., Czech, B., & Wang, Z.-Z. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac51b5 · Cited by 121
Quantum complexity and topological phases of matter
Caputa, P., & Liu, S. (2022) · Physical review. B./Physical review. B · doi:10.1103/physrevb.106.195125 · Cited by 114
“Among others, complexity played essential roles in discussions on the firewall [2], fast scrambling near black hole horizons [3–6], quantum chaos [7], and finally the nature of holographic dictionary itself [8].”
BackgroundAbedi, J., & Afshordi, N. (2019) · Journal of Cosmology and Astroparticle Physics · doi:10.1088/1475-7516/2019/11/010 · Cited by 114
“would be equivalent to setting ∆techo ∼ scrambling time for the black hole [9, 10, 27, 28].”
BackgroundAspects of the Papadodimas-Raju proposal for the black hole interior
Harlow, D. (2014) · Journal of High Energy Physics · doi:10.1007/jhep11(2014)055 · Cited by 44
Self-citationDynamics and transport at the threshold of many-body localization
Gopalakrishnan, S., & Parameswaran, S. A. (2020) · Physics Reports · doi:10.1016/j.physrep.2020.03.003 · Cited by 102
Krylov complexity in free and interacting scalar field theories with bounded power spectrum
Camargo, H. A., Jahnke, V., Kim, K.-Y., & Nishida, M. (2023) · Journal of High Energy Physics · doi:10.1007/jhep05(2023)226 · Cited by 111
Complexity Growth Rate in Lovelock Gravity
Cano, P. A., Hennigar, R. A., & Marrochio, H. (2018) · Physical Review Letters · doi:10.1103/physrevlett.121.121602 · Cited by 82
Unitarity of black hole evaporation in final-state projection models
Lloyd, S., & Preskill, J. P. (2014) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 66
Bousso, R. (2014) · Physical Review Letters · doi:10.1103/physrevlett.112.041102 · Cited by 68
A world without pythons would be so simple
Engelhardt, N., Penington, G., & Shahbazi-Moghaddam, A. (2021) · Classical and Quantum Gravity · doi:10.1088/1361-6382/ac2de5 · Cited by 64
“It also leads to a geometrical explanation for the expectation of Harlow–Hayden [10] that decoding Hawking radiation should be exponentially complex.”
The ghost in the radiation: robust encodings of the black hole interior
Kim, I., Tang, E., & Preskill, J. (2020) · Journal of High Energy Physics · doi:10.1007/jhep06(2020)031 · Cited by 63
Transitions in the Learnability of Global Charges from Local Measurements
Barratt, F., Agrawal, U., Potter, A. C., Gopalakrishnan, S., & Vasseur, R. (2022) · Physical Review Letters · doi:10.1103/physrevlett.129.200602 · Cited by 111
Black Holes: Eliminating Information or Illuminating New Physics?
Chakraborty, S., & Lochan, K. (2017) · Universe · doi:10.3390/universe3030055 · Cited by 75
“This certainly speaks against the firewall puzzle [88] (see also [97]).”
BackgroundHolographic complexity and volume
Couch, J., Eccles, S., Jacobson, T., & Nguyen, P. (2018) · Journal of High Energy Physics · doi:10.1007/jhep11(2018)044 · Cited by 70
Excluding black hole firewalls with extreme cosmic censorship
Page, D. N. (2014) · Journal of Cosmology and Astroparticle Physics · doi:10.1088/1475-7516/2014/06/051 · Cited by 59
“The AMPS argument has elicited a large number of responses (including a few [2, 3, 4] to forms of the argument realized even before the AMPS paper), some of which appear to support the firewall idea [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24], others seem rather agnostic or ambivalent […”
BackgroundComplexity change under conformal transformations in AdS3/CFT2
Flory, M., & Miekley, N. (2019) · Journal of High Energy Physics · doi:10.1007/jhep05(2019)003 · Cited by 60
Black Holes: Thermodynamics, Information, and Firewalls
Mann, R. B. (2015) · SpringerBriefs in physics · doi:10.1007/978-3-319-14496-2 · Cited by 75
Spread complexity and topological transitions in the Kitaev chain
Caputa, P., Gupta, N., Haque, S. S., Liu, S., Murugan, J., & Zyl, H. J. R. V. (2023) · Journal of High Energy Physics · doi:10.1007/jhep01(2023)120 · Cited by 72
Entanglement Wedge Reconstruction and the Information Paradox
Penington, G. (2019) · arXiv · doi:10.48550/arxiv.1905.08255 · Cited by 56
“The publication of [10] provoked a flood of responses, including [12–17].”
BackgroundEntanglement entropy and complexity for one-dimensional holographic superconductors
Zangeneh, M. K., Ong, Y. C., & Wang, B. (2017) · Physics Letters B · doi:10.1016/j.physletb.2017.05.051 · Cited by 58
Violations of the Born rule in cool state-dependent horizons
Marolf, D., & Polchinski, J. (2016) · Journal of High Energy Physics · doi:10.1007/jhep01(2016)008 · Cited by 55
Shadow process tomography of quantum channels
Kunjummen, J., Tran, M. C., Carney, D., & Taylor, J. M. (2023) · Physical Review A · doi:10.1103/physreva.107.042403 · Cited by 112
Bousso, R. (2013) · Physical Review D · doi:10.1103/physrevd.88.084035 · Cited by 53
“) The counterargument that B̂ may not be computationally accessible [34] has been questioned in Ref.”
BackgroundHolographic complexity and action growth in massive gravities
Pan, W.-J., & Huang, Y.-C. (2017) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.95.126013 · Cited by 59
Semiclassical and Stochastic Gravity: Quantum Field Effects on Curved Spacetime
Hu, B. L., & Verdaguer, E. (2020) · Cambridge University Press eBooks · doi:10.1017/9780511667497 · Cited by 126
Black-hole entropy from supergravity superstrata states
Bena, I., Shigemori, M., & Warner, N. P. (2014) · Journal of High Energy Physics · doi:10.1007/jhep10(2014)140 · Cited by 52
Van Raamsdonk, M. (2014) · Journal of High Energy Physics · doi:10.1007/jhep11(2014)038 · Cited by 52
Holographic complexity and two identities of action growth
Huang, H., Feng, X.-H., & Lü, H. (2017) · Physics Letters B · doi:10.1016/j.physletb.2017.04.011 · Cited by 56
Generalized uncertainty principle: implications for black hole complementarity
Chen, P., Ong, Y. C., & Yeom, D.-H. (2014) · Journal of High Energy Physics · doi:10.1007/jhep12(2014)021 · Cited by 53
A complexity/fidelity susceptibility g-theorem for AdS3/BCFT2
Flory, M. (2017) · Journal of High Energy Physics · doi:10.1007/jhep06(2017)131 · Cited by 53
Scrambling Transition in a Radiative Random Unitary Circuit
Weinstein, Z., Kelly, S. P., Marino, J., & Altman, E. (2023) · Physical Review Letters · doi:10.1103/physrevlett.131.220404 · Cited by 76
Complexity of holographic superconductors
Yang, R.-Q., Jeong, H.-S., Niu, C., & Kim, K.-Y. (2019) · Journal of High Energy Physics · doi:10.1007/jhep04(2019)146 · Cited by 51
“As a candidate to explore inside the black hole horizon, another important concept, the “complexity”, has been introduced from quantum computation theory [8–13].”
BackgroundMore on complexity of operators in quantum field theory
Yang, R.-Q., An, Y.-S., Niu, C., Zhang, C.-Y., & Kim, K.-Y. (2019) · Journal of High Energy Physics · doi:10.1007/jhep03(2019)161 · Cited by 52
Black hole complementarity and firewall in two dimensions
Kim, W., Lee, B.-H., & Yeom, D.-H. (2013) · Journal of High Energy Physics · doi:10.1007/jhep05(2013)060 · Cited by 47
Entanglement wedges for gravitating regions
Bousso, R., & Penington, G. (2023) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.107.086002 · Cited by 84
Uncertainty relation in Schwarzschild spacetime
Feng, J., Zhang, Y.-Z., Gould, M. D., & Fan, H. (2015) · Physics Letters B · doi:10.1016/j.physletb.2015.02.058 · Cited by 47
Holographic spacetime, black holes and quantum error correcting codes: a review
Kibe, T., Mandayam, P., & Mukhopadhyay, A. (2022) · The European Physical Journal C · doi:10.1140/epjc/s10052-022-10382-1 · Cited by 44
“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] (see [257] for a nice discussion).”
BackgroundInfluentialTopological shadows and complexity of islands in multiboundary wormholes
Bhattacharya, A., Chanda, A., Maulik, S., Northe, C., & Roy, S. (2021) · Journal of High Energy Physics · doi:10.1007/jhep02(2021)152 · Cited by 50
Yoshida, B. (2019) · Journal of High Energy Physics · doi:10.1007/jhep10(2019)132 · Cited by 57
Finding pythons in unexpected places
Engelhardt, N., Penington, G., & Shahbazi-Moghaddam, A. (2022) · Classical and Quantum Gravity · doi:10.1088/1361-6382/ac3e75 · Cited by 43
“…relation between exponential complexity and nonminimal QESs can be motivated from the apparent contradiction between prior holographic complexity proposals (such as CV [35, 36] or CA [37]) and the Harlow–Hayden conjecture [38] that reconstruction of the Hawking radiation is exponentially complex.”
Island for gravitationally prepared state and pseudo entanglement wedge
Miyaji, M. (2021) · Journal of High Energy Physics · doi:10.1007/jhep12(2021)013 · Cited by 49
WdW-patches in AdS3 and complexity change under conformal transformations II
Flory, M. (2019) · Journal of High Energy Physics · doi:10.1007/jhep05(2019)086 · Cited by 43
“Ideas relating to such notions of complexity entered the holography literature in [3–5], see [6] for a recent overview.”
BackgroundSpread and spectral complexity in quantum spin chains: from integrability to chaos
Camargo, H. A., Huh, K.-B., Jahnke, V., Jeong, H.-S., Kim, K.-Y., & Nishida, M. (2024) · Journal of High Energy Physics · doi:10.1007/jhep08(2024)241 · Cited by 67
“…codimension-0 and codimension-1 surfaces in probing holographic spacetimes beyond the black hole horizon was highlighted almost a decade ago [1–6] and since then, the notion of holographic complexity has been generalized for infinite classes of codimension-0 and codimension-1 gravitational…”
BackgroundTowards the quantum-enabled technologies for development of drugs or delivery systems
Hassanzadeh, P. (2020) · Journal of Controlled Release · doi:10.1016/j.jconrel.2020.04.050 · Cited by 47
Hawking radiation correlations of evaporating black holes in JT gravity
Hollowood, T. J., Kumar, S. P., & Legramandi, A. (2020) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8121/abbc51 · Cited by 36
“This is what is expected: the entangled modes RB should be difficult to extract from the early radiation [14].”
BackgroundTime evolution of the complexity in chaotic systems: a concrete example
Yang, R.-Q., & Kim, K.-Y. (2020) · Journal of High Energy Physics · doi:10.1007/jhep05(2020)045 · Cited by 43
Treiblmaier, H., Swan, M., Filippi, P. D., Lacity, M. C., T, T. H. M. I., & Kim, H. (2021) · ACM SIGMIS Database the DATABASE for Advances in Information Systems · doi:10.1145/3447934.3447938 · Cited by 57
“A landmark example is Harlow & Hayden proposing (2013) a resolution to a problem in the study of black holes, suggesting with an information theoretic analysis that although it would be possible to obtain information about a particle radiating out of a black hole, it would not be possible to do so…”
BackgroundBranches of the black hole wave function need not contain firewalls
Bao, N., Carroll, S. M., Chatwin-Davies, A., Pollack, J., & Remmen, G. N. (2018) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.97.126014 · Cited by 39
“Several different resolutions to this puzzle have been proposed,1 from those that modify quantum mechanics [9, 10], to those that allow a breakdown of no drama [5] or of unitarity [11], identify the early Hawking radiation with the black hole interior [12], modify the interior geometry [13–15], invoke quantum complexi…”
BackgroundAn uneventful horizon in two dimensions
Almheiri, A., & Sully, J. (2014) · Journal of High Energy Physics · doi:10.1007/jhep02(2014)108 · Cited by 33
Complexity of AdS5 black holes with a rotating string
Nagasaki, K. (2017) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.96.126018 · Cited by 32
“The growth of complexity is related to problems of black holes, for example, information problem, the transparency of horizons or the existence of firewalls [7, 8, 9, 10, 11].”
BackgroundEntanglement islands in generalized two-dimensional dilaton black holes
Yu, M., & Ge, X.-H. (2023) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.107.066020 · Cited by 46
“Although many different solutions are proposed, all have some flaws [87, 88].”
BackgroundPure states and black hole complementarity
Lowe, D. A., & Thorlacius, L. (2013) · Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields · doi:10.1103/physrevd.88.044012 · Cited by 34
Soft mode and interior operator in the Hayden-Preskill thought experiment
Yoshida, B. (2019) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.100.086001 · Cited by 45
Modular discretization of the AdS2/CFT1 holography
Axenides, M., Floratos, E. G., & Nicolis, S. (2014) · Journal of High Energy Physics · doi:10.1007/jhep02(2014)109 · Cited by 29
Backdraft: String Creation in an Old Schwarzschild Black HolePreprint
Silverstein, E. M. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.1486 · Cited by 40
Holographic purification complexity
Cáceres, E., Couch, J., Eccles, S., & Fischler, W. (2019) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.99.086016 · Cited by 32
“[1] D.”
BackgroundKrylov complexity of modular Hamiltonian evolution
Caputa, P., Magán, J. M., Patramanis, D., & Tonni, E. (2024) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.109.086004 · Cited by 44
“38 (1999) 1113] [arXiv:hep-th/9711200]; [5] D.”
Reanalyzing an evaporating black hole
Nomura, Y. (2019) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.99.086004 · Cited by 35
“[51–54].”
BackgroundOpen Problems Related to Quantum Query Complexity
Aaronson, S. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3488559 · Cited by 69
Bravo‐Gaete, M., & Santos, F. F. (2022) · The European Physical Journal C · doi:10.1140/epjc/s10052-022-10064-y · Cited by 31
Butterflies on the Stretched HorizonPreprint
Susskind, L. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.7379 · Cited by 44
“Any unitary operator can be implemented with an exponential number of gates [2][29][30][31].”
BackgroundHomology conditions for RT surfaces in double holography
Neuenfeld, D. (2022) · Classical and Quantum Gravity · doi:10.1088/1361-6382/ac51e7 · Cited by 25
“And in fact, the idea that computational complexity or the complexity of operators plays an important role in the validity of semi-classical gravity is a recurring theme [85, 89].”
Entropy of a vacuum: What does the covariant entropy count?
Nomura, Y., & Weinberg, S. J. (2014) · Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields · doi:10.1103/physrevd.90.104003 · Cited by 28
Black holes or firewalls: A theory of horizons
Nomura, Y., Varela, J., & Weinberg, S. J. (2013) · Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields · doi:10.1103/physrevd.88.084052 · Cited by 27
Fast optimization algorithms and the cosmological constant
Bao, N., Bousso, R., Jordan, S. P., & Lackey, B. (2017) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.96.103512 · Cited by 32
Complexity from spinning primaries
Koch, R. D. M., Kim, M., & Zyl, H. J. R. V. (2021) · Journal of High Energy Physics · doi:10.1007/jhep12(2021)030 · Cited by 26
“Another important measure of quantum information is quantum computational complexity [13].”
BackgroundPage curve of effective Hawking radiation
Chou, C.-J., Lao, H. B., & Yang, Y. (2022) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.106.066008 · Cited by 34
Measurements without probabilities in the final state proposal
Bousso, R., & Stanford, D. (2014) · Physical Review D · doi:10.1103/physrevd.89.044038 · Cited by 25
“However, the computational obstacles of [17] appear to be surmountable in the “laboratory” setting of a large black hole in an AdS box [18].”
BackgroundMethodComplexity growth of rotating black holes with a probe string
Nagasaki, K. (2018) · Physical review. D/Physical review. D. · doi:10.1103/physrevd.98.126014 · Cited by 25
“Complexity is realized as an important quantity for studying the structure of black hole spacetime — the Einstein-Rosen bridge [23, 24, 25, 26, 27, 28, 29, 30, 31], which is a structure of connecting two external black holes thought to be equivalent to entangled pair of particles (ER = EPR) [32].”
Background
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.