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:2110.11371 · Physical Review A

Resource theory of quantum uncomplexity

Nicole Yunger Halpern, Naga Bhavya Teja Kothakonda, Jonas Haferkamp, Anthony Munson, Jens Eisert, Philippe Faist

Published Dec 15, 2022• 35 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.106.062417

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

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

Entanglement theory with limited computational resources

Lorenzo Leone, J. Douglas Rizzo, Jens Eisert +1 more

Abstract The precise quantification of the limits to manipulating quantum resources lies at the core of quantum information theory. However, standard information-theoretic analyses do not consider the actual computational complexity involved in performing certain tasks. Here we address this issue within the realm of entanglement theory, finding that accounting for computational efficiency substantially changes what can be achieved using entangled resources. We consider two key figures of merit: the computational distillable entanglement and the computational entanglement cost. These measures quantify the optimal rates of entangled bits that can be extracted from or used to dilute many identical copies of n -qubit bipartite pure states, using computationally efficient local operations and classical communication. We demonstrate that computational entanglement measures diverge considerably from their information-theoretic counterparts. Whereas the information-theoretic distillable entanglement is determined by the von Neumann entropy of the reduced state, we show that the min-entropy governs the computationally efficient setting. On the other hand, computationally efficient entanglement dilution requires maximal consumption of entangled bits, even for nearly unentangled states. Furthermore, in the worst-case scenario, even when an efficient description of the state exists and is fully known, one gains no advantage over state-agnostic protocols. Our findings establish sample-complexity bounds for measuring and testing the von Neumann entropy, fundamental limitations on efficient state compression and efficient local tomography protocols.

arXiv:2502.12284•Nature Physics•Oct 22, 2025•17 citations

Resource theories of knowledge

Lídia del Rio, Lea Krämer, Renato Renner

How far can we take the resource theoretic approach to explore physics? Resource theories like LOCC, reference frames and quantum thermodynamics have proven a powerful tool to study how agents who are subject to certain constraints can act on physical systems. This approach has advanced our understanding of fundamental physical principles, such as the second law of thermodynamics, and provided operational measures to quantify resources such as entanglement or information content. In this work, we significantly extend the approach and range of applicability of resource theories. Firstly we generalize the notion of resource theories to include any description or knowledge that agents may have of a physical state, beyond the density operator formalism. We show how to relate theories that differ in the language used to describe resources, like micro and macroscopic thermodynamics. Finally, we take a top-down approach to locality, in which a subsystem structure is derived from a global theory rather than assumed. The extended framework introduced here enables us to formalize new tasks in the language of resource theories, ranging from tomography, cryptography, thermodynamics and foundational questions, both within and beyond quantum theory.

arXiv:1511.08818•Jan 1, 2015•86 citations

Resource-Dependent Complexity of Quantum Channels

Roy Araiza, Yidong Chen, Marius Junge +1 more

We introduce a new framework for quantifying the complexity of quantum channels, grounded in a suitably chosen resource set. This class of convex functions is designed to analyze the complexity of both open and closed quantum systems. By leveraging Lipschitz norms inspired by quantum optimal transport theory, we rigorously establish the fundamental properties of this complexity measure. The flexibility in selecting the resource set allows us to derive effective lower bounds for gate complexities and simulation costs of both Hamiltonian simulations and dynamics of open quantum systems. Additionally, we demonstrate that this complexity measure exhibits linear growth for random quantum circuits and finite-dimensional quantum simulations, up to the Brown-Susskind threshold.

arXiv:2303.11304•Quantum•Jan 8, 2026•11 citations

Resource theories of quantum channels and the universal role of resource erasure

Zi-Wen Liu, Andreas Winter

We initiate the systematic study of resource theories of quantum channels, i.e. of the dynamics that quantum systems undergo by completely positive maps, in abstracto: Resources are in principle all maps from one quantum system to another, but some maps are deemed free. The free maps are supposed to satisfy certain axioms, among them closure under tensor products, under composition and freeness of the identity map (the latter two say that the free maps form a monoid). The free maps act on the resources simply by tensor product and composition. This generalizes the much-studied resource theories of quantum states, and abolishes the distinction between resources (states) and the free maps, which act on the former, leaving only maps, divided into resource-full and resource-free ones. We discuss the axiomatic framework of quantifying channel resources, and show two general methods of constructing resource monotones of channels. Furthermore, we show that under mild regularity conditions, each resource theory of quantum channels has a distinguished monotone, the robustness (and its smoothed version), generalizing the analogous concept in resource theories of states. We give an operational interpretation of the log-robustness as the amount of heat dissipation (randomness) required for resource erasure by random reversible free maps, valid in broad classes of resource theories of quantum channels. Technically, this is based on an abstract version of the recent convex-split lemma, extended from its original domain of quantum states to ordered vector spaces with sufficiently well-behaved base norms (which includes the case of quantum channels with diamond norm or variants thereof). Finally, we remark on several key issues concerning the asymptotic theory.

