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:1810.11563

Three Lectures on Complexity and Black Holes

Leonard Susskind

Published Oct 27, 2018• 32 citations
arXivHTMLPDF

Abstract

Given at PiTP 2018 summer program entitled "From Qubits to Spacetime." The first lecture describes the meaning of quantum complexity, the analogy between entropy and complexity, and the second law of complexity. Lecture two reviews the connection between the second law of complexity and the interior of black holes. I discuss how firewalls are related to periods of non-increasing complexity which typically only occur after an exponentially long time. The final lecture is about the thermodynamics of complexity, and "uncomplexity" as a resource for doing computational work. I explain the remarkable power of "one clean qubit," in both computational terms and in space-time terms. The lectures can also be found online at \url{https://static.ias.edu/pitp/2018/node/1796.html} .

DOI
10.48550/arxiv.1810.11563

Related papers

Second law of quantum complexity

Adam R. Brown, Leonard Susskind

We give arguments for the existence of a thermodynamics of quantum complexity that includes a ``second law of complexity.'' To guide us, we derive a correspondence between the computational (circuit) complexity of a quantum system of $K$ qubits, and the positional entropy of a related classical system with ${2}^{K}$ degrees of freedom. We also argue that the kinetic entropy of the classical system is equivalent to the Kolmogorov complexity of the quantum Hamiltonian. We observe that the expected pattern of growth of the complexity of the quantum system parallels the growth of entropy of the classical system. We argue that the property of having less-than-maximal complexity (uncomplexity) is a resource that can be expended to perform directed quantum computation. Although this paper is not primarily about black holes, we find a surprising interpretation of the uncomplexity resource as the accessible volume of spacetime behind a black hole horizon.

arXiv:1701.01107•Physical review. D/Physical review. D.•Apr 25, 2018•292 citations

Uncomplexity and black hole geometry

Ying Zhao

We give a definition of uncomplexity of a mixed state without invoking any particular definitions of mixed state complexity and argue that it gives the amount of computational power Bob has when he only has access to part of a system. We find geometric meanings of our definition in various black hole examples and make a connection with subregion duality. We show that Bob's uncomplexity is the portion of his accessible interior spacetime inside his entanglement wedge. This solves a puzzle we encountered about the uncomplexity of the thermofield double state. In this process, we identify different kinds of operations Bob can do as being responsible for the growth of different parts of spacetime.

arXiv:1711.03125•Physical review. D/Physical review. D.•Jun 13, 2018•37 citations

Black Holes and Complexity Classes

Leonard Susskind

It is not known what the limitations are on using quantum computation to speed up classical computation. An example would be the power to speed up PSPACE-complete computations. It is also not known what the limitations are on the duration of time over which classical general relativity can describe the interior geometry of black holes. What is known is that these two questions are closely connected: the longer GR can describe black holes, the more limited are quantum computers. This conclusion, formulated as a theorem, is a result of unpublished work done by Scott Aaronson and myself which I explain here.

arXiv:1802.02175•Feb 6, 2018•21 citations

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 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

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
Given at PiTP 2018 summer program entitled "From Qubits to Spacetime." The first lecture describes the meaning of quantum complexity, the analogy between entropy and complexity, and the second law of complexity. Lecture two reviews the connection between the second law of complexity and the interior of black holes. I discuss how firewalls are related to periods of non-increasing complexity which typically only occur after an exponentially long time. The final lecture is about the thermodynamics of complexity, and "uncomplexity" as a resource for doing computational work. I explain the remarkable power of "one clean qubit," in both computational terms and in space-time terms. The lectures can also be found online at \url{https://static.ias.edu/pitp/2018/node/1796.html} .
We give arguments for the existence of a thermodynamics of quantum complexity that includes a ``second law of complexity.'' To guide us, we derive a correspondence between the computational (circuit) complexity of a quantum system of KKK qubits, and the positional entropy of a related classical system with 2K{2}^{K}2K degrees of freedom. We also argue that the kinetic entropy of the classical system is equivalent to the Kolmogorov complexity of the quantum Hamiltonian. We observe that the expected pattern of growth of the complexity of the quantum system parallels the growth of entropy of the classical system. We argue that the property of having less-than-maximal complexity (uncomplexity) is a resource that can be expended to perform directed quantum computation. Although this paper is not primarily about black holes, we find a surprising interpretation of the uncomplexity resource as the accessible volume of spacetime behind a black hole horizon.
We give a definition of uncomplexity of a mixed state without invoking any particular definitions of mixed state complexity and argue that it gives the amount of computational power Bob has when he only has access to part of a system. We find geometric meanings of our definition in various black hole examples and make a connection with subregion duality. We show that Bob's uncomplexity is the portion of his accessible interior spacetime inside his entanglement wedge. This solves a puzzle we encountered about the uncomplexity of the thermofield double state. In this process, we identify different kinds of operations Bob can do as being responsible for the growth of different parts of spacetime.
It is not known what the limitations are on using quantum computation to speed up classical computation. An example would be the power to speed up PSPACE-complete computations. It is also not known what the limitations are on the duration of time over which classical general relativity can describe the interior geometry of black holes. What is known is that these two questions are closely connected: the longer GR can describe black holes, the more limited are quantum computers. This conclusion, formulated as a theorem, is a result of unpublished work done by Scott Aaronson and myself which I explain here.
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.
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.
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.