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:1711.03125 · Physical review. D/Physical review. D.

Uncomplexity and black hole geometry

Ying Zhao

Published Jun 13, 2018• 39 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevd.97.126007

Related papers

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•150 citations

Three Lectures on Complexity and Black Holes

Leonard Susskind

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

arXiv:1810.11563•Oct 27, 2018•165 citations

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

Null states from large superpositions of two-sided black holes

Gardiner, John G.

A standard insight of the AdS/CFT correspondence is that some aspects of the geometry of a bulk state are encoded in the entanglement structure of its dual boundary state. As entanglement is not a linear quantum observable, this means that geometry in a quantum theory of gravity should likewise not be a linear observable. This allows for linear dependencies between states with distinct geometries. We explore linear dependencies between certain states with simple geometric duals: states made up of $n$ copies of a thermofield double state and the states obtained from this one by permuting the $n$ right hand sides. There are $n!$ such states, all dual to distinct geometries. We derive expressions for the maximum fidelity between one such state and a linear combination of the others, and see that this fidelity approaches 1 as the number $n$ of black holes increases. We also consider the possibility of obtaining a single thermofield double state as the partial trace of a superposition of states whose topology does not connect the two untraced sides. We derive lower bounds for the fidelity between the thermofield double state and such partial traces and comment on the conceptual implications of the existence of such states.

arXiv:2206.06352•Jun 13, 2022•1 citation

Holographic study of entanglement and complexity for mixed states

Ashis Saha, Sunandan Gangopadhyay

In this paper, we holographically quantify the entanglement and complexity for mixed states by following the prescription of purification. The bulk theory we consider in this work is a hyperscaling violating solution, characterized by two parameters, hyperscaling violating exponent $\ensuremath{\theta}$ and dynamical exponent $z$. This geometry is due to a nonrelativistic strongly coupled theory with hidden Fermi surfaces. We first compute the holographic analogy of entanglement of purification, denoted as the minimal area of the entanglement wedge cross section and observe the effects of $z$ and $\ensuremath{\theta}$. Then in order to probe the mixed state complexity we compute the mutual complexity for the Banados Teitelboim Zanelli (BTZ) black hole and the hyperscaling violating geometry by incorporating the holographic subregion complexity conjecture. We carry this out for two disjoint subsystems separated by a distance and also when the subsystems are adjacent with subsystems making up the full system. Furthermore, various aspects of holographic entanglement entropy such as the entanglement Smarr relation, the Fisher information metric, and the butterfly velocity have also been discussed.

arXiv:2101.00887•Physical review. D/Physical review. D.•Apr 6, 2021•20 citations

A quantum circuit interpretation of evaporating black hole geometry

Ying Zhao

Abstract We give a quantum circuit interpretation of evaporating black hole geometry. We make an analogy between the appearance of island for evaporating black hole and the transition from two-sided to one-sided black hole in the familiar example of perturbed thermofield double. If Alice perturbs thermofield double and waits for scrambling time, she will have a one-sided black hole with interior of her own. We argue that by similar mechanism the radiation gets access to the interior (island forms) after Page time. The growth of the island happens as a result of the constant transitions from two-sided to one-sided black holes.

arXiv:1912.00909•Journal of High Energy Physics•Jul 1, 2020•21 citations
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.
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.
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.
A standard insight of the AdS/CFT correspondence is that some aspects of the geometry of a bulk state are encoded in the entanglement structure of its dual boundary state. As entanglement is not a linear quantum observable, this means that geometry in a quantum theory of gravity should likewise not be a linear observable. This allows for linear dependencies between states with distinct geometries. We explore linear dependencies between certain states with simple geometric duals: states made up of nnn copies of a thermofield double state and the states obtained from this one by permuting the nnn right hand sides. There are n!n!n! such states, all dual to distinct geometries. We derive expressions for the maximum fidelity between one such state and a linear combination of the others, and see that this fidelity approaches 1 as the number nnn of black holes increases. We also consider the possibility of obtaining a single thermofield double state as the partial trace of a superposition of states whose topology does not connect the two untraced sides. We derive lower bounds for the fidelity between the thermofield double state and such partial traces and comment on the conceptual implications of the existence of such states.
In this paper, we holographically quantify the entanglement and complexity for mixed states by following the prescription of purification. The bulk theory we consider in this work is a hyperscaling violating solution, characterized by two parameters, hyperscaling violating exponent $\ensuremath{\theta}$ and dynamical exponent zzz. This geometry is due to a nonrelativistic strongly coupled theory with hidden Fermi surfaces. We first compute the holographic analogy of entanglement of purification, denoted as the minimal area of the entanglement wedge cross section and observe the effects of zzz and $\ensuremath{\theta}$. Then in order to probe the mixed state complexity we compute the mutual complexity for the Banados Teitelboim Zanelli (BTZ) black hole and the hyperscaling violating geometry by incorporating the holographic subregion complexity conjecture. We carry this out for two disjoint subsystems separated by a distance and also when the subsystems are adjacent with subsystems making up the full system. Furthermore, various aspects of holographic entanglement entropy such as the entanglement Smarr relation, the Fisher information metric, and the butterfly velocity have also been discussed.
Abstract We give a quantum circuit interpretation of evaporating black hole geometry. We make an analogy between the appearance of island for evaporating black hole and the transition from two-sided to one-sided black hole in the familiar example of perturbed thermofield double. If Alice perturbs thermofield double and waits for scrambling time, she will have a one-sided black hole with interior of her own. We argue that by similar mechanism the radiation gets access to the interior (island forms) after Page time. The growth of the island happens as a result of the constant transitions from two-sided to one-sided black holes.