arXiv:1904.04201•Apr 8, 2019•136 citations
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.
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 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 .
Abstract The precise quantification of the limits to manipulating quantum resources lies at the core of quantum information theory. However, standard information-theoretic analyses do not consider the actual computational complexity involved in performing certain tasks. Here we address this issue within the realm of entanglement theory, finding that accounting for computational efficiency substantially changes what can be achieved using entangled resources. We consider two key figures of merit: the computational distillable entanglement and the computational entanglement cost. These measures quantify the optimal rates of entangled bits that can be extracted from or used to dilute many identical copies of n -qubit bipartite pure states, using computationally efficient local operations and classical communication. We demonstrate that computational entanglement measures diverge considerably from their information-theoretic counterparts. Whereas the information-theoretic distillable entanglement is determined by the von Neumann entropy of the reduced state, we show that the min-entropy governs the computationally efficient setting. On the other hand, computationally efficient entanglement dilution requires maximal consumption of entangled bits, even for nearly unentangled states. Furthermore, in the worst-case scenario, even when an efficient description of the state exists and is fully known, one gains no advantage over state-agnostic protocols. Our findings establish sample-complexity bounds for measuring and testing the von Neumann entropy, fundamental limitations on efficient state compression and efficient local tomography protocols.
How far can we take the resource theoretic approach to explore physics? Resource theories like LOCC, reference frames and quantum thermodynamics have proven a powerful tool to study how agents who are subject to certain constraints can act on physical systems. This approach has advanced our understanding of fundamental physical principles, such as the second law of thermodynamics, and provided operational measures to quantify resources such as entanglement or information content. In this work, we significantly extend the approach and range of applicability of resource theories. Firstly we generalize the notion of resource theories to include any description or knowledge that agents may have of a physical state, beyond the density operator formalism. We show how to relate theories that differ in the language used to describe resources, like micro and macroscopic thermodynamics. Finally, we take a top-down approach to locality, in which a subsystem structure is derived from a global theory rather than assumed. The extended framework introduced here enables us to formalize new tasks in the language of resource theories, ranging from tomography, cryptography, thermodynamics and foundational questions, both within and beyond quantum theory.
We introduce a new framework for quantifying the complexity of quantum channels, grounded in a suitably chosen resource set. This class of convex functions is designed to analyze the complexity of both open and closed quantum systems. By leveraging Lipschitz norms inspired by quantum optimal transport theory, we rigorously establish the fundamental properties of this complexity measure. The flexibility in selecting the resource set allows us to derive effective lower bounds for gate complexities and simulation costs of both Hamiltonian simulations and dynamics of open quantum systems. Additionally, we demonstrate that this complexity measure exhibits linear growth for random quantum circuits and finite-dimensional quantum simulations, up to the Brown-Susskind threshold.
We initiate the systematic study of resource theories of quantum channels, i.e. of the dynamics that quantum systems undergo by completely positive maps, in abstracto: Resources are in principle all maps from one quantum system to another, but some maps are deemed free. The free maps are supposed to satisfy certain axioms, among them closure under tensor products, under composition and freeness of the identity map (the latter two say that the free maps form a monoid). The free maps act on the resources simply by tensor product and composition. This generalizes the much-studied resource theories of quantum states, and abolishes the distinction between resources (states) and the free maps, which act on the former, leaving only maps, divided into resource-full and resource-free ones. We discuss the axiomatic framework of quantifying channel resources, and show two general methods of constructing resource monotones of channels. Furthermore, we show that under mild regularity conditions, each resource theory of quantum channels has a distinguished monotone, the robustness (and its smoothed version), generalizing the analogous concept in resource theories of states. We give an operational interpretation of the log-robustness as the amount of heat dissipation (randomness) required for resource erasure by random reversible free maps, valid in broad classes of resource theories of quantum channels. Technically, this is based on an abstract version of the recent convex-split lemma, extended from its original domain of quantum states to ordered vector spaces with sufficiently well-behaved base norms (which includes the case of quantum channels with diamond norm or variants thereof). Finally, we remark on several key issues concerning the asymptotic theory.