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:2304.09900 · SciPost Physics

Constraints on physical computers in holographic spacetimes

Aleksander M. Kubicki, Alex May, David Pérez-Garcı́a

Published Jan 23, 2024• 2 citations
arXivHTMLPDF

Abstract

Within the setting of the AdS/CFT correspondence, we ask about the power of computers in the presence of gravity. We show that there are computations on n n qubits which cannot be implemented inside of black holes with entropy less than O(2^n) O ( 2 n ) . To establish our claim, we argue computations happening inside the black hole must be implementable in a programmable quantum processor, so long as the inputs and description of the unitary to be run are not too large. We then prove a bound on quantum processors which shows many unitaries cannot be implemented inside the black hole, and further show some of these have short descriptions and act on small systems. These unitaries with short descriptions must be computationally forbidden from happening inside the black hole.

DOI
10.21468/scipostphys.16.1.024

Related papers

Entanglement, Complexity, and Holography

Mudassir Moosa

It was found, by studying black holes, that the compatibility of the theory of gravity and the laws of quantum mechanics demands that the universe must act like a hologram. That is, all the information inside a region of the universe should be encoded on a so-called holographic screen of one-lesser dimension. This is termed the holographic principle. In a generic spacetime, such as an expanding universe, holographic screens depend on the choice of an observer, which is consistent with the notion that the observer is part of the system in cosmology. In the first part of this dissertation, we study the observer-dependence of holographic screens. This will help us understand how the fundamental description of the universe depends on the choice of the observer. Furthermore, we study the dynamics of the holographic screens and their geometry in the first part of this dissertation.An example where the holographic principle is manifest is the AdS-CFT correspondence. This correspondence connects quantum information quantities, like entanglement and complexity, to geometric quantities, like area and volume, respectively. In the second and the third part of this dissertation, we use the AdS-CFT correspondence as a tool to calculate the entanglement entropy and the computational complexity of a quenched CFT state. Studying the time evolution of the entanglement entropy following a quantum quench teaches us how a CFT state thermalizes. On the other hand, studying the time evolution of the computational complexity allows us to check the validity of various recent conjectures involving black holes and complexity.

•Aug 18, 2018•0 citations

Complexity and entanglement in non-local computation and holography

Alex May

Does gravity constrain computation? We study this question using the AdS/CFT correspondence, where computation in the presence of gravity can be related to non-gravitational physics in the boundary theory. In AdS/CFT, computations which happen locally in the bulk are implemented in a particular non-local form in the boundary, which in general requires distributed entanglement. In more detail, we recall that for a large class of bulk subregions the area of a surface called the ridge is equal to the mutual information available in the boundary to perform the computation non-locally. We then argue the complexity of the local operation controls the amount of entanglement needed to implement it non-locally, and in particular complexity and entanglement cost are related by a polynomial. If this relationship holds, gravity constrains the complexity of operations within these regions to be polynomial in the area of the ridge.

arXiv:2204.00908•Quantum•Nov 28, 2022•23 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

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

Breakdown of quantum mechanics in gravitational holography

Akal, Abram

According to the holographic principle, the information content assigned to a gravitational region is processed by its lower dimensional boundary. As an example setup compatible with this principle, the AdS/CFT correspondence relies on the existence of D-branes in superstring theory. Black hole complementarity is inevitably linked to holography and states that information associated with the collapsed pure state is reflected in the near horizon region. Yet, if this is so, it is indispensable to understand the mechanism that makes black holes viewed from the outside evolve unitarily. We here argue that the information preserving quantum atmosphere of the black hole emerges from hidden variables on its horizon which would necessitate going beyond a probabilistic description within standard quantum theory. In AdS/CFT, this would mean that the completion of the semiclassical subalgebra to the complete boundary algebra has to be traced back to the emergent near horizon Hilbert space structure. The present investigations suggest that spacetime horizons, in general, may play a crucial role in restoring a long speculated ontology in quantum mechanics.

arXiv:2208.01019•Aug 1, 2022•0 citations

A Covariant Holographic Entanglement Entropy Proposal

Veronika E. Hubeny, Mukund Rangamani, Tadashi Takayanagi

With an aim towards understanding the time-dependence of entanglement entropy in generic quantum field theories, we propose a covariant generalization of the holographic entanglement entropy proposal of hep-th/0603001. Apart from providing several examples of possible covariant generalizations, we study a particular construction based on light-sheets, motivated in similar spirit to the covariant entropy bound underlying the holographic principle. In particular, we argue that the entanglement entropy associated with a specified region on the boundary in the context of the AdS/CFT correspondence is given by the area of a co-dimension two bulk surface with vanishing expansions of null geodesics. We demonstrate our construction with several examples to illustrate its reduction to the holographic entanglement entropy proposal in static spacetimes. We further show how this proposal may be used to understand the time evolution of entanglement entropy in a time varying QFT state dual to a collapsing black hole background. Finally, we use our proposal to argue that the Euclidean wormhole geometries with multiple boundaries should be regarded as states in a non-interacting but entangled set of QFTs, one associated to each boundary.

