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.
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 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.
This work is originally a Cambridge Part III essay paper. Quantum complexity arises as an alternative measure to the Fubini metric between two quantum states. Given two states and a set of allowed gates, it is defined as the least complex unitary operator capable of transforming one state into the other. Starting with K qubits evolving through a k-local Hamiltonian, it is possible to draw an analogy between the quantum system and an auxiliary classical system. Using the definition of complexity to define a metric for the classical system, it is possible to relate its entropy with the quantum complexity of the K qubits, defining the Second Law of Quantum Complexity. The law states that, if it is not already saturated, the quantum complexity of a system will increase with an overwhelming probability towards its maximum value. In the context of AdS/CFT duality and the ER=EPR conjecture, the growth of the volume of the Einstein Rosen bridge interior is proportional to the quantum complexity of the instantaneous state of the conformal field theory. Therefore, the interior of the wormhole connecting two entangled CFT will grow as a natural consequence of the complexification of the boundary state.
The `quantum gravity in the lab' paradigm suggests that quantum computers might shed light on quantum gravity by simulating the CFT side of the AdS/CFT correspondence and mapping the results to the AdS side. This relies on the assumption that the duality map (the `dictionary') is efficient to compute. In this work, we show that the complexity of the AdS/CFT dictionary is surprisingly subtle: there might be cases in which one can efficiently apply operators to the CFT state (a task we call 'operator reconstruction') without being able to extract basic properties of the dual bulk state such as its geometry (which we call 'geometry reconstruction'). Geometry reconstruction corresponds to the setting where we want to extract properties of a completely unknown bulk dual from a simulated CFT boundary state. We demonstrate that geometry reconstruction may be generically hard due to the connection between geometry and entanglement in holography. In particular we construct ensembles of states whose entanglement approximately obey the Ryu-Takayanagi formula for arbitrary geometries, but which are nevertheless computationally indistinguishable. This suggests that even for states with the special entanglement structure of holographic CFT states, geometry reconstruction might be hard. This result should be compared with existing evidence that operator reconstruction is generically easy in AdS/CFT. A useful analogy for the difference between these two tasks is quantum fully homomorphic encryption (FHE): this encrypts quantum states in such a way that no efficient adversary can learn properties of the state, but operators can be applied efficiently to the encrypted state. We show that quantum FHE can separate the complexity of geometry reconstruction vs operator reconstruction, which raises the question whether FHE could be a useful lens through which to view AdS/CFT.
[This is a creative exploration of a concept with AI -it should not be taken as correct mathematics.] We present a detailed examination of the conjectured correspondence between Einstein-Rosen (ER) bridges and Einstein-Podolsky-Rosen (EPR) entanglement, denoted as ER=EPR. This examination concentrates on the quantitative structures and derivations supporting this correspondence, primarily within the setting of the Anti-de Sitter/Conformal Field Theory (AdS/CFT) duality. We analyze the realization of this correspondence in the eternal black hole geometry and its dual Thermofield Double (TFD) state. A complete exposition of the holographic entanglement entropy prescriptions is provided, including the derivation of the Quantum Extremal Surface (QES) prescription via the Lewkowycz-Maldacena argument concerning the gravitational path integral and conical singularities, and the subsequent derivation of the Jafferis-Lewkowycz-Maldacena-Suh (JLMS) relation establishing the equality of bulk and boundary relative entropies. We investigate the relationship between the temporal evolution of the spacetime geometry, characterized by the growth of the Einstein-Rosen bridge, and the evolution of quantum complexity. A complete derivation of the maximal volume growth rate is provided, carefully analyzing the geometry inside the horizon. Furthermore, a complete derivation of the action growth rate, supporting the Complexity=Action conjecture, is provided, clarifying the precise contribution of bulk, boundary, and joint terms in the gravitational action according to the definitions established by Lehner et al. for manifolds with null boundaries. The correspondence is extended to typical entangled states, characterized by Einstein-Rosen caterpillars. We derive the effective Hamiltonian governing the ensemble average of the generating random circuits and establish the quantitative relationship between the geometric length of the wormhole and the measure of quantum randomness (k-designs), utilizing the results of Magán, Sasieta, and Swingle. The role of QES and the derivation of the Page curve via replica wormholes are analyzed, detailing the calculations in Jackiw-Teitelboim gravity theories following Penington et al. Mechanisms for rendering wormholes traversable via boundary interactions (Gao-Jafferis-Wall construction) and operational interpretations based on Local Operationsand Classical Communication protocols are also discussed, emphasizing the quantitative consistency of these interconnected concepts.
A bstract Within the AdS/CFT correspondence, computational complexity for reduced density matrices of holographic conformal field theories has been conjectured to be related to certain geometric observables in the dual gravity theory. We study this conjecture from both the gravity and field theory point of view. Specifically, we consider a measure of complexity associated to the Bures metric on the space of density matrices. We compute this complexity measure for mixed states associated to single intervals in descendant states of the vacuum in 2d CFTs. Moreover, we derive from first principles a geometric observable dual to the Bures metric which is localized in the entanglement wedge of the AdS spacetime associated to the quantum circuit on the boundary. Finally, we compare the Bures metric complexity measure with holographic subregion complexity within the “complexity=volume” paradigm for perturbatively small transformations of the vacuum. While there is no exact agreement between these two quantities, we find striking similarities as we vary the target state and interval size, suggesting that these quantities are closely related.