Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2005.12491 · Journal of High Energy Physics

Remarks on black hole complexity puzzle

Beni Yoshida

Published Oct 1, 2020• 7 citations
arXivHTMLPDF

Abstract

Abstract Recently a certain conceptual puzzle in the AdS/CFT correspondence, concerning the growth of quantum circuit complexity and the wormhole volume, has been identified by Bouland-Fefferman-Vazirani and Susskind. In this note, we propose a resolution of the puzzle and save the quantum Extended Church-Turing thesis by arguing that there is no computational shortcut in measuring the volume due to gravitational backreaction from bulk observers. A certain strengthening of the firewall puzzle from the computational complexity perspective, as well as its potential resolution, is also presented.

DOI
10.1007/jhep10(2020)103

Related papers

Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

A fundamental issue in the AdS/CFT correspondence is the wormhole growth paradox. Susskind's conjectured resolution of the paradox was to equate the volume of the wormhole with the circuit complexity of its dual quantum state in the CFT. We study the ramifications of this conjecture from a complexity-theoretic perspective. Specifically we give evidence for the existence of computationally pseudorandom states in the CFT, and argue that wormhole volume is measureable in a non-physical but computational sense, by amalgamating the experiences of multiple observers in the wormhole. In other words the conjecture equates a quantity which is difficult to compute with one which is easy to compute. The pseudorandomness argument further implies that this is a necessary feature of any resolution of the wormhole growth paradox, not just of Susskind's Complexity=Volume conjecture. As a corollary we conclude that either the AdS/CFT dictionary map must be exponentially complex, or the quantum Extended Church-Turing thesis must be false in quantum gravity.

arXiv:1910.14646•Oct 31, 2019•21 citations

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract)

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

The AdS/CFT correspondence is central to efforts to reconcile gravity and quantum mechanics, a fundamental goal of physics. It posits a duality between a gravitational theory in Anti de Sitter (AdS) space and a quantum mechanical conformal field theory (CFT), embodied in a map known as the AdS/CFT dictionary mapping states to states and operators to operators. This dictionary map is not well understood and has only been computed on special, structured instances. In this work we introduce cryptographic ideas to the study of AdS/CFT, and provide evidence that either the dictionary must be exponentially hard to compute, or else the quantum Extended Church-Turing thesis must be false in quantum gravity. Our argument has its origins in a fundamental paradox in the AdS/CFT correspondence known as the wormhole growth paradox. The paradox is that the CFT is believed to be "scrambling" - i.e. the expectation value of local operators equilibrates in polynomial time - whereas the gravity theory is not, because the interiors of certain black holes known as "wormholes" do not equilibrate and instead their volume grows at a linear rate for at least an exponential amount of time. So what could be the CFT dual to wormhole volume? Susskind’s proposed resolution was to equate the wormhole volume with the quantum circuit complexity of the CFT state. From a computer science perspective, circuit complexity seems like an unusual choice because it should be difficult to compute, in contrast to physical quantities such as wormhole volume. We show how to create pseudorandom quantum states in the CFT, thereby arguing that their quantum circuit complexity is not "feelable", in the sense that it cannot be approximated by any efficient experiment. This requires a specialized construction inspired by symmetric block ciphers such as DES and AES, since unfortunately existing constructions based on quantum-resistant one way functions cannot be used in the context of the wormhole growth paradox as only very restricted operations are allowed in the CFT. By contrast we argue that the wormhole volume is "feelable" in some general but non-physical sense. The duality between a "feelable" quantity and an "unfeelable" quantity implies that some aspect of this duality must have exponential complexity. More precisely, it implies that either the dictionary is exponentially complex, or else the quantum gravity theory is exponentially difficult to simulate on a quantum computer. While at first sight this might seem to justify the discomfort of complexity theorists with equating computational complexity with a physical quantity, a further examination of our arguments shows that any resolution of the wormhole growth paradox must equate wormhole volume to an "unfeelable" quantity, leading to the same conclusions. In other words this discomfort is an inevitable consequence of the paradox.

Leibniz international proceedings in informatics•Jan 1, 2020•15 citations

Quantum computational complexity from quantum information to black holes and back