•Jan 1, 2008•977 citations
Within the setting of the AdS/CFT correspondence, we ask about the power of computers in the presence of gravity. We show that there are computations on n n qubits which cannot be implemented inside of black holes with entropy less than O(2^n) O ( 2 n ) . To establish our claim, we argue computations happening inside the black hole must be implementable in a programmable quantum processor, so long as the inputs and description of the unitary to be run are not too large. We then prove a bound on quantum processors which shows many unitaries cannot be implemented inside the black hole, and further show some of these have short descriptions and act on small systems. These unitaries with short descriptions must be computationally forbidden from happening inside the black hole.
It was found, by studying black holes, that the compatibility of the theory of gravity and the laws of quantum mechanics demands that the universe must act like a hologram. That is, all the information inside a region of the universe should be encoded on a so-called holographic screen of one-lesser dimension. This is termed the holographic principle. In a generic spacetime, such as an expanding universe, holographic screens depend on the choice of an observer, which is consistent with the notion that the observer is part of the system in cosmology. In the first part of this dissertation, we study the observer-dependence of holographic screens. This will help us understand how the fundamental description of the universe depends on the choice of the observer. Furthermore, we study the dynamics of the holographic screens and their geometry in the first part of this dissertation.An example where the holographic principle is manifest is the AdS-CFT correspondence. This correspondence connects quantum information quantities, like entanglement and complexity, to geometric quantities, like area and volume, respectively. In the second and the third part of this dissertation, we use the AdS-CFT correspondence as a tool to calculate the entanglement entropy and the computational complexity of a quenched CFT state. Studying the time evolution of the entanglement entropy following a quantum quench teaches us how a CFT state thermalizes. On the other hand, studying the time evolution of the computational complexity allows us to check the validity of various recent conjectures involving black holes and complexity.
Does gravity constrain computation? We study this question using the AdS/CFT correspondence, where computation in the presence of gravity can be related to non-gravitational physics in the boundary theory. In AdS/CFT, computations which happen locally in the bulk are implemented in a particular non-local form in the boundary, which in general requires distributed entanglement. In more detail, we recall that for a large class of bulk subregions the area of a surface called the ridge is equal to the mutual information available in the boundary to perform the computation non-locally. We then argue the complexity of the local operation controls the amount of entanglement needed to implement it non-locally, and in particular complexity and entanglement cost are related by a polynomial. If this relationship holds, gravity constrains the complexity of operations within these regions to be polynomial in the area of the ridge.
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.
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.
According to the holographic principle, the information content assigned to a gravitational region is processed by its lower dimensional boundary. As an example setup compatible with this principle, the AdS/CFT correspondence relies on the existence of D-branes in superstring theory. Black hole complementarity is inevitably linked to holography and states that information associated with the collapsed pure state is reflected in the near horizon region. Yet, if this is so, it is indispensable to understand the mechanism that makes black holes viewed from the outside evolve unitarily. We here argue that the information preserving quantum atmosphere of the black hole emerges from hidden variables on its horizon which would necessitate going beyond a probabilistic description within standard quantum theory. In AdS/CFT, this would mean that the completion of the semiclassical subalgebra to the complete boundary algebra has to be traced back to the emergent near horizon Hilbert space structure. The present investigations suggest that spacetime horizons, in general, may play a crucial role in restoring a long speculated ontology in quantum mechanics.
With an aim towards understanding the time-dependence of entanglement entropy in generic quantum field theories, we propose a covariant generalization of the holographic entanglement entropy proposal of hep-th/0603001. Apart from providing several examples of possible covariant generalizations, we study a particular construction based on light-sheets, motivated in similar spirit to the covariant entropy bound underlying the holographic principle. In particular, we argue that the entanglement entropy associated with a specified region on the boundary in the context of the AdS/CFT correspondence is given by the area of a co-dimension two bulk surface with vanishing expansions of null geodesics. We demonstrate our construction with several examples to illustrate its reduction to the holographic entanglement entropy proposal in static spacetimes. We further show how this proposal may be used to understand the time evolution of entanglement entropy in a time varying QFT state dual to a collapsing black hole background. Finally, we use our proposal to argue that the Euclidean wormhole geometries with multiple boundaries should be regarded as states in a non-interacting but entangled set of QFTs, one associated to each boundary.