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

Second law of quantum complexity

Adam R. Brown, Leonard Susskind

Published Apr 25, 2018• 292 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevd.97.086015

Related papers

Resource theory of quantum uncomplexity

Nicole Yunger Halpern, Naga Bhavya Teja Kothakonda, Jonas Haferkamp +3 more

Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state's distance from maximal complexity, or ``uncomplexity,'' the more useful the state is as input to a quantum computation. Separately, resource theories---simple models for agents subject to constraints---are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.

arXiv:2110.11371•Physical Review A•Dec 15, 2022•23 citations

Quantum complexity and the virial theorem

Ning Bao, Junyu Liu

Abstract It is conjectured that in the geometric formulation of quantum computing, one can study quantum complexity through classical entropy of statistical ensembles established non-relativistically in the group manifold of unitary operators. The kinetic and positional decompositions of statistical entropy are conjectured to correspond to the Kolmogorov complexity and computational complexity, respectively, of corresponding quantum circuits. In this paper, we claim that by applying the virial theorem to the group manifold, one can derive a generic relation between Kolmogorov complexity and computational complexity in the thermal equilibrium.

arXiv:1804.03242•Journal of High Energy Physics•Aug 1, 2018•9 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•32 citations

`It from Bit': is there a second law of quantum complexity?

S. Davatolhagh, A. Sheykhi, M. H. Zarei

At a deeper level the principle of least action is interpreted as the law of least entropy increase consistent with Prigogine's principle of minimum entropy production, and the implications of quasistatic information quantization rule (Proc. R. Soc. A 480: 20240024), are explored for the conjectured second law of quantum complexity. It is thus shown that the conjectured second law of complexity is derivable from the information quantization rule such that long after heat-death the quantum state complexity evolves as $C(t)=C_{\rm max}\exp(-1/t)$, increasing with time to a saturation value $C_{\rm max}$ that is exponential in the equilibrium entropy $S_{\rm max}$. For the out-of-equilibrium circumstances, however, the quantum complexity can decrease with the time, asymptotically tending to a minimum determined by the distance from equilibrium.

quant-pharXiv:2608.22977•Aug 25, 2026•0 citations

Complexity-Constrained Quantum Thermodynamics

Anthony Munson, Naga Bhavya Teja Kothakonda, Jonas Haferkamp +3 more

Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process’s complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n -qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state in our model, via a complexity-constrained process, is quantified by the state’s . The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the . The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer’s ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy. In a random circuit—a simple model for quantum chaotic dynamics—the complexity entropy transitions from zero to its maximal value around the time corresponding to the observer’s computational-power limit. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a , which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of , as quantified by .

arXiv:2403.04828•PRX Quantum•Mar 10, 2025•9 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
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.
Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state's distance from maximal complexity, or ``uncomplexity,'' the more useful the state is as input to a quantum computation. Separately, resource theories---simple models for agents subject to constraints---are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind's conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.
Abstract It is conjectured that in the geometric formulation of quantum computing, one can study quantum complexity through classical entropy of statistical ensembles established non-relativistically in the group manifold of unitary operators. The kinetic and positional decompositions of statistical entropy are conjectured to correspond to the Kolmogorov complexity and computational complexity, respectively, of corresponding quantum circuits. In this paper, we claim that by applying the virial theorem to the group manifold, one can derive a generic relation between Kolmogorov complexity and computational complexity in the thermal equilibrium.
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} .
At a deeper level the principle of least action is interpreted as the law of least entropy increase consistent with Prigogine's principle of minimum entropy production, and the implications of quasistatic information quantization rule (Proc. R. Soc. A 480: 20240024), are explored for the conjectured second law of quantum complexity. It is thus shown that the conjectured second law of complexity is derivable from the information quantization rule such that long after heat-death the quantum state complexity evolves as C(t)=Cmaxexp⁡(−1/t)C(t)=C_{\rm max}\exp(-1/t)C(t)=Cmax​exp(−1/t), increasing with time to a saturation value CmaxC_{\rm max}Cmax​ that is exponential in the equilibrium entropy SmaxS_{\rm max}Smax​. For the out-of-equilibrium circumstances, however, the quantum complexity can decrease with the time, asymptotically tending to a minimum determined by the distance from equilibrium.
Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process’s complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n -qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state in our model, via a complexity-constrained process, is quantified by the state’s . The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the . The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer’s ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy. In a random circuit—a simple model for quantum chaotic dynamics—the complexity entropy transitions from zero to its maximal value around the time corresponding to the observer’s computational-power limit. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a , which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of , as quantified by .
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.