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.
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.
In this Dissertation, different aspects of holographic entanglement entropy are explored. In quantum information theory, entanglement is a useful resource needed to perform quantum operations. Entanglement entropy quantifies this resource and even if computable in quantum field theories, it is quite hard to calculate explicitly. However, in the context of gauge/gravity duality, (holographic) entanglement entropy was proposed by Ryu and Takayanagi (RT) to be captured by the area of a minimal surface in Anti DeSitter (AdS) space, which is extremely simple to compute. We begin by using the holographic dictionary to derive the RT formula. This is done by first considering smooth bulk geometries which are dual to n copies of the boundary geometry glued in a particular way. The action of these geometries computes the Renyi entropies S_n for any integer n. We give a prescription to analytically continue the action to non-integer n and argue that, as n goes to 1,S_1, the entanglement entropy, is given by the area of a minimal surface, reproducing the RT conjecture. That is, we reduced the RT proposal to the equality between bulk and boundary partition functions, a standard entry in the dictionary. We then generalize the previous formalism to account for corrections due to bulk quantum fields (1/N corrections in the boundary). This allows us to derive a new formula: boundary entanglement entropy is given by the area of the minimal surface plus bulk entanglement entropy. This extends RT beyond the planar limit and we present several predictions of the proposal. Our exploration of holographic entanglement entropy continues by considering different states: by comparing the quantum corrected entropy for nearby states we obtain the modular hamiltonian operator in bulk perturbation theory. From this expression of the modular hamiltonian, we derive that relative entropy is bulk relative entropy and that the modular flow is the bulk modular flow.
This dissertation reviews several recent advances at the intersection of quantum information and holography. In holography, properties of quantum systems admit a gravitational interpretation via the AdS/CFT correspondence. For holographic states, boundary entanglement entropy is dual to bulk geodesic areas, known as Ryu-Takayanagi surfaces. Furthermore, the viability to possess a holographic dual at all is constrained by entanglement structure. Accordingly, entanglement enables a coarse classification of states in a Hilbert space. Similarly, state transformation under operator groups also provides a classification on the Hilbert space. Stabilizer states, for example, are invariant under large sets of operations and consequently can be simulated on a classical computer. Cayley graphs offer a useful representation for a group of operators, where vertices represent group elements and edges represent generators. The orbit of a state under action of the group can also be represented as a "reachability graph", a quotient of the group Cayley graph. Reachability graphs can be dressed to encode entanglement information, making them a useful tool for studying entanglement dynamics. Quotienting a reachability graph by group elements that fix a state computable, e.g. entanglement entropy, builds a "contracted graph". Contracted graphs explicitly bound state parameter evolution in quantum circuits. In this thesis, an upper bound on entanglement entropy evolution in Clifford circuits is presented. Another important property of quantum systems is magic, which quantifies the difficulty of simulating a quantum state. Magic and entanglement play complementary roles when describing emergent phenomena in AdS/CFT. This work describes the interplay of entanglement and magic, offering holographic consequences for magic as cosmic brane back-reaction.
Entanglement entropy of holographic CFTs is expected to play a crucial role in the reconstruction of semiclassical bulk gravity. We consider the entanglement entropy of spherical regions of vacuum, which is known to contain universal contributions. After perturbing the CFT with a relevant scalar operator, also the first order change of this quantity gives a universal term which only depends on a discrete set of basic CFT parameters. We show that in gravity this statement corresponds to the uniqueness of the ghost-free graviton propagator on an AdS background geometry. While the gravitational dynamics in this context contains little information about the structure of the bulk theory, there is a discrete set of dimensionless parameters of the theory which determines the entanglement entropy. We argue that for every (not necessarily holographic) CFT, any reasonable gravity model can be used to compute this particular entanglement entropy. We elucidate how this statement is consistent with AdS/CFT and also give various generalizations. On the one hand this illustrates the remarkable usefulness of geometric concepts for understanding entanglement in general CFTs. On the other hand, it provides hints as to what entanglement data can be expected to provide enough information to distinguish, e.g., bulk theories with different higher curvature couplings.
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.
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.
Holographic quantum error-correcting code, the quantum-information structure hypothesized for the AdS/CFT correspondence, has being attracting increasing attention in new directions interrelating the studies of quantum gravity and quantum simulation. In this work, we initiate a novel approach for building holographic code that can be generally applied in potentially broad and interdisciplinary contexts. Our approach takes an "opposite" route to the conventional paradigm that is based on bulk tensor-networks. As illustrated in an exact model, we start from scalable descriptions of boundary qudits which can guide succinct quantum-circuit simulations, and rigorously show how the bulk qudits and the encoding structure emerge from boundary entanglement patterns. By investigating the entanglement patterns, we systematically unfold the hypothetical structure for bulk reconstruction and the details of the Ryu-Takayanagi formula in the formalism of operator-algebra quantum error correction, demonstrating desired properties that are not yet proved in the established models. Our work might offer a fresh perspective for the study of holographic code.