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.
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.
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.
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.
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.
Fast scrambling and exponential growth of complexity are two distinctive features of quantum gravity, offering a unique window into the mechanisms that govern the semiclassical limit of the holographic duality. In this thesis, we explore these information-theoretic phenomena through two key diagnostics --- out-of-time ordered correlation functions (OTOCs) and spread complexity --- computed in the setting of two-dimensional holographic conformal field theories (CFTs). First, we focus on the large-c limit of Liouville theory, where the computation of OTOCs reveals distinctive insights into both the chaotic nature and the structural features of the theory. Remarkably, we find it exhibits a maximal Lyapunov exponent, despite lacking the identity operator in its spectrum, and a scrambling time logarithmic in the central charge. Using path integral techniques, we calculate heavy-light four-point functions, and uncover a conformal block expansion dominated by the exchange of an infinite tower of spinless double-trace operators. We attribute the chaotic behaviour of the OTOC to this exchange of operators, which can be thought of as dressed scramblons. Additionally, we observe that at the onset of scrambling, the dominance of conformal blocks shifts from heavy primaries at early times to light primaries at late times. Second, we turn to the diagnostic of spread complexity in locally excited holographic CFTs and argue that its time derivative is dual to the proper radial momentum of a massive point particle propagating in Anti-de Sitter spacetime (AdS). Exploiting the conformal symmetry and the emergence of an ``effective'' SL(2,R) group, we employ representation-theoretic techniques to compute return amplitudes, Lanczos coefficients, and spread complexities. We then verify our conjectured duality for three settings: the CFT on the line, dual to Poincaré AdS; the CFT on the circle, dual to global AdS; and the CFT at finite temperature, dual to a BTZ black hole. In the gravitational theory, the same SL(2,R) structure emerges as the isometry group of the infalling plane of the bulk particle. Third, we generalise the analysis of spread complexity to modular Hamiltonian evolution. Exploiting the rich algebraic structure of modular theory, we construct the modular Hamiltonians Kₘ and the half-sided modular translations G for the three example states above. Leveraging conformal symmetry, we once again compute modular return amplitudes, Lanczos coefficients, and modular spread complexities. In particular, we emphasise the role of ``conformal regularisation'' --- i.e. regulating with the operator that generates modular evolution - in preserving the effective SL(2,R) structure of the amplitudes. We find that evolution under Kₘ exhibits thermal spread complexity for β = 1 across all examples, while G-evolution universally leads to quadratic growth. Finally, we provide a formal explanation of these results, identifying the role of the Killing norm D of the evolution operator as the key factor governing the behaviour of complexity.
In this thesis we apply techniques from quantum information theory to study quantum gravity within the framework of the anti-de Sitter / conformal field theory correspondence (AdS/CFT). Through AdS/CFT, progress has been made in understanding the structure of entanglement in quantum field theories, and in how gravitational physics can emerge from these structures. However, this understanding is far from complete and will require the development of new tools to quantify correlations in CFT. This thesis presents refinements of a duality between operator product expansion (OPE) blocks in the CFT, giving the contribution of a conformal family to the OPE, and geodesic integrated fields in AdS which are diffeomorphism invariant quantities. This duality was originally discovered in the maximally symmetric setting of pure AdS dual to the CFT ground state. In less symmetric states the duality must be modified. Working with excited states within AdS3/CFT2, this thesis shows how the OPE block decomposes into more fine-grained CFT observables that are dual to AdS fields integrated over non-minimal geodesics. Additionally, this thesis contains results on the dynamics of entanglement measures for general quantum systems. Results are presented for the family of quantum Rényi entropies and entanglement negativity. Rényi entropies are studied for general dynamics by imposing special initial conditions. Around pure, separable initial states, all Rényi entropies grow with the same timescale at leading, and next-to-leading order. Mathematical tools are developed for the differentiation of non-analytic matrix functions with respect to constrained arguments and are used to construct analytic expressions for derivatives of negativity. We establish bounds on the rate of change of state distinguishability and the rate of entanglement growth for closed systems. Note: Abstract shortened.