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• 165 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•378 citations

BLACK HOLES AND QUBITS

L. Borsten, M. J. Duff, W. Rubens

These notes have been compiled to accompany a series of four lectures given at the Kinki University Quantum Computing Series Summer School on Decoherence, Entanglement and Entropy, August 2009 at the Oxford Kobe Institute (Kobe, Japan). Each of the four lectures focuses on a particular topic falling under the broad umbrella of the "black-hole/qubit correspondence". Lecture I introduces the first instance of the black-hole/qubit correspondence, the relationship between the entanglement of three qubits and the entropy of STU black holes. Lecture II develops this correspondence to the case of black holes and the tripartite entanglement of seven qubits. Lecture III examines the use of Jordan algebras and the Freudenthal triple system, which capture the U -duality symmetries of these black hole systems, in entanglement classification. Lecture IV introduces the superqubit, a natural candidate to represent supersymmetric quantum information. These lectures draw on work done with D. Dahanayake, H. Ebrahim, S. Ferrara and A. Marrani whose efforts are most gratefully acknowledged.

•Jul 16, 2012•1 citation

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•39 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•62 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

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
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.
These notes have been compiled to accompany a series of four lectures given at the Kinki University Quantum Computing Series Summer School on Decoherence, Entanglement and Entropy, August 2009 at the Oxford Kobe Institute (Kobe, Japan). Each of the four lectures focuses on a particular topic falling under the broad umbrella of the "black-hole/qubit correspondence". Lecture I introduces the first instance of the black-hole/qubit correspondence, the relationship between the entanglement of three qubits and the entropy of STU black holes. Lecture II develops this correspondence to the case of black holes and the tripartite entanglement of seven qubits. Lecture III examines the use of Jordan algebras and the Freudenthal triple system, which capture the U -duality symmetries of these black hole systems, in entanglement classification. Lecture IV introduces the superqubit, a natural candidate to represent supersymmetric quantum information. These lectures draw on work done with D. Dahanayake, H. Ebrahim, S. Ferrara and A. Marrani whose efforts are most gratefully acknowledged.
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.
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.
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.