Shira Chapman, Giuseppe Policastro

Abstract Quantum computational complexity estimates the difficulty of constructing quantum states from elementary operations, a problem of prime importance for quantum computation. Surprisingly, this quantity can also serve to study a completely different physical problem – that of information processing inside black holes. Quantum computational complexity was suggested as a new entry in the holographic dictionary, which extends the connection between geometry and information and resolves the puzzle of why black hole interiors keep growing for a very long time. In this pedagogical review, we present the geometric approach to complexity advocated by Nielsen and show how it can be used to define complexity for generic quantum systems; in particular, we focus on Gaussian states in QFT, both pure and mixed, and on certain classes of CFT states. We then present the conjectured relation to gravitational quantities within the holographic correspondence and discuss several examples in which different versions of the conjectures have been tested. We highlight the relation between complexity, chaos and scrambling in chaotic systems. We conclude with a discussion of open problems and future directions. This article was written for the special issue of EPJ-C Frontiers in Holographic Duality.

arXiv:2110.14672•The European Physical Journal C•Feb 1, 2022•127 citations

Complexity and Entanglement in Quantum Gravity

Arjun Kar

We present a collection of recent results concerning quantum information theory applied to quantum gravity. We first study the entanglement structure of Euclidean path integral states in SU(2) Chern-Simons theory, where we elucidate a connection between topological entanglement and quantum mechanical entanglement. We prove that the topology of certain three-manifolds controls the entanglement structure of the resulting quantum state, and conjecture a more general relationship for arbitrary three-manifolds. We then analyze the quantum circuit complexity of the time evolution operator in the Sachdev-Ye-Kitaev model, a theory of near-extremal black hole microstates. We find that this complexity grows linearly for a time exponential in the entropy, modulo a caveat concerning global obstructions to the growth of the distance function along geodesics, which we do not rule out. This constitutes a partial proof of Susskind’s conjecture about the complexity growth of black holes. Finally, we address the black hole information paradox in three dimensions by considering a toy model of black hole microstates in the form of an end-of-the-world brane. This brane carries a quantum theory which is itself holographic, and we compute entanglement entropies in the glued dual geometry by using a Ryu-Takayanagi formula where the minimal entropy surface can pass through the gluing surface.

•Jan 1, 2020•0 citations

Scrambling and Complexity in AdS/CFT and Black Holes

Kento Watanabe

The AdS/CFT correspondence and quantum entanglement (or quantum information). This is one of topics exciting many physicists in this decade. And black holes always play a role of inspiring lab in many cases. In this thesis, we will discuss about scrambling of quantum entanglement and complexity of states in AdS/CFT. In both topics, black holes are expected to be the fastest processors of quantum information. This thesis contains brief reviews of each topics and our own works. One work is an explicit calculation of fast scrambling time in two dimensional holographic CFTs and three dimensional BTZ black holes using the two-sided mutual information. This calculation is a first CFT counterpart of Shenker-Stanford’s work in the gravity dual and an extension of their shock-wave approximation to finite time region in the gravity side. Another work is about socalled optimization procedure of Euclidean path- integrals in CFTs. The optimization procedure gives us a new way to extract dual geometries only from CFT data. And it also gives a new proposal for the definition of complexity of states in CFTs.

•Mar 26, 2018•0 citations

Krylov complexity and the growth of the black hole interior in 3D gravity

Arpan Bhattacharyya, Sounak Pal, Juan F. Pedraza

We investigate the growth of the black hole interior in three-dimensional gravity from the boundary theory. For the two-sided BTZ black hole, we propose a boundary reconstruction of the time dependence of a codimension-one surface in terms of correlation functions of smeared operators in the thermofield double state, reproducing the characteristic late-time linear growth predicted by the complexity-volume proposal. Using the Chern--Simons formulation of three-dimensional gravity, these nonlocal correlators are represented by bulk Wilson lines with smeared endpoints, extending the familiar connection between Wilson lines and codimension-two observables underlying holographic entanglement entropy to codimension-one observables. We then ask whether the same geometric growth is captured by Krylov complexity. For the smeared operators, we extract the Lanczos data from their correlation functions and find that operator Krylov complexity reproduces the late-time linear growth of the black hole interior, extending previous connections between operator growth and bulk geometry to AdS$_3$. By contrast, the Krylov spread complexity of the thermofield double state, obtained from the semiclassical gravitational partition function, does not exhibit the linear growth of the bulk volume within the regime accessible to our analysis. Our results therefore point to a distinguished role for operator Krylov complexity in encoding black hole interior growth beyond two-dimensional gravity, while highlighting a qualitative distinction between operator and state notions of Krylov complexity.

hep-thCross-listedarXiv:2608.19373•Aug 21, 2026
Abstract Recently a certain conceptual puzzle in the AdS/CFT correspondence, concerning the growth of quantum circuit complexity and the wormhole volume, has been identified by Bouland-Fefferman-Vazirani and Susskind. In this note, we propose a resolution of the puzzle and save the quantum Extended Church-Turing thesis by arguing that there is no computational shortcut in measuring the volume due to gravitational backreaction from bulk observers. A certain strengthening of the firewall puzzle from the computational complexity perspective, as well as its potential resolution, is also presented.
A fundamental issue in the AdS/CFT correspondence is the wormhole growth paradox. Susskind's conjectured resolution of the paradox was to equate the volume of the wormhole with the circuit complexity of its dual quantum state in the CFT. We study the ramifications of this conjecture from a complexity-theoretic perspective. Specifically we give evidence for the existence of computationally pseudorandom states in the CFT, and argue that wormhole volume is measureable in a non-physical but computational sense, by amalgamating the experiences of multiple observers in the wormhole. In other words the conjecture equates a quantity which is difficult to compute with one which is easy to compute. The pseudorandomness argument further implies that this is a necessary feature of any resolution of the wormhole growth paradox, not just of Susskind's Complexity=Volume conjecture. As a corollary we conclude that either the AdS/CFT dictionary map must be exponentially complex, or the quantum Extended Church-Turing thesis must be false in quantum gravity.
The AdS/CFT correspondence is central to efforts to reconcile gravity and quantum mechanics, a fundamental goal of physics. It posits a duality between a gravitational theory in Anti de Sitter (AdS) space and a quantum mechanical conformal field theory (CFT), embodied in a map known as the AdS/CFT dictionary mapping states to states and operators to operators. This dictionary map is not well understood and has only been computed on special, structured instances. In this work we introduce cryptographic ideas to the study of AdS/CFT, and provide evidence that either the dictionary must be exponentially hard to compute, or else the quantum Extended Church-Turing thesis must be false in quantum gravity. Our argument has its origins in a fundamental paradox in the AdS/CFT correspondence known as the wormhole growth paradox. The paradox is that the CFT is believed to be "scrambling" - i.e. the expectation value of local operators equilibrates in polynomial time - whereas the gravity theory is not, because the interiors of certain black holes known as "wormholes" do not equilibrate and instead their volume grows at a linear rate for at least an exponential amount of time. So what could be the CFT dual to wormhole volume? Susskind’s proposed resolution was to equate the wormhole volume with the quantum circuit complexity of the CFT state. From a computer science perspective, circuit complexity seems like an unusual choice because it should be difficult to compute, in contrast to physical quantities such as wormhole volume. We show how to create pseudorandom quantum states in the CFT, thereby arguing that their quantum circuit complexity is not "feelable", in the sense that it cannot be approximated by any efficient experiment. This requires a specialized construction inspired by symmetric block ciphers such as DES and AES, since unfortunately existing constructions based on quantum-resistant one way functions cannot be used in the context of the wormhole growth paradox as only very restricted operations are allowed in the CFT. By contrast we argue that the wormhole volume is "feelable" in some general but non-physical sense. The duality between a "feelable" quantity and an "unfeelable" quantity implies that some aspect of this duality must have exponential complexity. More precisely, it implies that either the dictionary is exponentially complex, or else the quantum gravity theory is exponentially difficult to simulate on a quantum computer. While at first sight this might seem to justify the discomfort of complexity theorists with equating computational complexity with a physical quantity, a further examination of our arguments shows that any resolution of the wormhole growth paradox must equate wormhole volume to an "unfeelable" quantity, leading to the same conclusions. In other words this discomfort is an inevitable consequence of the paradox.
Abstract Quantum computational complexity estimates the difficulty of constructing quantum states from elementary operations, a problem of prime importance for quantum computation. Surprisingly, this quantity can also serve to study a completely different physical problem – that of information processing inside black holes. Quantum computational complexity was suggested as a new entry in the holographic dictionary, which extends the connection between geometry and information and resolves the puzzle of why black hole interiors keep growing for a very long time. In this pedagogical review, we present the geometric approach to complexity advocated by Nielsen and show how it can be used to define complexity for generic quantum systems; in particular, we focus on Gaussian states in QFT, both pure and mixed, and on certain classes of CFT states. We then present the conjectured relation to gravitational quantities within the holographic correspondence and discuss several examples in which different versions of the conjectures have been tested. We highlight the relation between complexity, chaos and scrambling in chaotic systems. We conclude with a discussion of open problems and future directions. This article was written for the special issue of EPJ-C Frontiers in Holographic Duality.
We present a collection of recent results concerning quantum information theory applied to quantum gravity. We first study the entanglement structure of Euclidean path integral states in SU(2) Chern-Simons theory, where we elucidate a connection between topological entanglement and quantum mechanical entanglement. We prove that the topology of certain three-manifolds controls the entanglement structure of the resulting quantum state, and conjecture a more general relationship for arbitrary three-manifolds. We then analyze the quantum circuit complexity of the time evolution operator in the Sachdev-Ye-Kitaev model, a theory of near-extremal black hole microstates. We find that this complexity grows linearly for a time exponential in the entropy, modulo a caveat concerning global obstructions to the growth of the distance function along geodesics, which we do not rule out. This constitutes a partial proof of Susskind’s conjecture about the complexity growth of black holes. Finally, we address the black hole information paradox in three dimensions by considering a toy model of black hole microstates in the form of an end-of-the-world brane. This brane carries a quantum theory which is itself holographic, and we compute entanglement entropies in the glued dual geometry by using a Ryu-Takayanagi formula where the minimal entropy surface can pass through the gluing surface.
The AdS/CFT correspondence and quantum entanglement (or quantum information). This is one of topics exciting many physicists in this decade. And black holes always play a role of inspiring lab in many cases. In this thesis, we will discuss about scrambling of quantum entanglement and complexity of states in AdS/CFT. In both topics, black holes are expected to be the fastest processors of quantum information. This thesis contains brief reviews of each topics and our own works. One work is an explicit calculation of fast scrambling time in two dimensional holographic CFTs and three dimensional BTZ black holes using the two-sided mutual information. This calculation is a first CFT counterpart of Shenker-Stanford’s work in the gravity dual and an extension of their shock-wave approximation to finite time region in the gravity side. Another work is about socalled optimization procedure of Euclidean path- integrals in CFTs. The optimization procedure gives us a new way to extract dual geometries only from CFT data. And it also gives a new proposal for the definition of complexity of states in CFTs.
We investigate the growth of the black hole interior in three-dimensional gravity from the boundary theory. For the two-sided BTZ black hole, we propose a boundary reconstruction of the time dependence of a codimension-one surface in terms of correlation functions of smeared operators in the thermofield double state, reproducing the characteristic late-time linear growth predicted by the complexity-volume proposal. Using the Chern--Simons formulation of three-dimensional gravity, these nonlocal correlators are represented by bulk Wilson lines with smeared endpoints, extending the familiar connection between Wilson lines and codimension-two observables underlying holographic entanglement entropy to codimension-one observables. We then ask whether the same geometric growth is captured by Krylov complexity. For the smeared operators, we extract the Lanczos data from their correlation functions and find that operator Krylov complexity reproduces the late-time linear growth of the black hole interior, extending previous connections between operator growth and bulk geometry to AdS3_33​. By contrast, the Krylov spread complexity of the thermofield double state, obtained from the semiclassical gravitational partition function, does not exhibit the linear growth of the bulk volume within the regime accessible to our analysis. Our results therefore point to a distinguished role for operator Krylov complexity in encoding black hole interior growth beyond two-dimensional gravity, while highlighting a qualitative distinction between operator and state notions of Krylov complexity.