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

Attainable Boundaries versus Operational Equivalence: Dual Benchmarks for the Hierarchical Assessment of Quantum Resources

Sunho Kim, Chunhe Xiong, Junde Wu

quant-phSubmitted Oct 8, 2026• Announced Oct 9, 2026• 0 citations• Revised Oct 27, 2026 (v2)
v1 · Oct 8, 2026v2 · Oct 27, 2026
arXivHTMLPDF

Abstract

Conventional resource theories quantify utility against an idealized free set $\mathcal{F}$. In practice, however, realizable states are confined to a specific supply environment $\mathcal{E}$ shaped by experimental and noise constraints. We propose a framework that evaluates the relative utility of arbitrary states with respect to $\mathcal{E}$, using two reference representations: the set of states reachable by free operations (defining the attainable boundary) and the set obtained via numerical optimization (defining operational equivalence). Two complementary methodologies are established. First, by assessing each state under its individually optimized strategy, we provide a strategy-dependent benchmark that quantifies achievable performance. Second, by deriving the optimal strategy for each state separately, we obtain a computable lower bound, yielding a strategy-independent measure of relative superiority that is independent of specific setups. To realize these methodologies numerically, we introduce relative measures based on the generalized robustness and the relative entropy. We then establish, theoretically, a quantitative hierarchical relation between the strategy-dependent benchmark and the strategy-independent lower bound. In a thermodynamic setting, the minimum work cost for synthesizing a target state is lower-bounded by the free-energy difference, which reflects only absolute utility. Applying our framework, we identify this bound as a strategy-independent quantification. Through two scenarios based respectively on information-theoretic distance and thermodynamic distance, we derive upper bounds on the minimum work cost for recovering entanglement in a noisy environment. We show that, at moderate and low temperatures in the low-noise regime, the thermodynamic-distance-based upper bound is tighter than the information-theoretic one.

AI Summary

The paper asks how to benchmark a quantum state against a constrained supply set $\mathcal E$, rather than only against free states. It constructs a free-operation reachable set $\mathcal R^{FO}(\mathcal E)$ and larger sublevel sets containing states whose chosen resource monotone does not exceed its maximum over $\mathcal E$. Generalized robustness and relative-entropy distance to these sets define measures of relative superiority. Set inclusion yields a hierarchy between conventional, reachable-set, and sublevel-set measures. The paper derives the robustness identity $R^{\max}_{\mathcal E}(\rho)=\max\{[R(\rho)-R(\mathcal E)]/[1+R(\mathcal E)],0\}$ by composing robustness decompositions. It also claims the analogous relative-entropy identity $D^{\max}_{\mathcal E}(\rho)=\max\{D(\rho)-D(\mathcal E),0\}$. Its proof, however, invokes a triangle inequality and affine-path additivity that relative entropy does not generally satisfy. The thermodynamic application introduces thermally anchored robustness: the least Gibbs-state admixture making a target reachable. Pinsker’s inequality and entropy-continuity bounds give two upper bounds on a quantity defined as the minimum free-energy gap. A noisy two-qubit Bell-state example reports a smaller anchored-robustness bound at moderate and low temperatures with low noise. These bounds concern the free-energy-gap quantity, not an operationally demonstrated synthesis cost; the paper acknowledges that actual single-shot work can exceed that gap. The example additionally assumes nondecreasing system entropy under thermal operations, which is not generally required. Stated limitations include difficult high-dimensional reference-set characterization, potentially loose bounds, and restricted distance/noise ranges for their validity.

Almost certainly largely AI-generatedAI use disclosedOverclaimsUnclear noveltyMissing comparisonPossible error
During manuscript preparation, the authors used AI tools (including DeepSeek) to assist with language editing, proofreading, and restructuring of numerical and mathematical derivations.

Central claim may not hold: Theorem 2's relative-entropy identity and consequent lower bound are contradicted by a two-dimensional example with free state I/2, supplied state diag(0.8,0.2), and target |0><0|. The work-bound proofs upper-bound a free-energy-gap surrogate rather than actual single-shot synthesis work, so they do not establish the advertised operational work-cost upper bounds. The Bell example computes thermal reachability using non-decreasing system entropy, although allowed thermal operations can decrease system entropy. The Bell example labels energy-basis populations as eigenvalues and applies population thermo-majorization without the additional constraints needed for states coherent across distinct energies. The entropy function used to invert the Bell example's TAR has derivative -x tanh(x/2) at R=1, contradicting its asserted global increase for every positive inverse temperature.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
18 pages, 2 figures

Related papers

Quantification of Quantum Resources

Gilad Gour

Chapter 10 delves into the quantification of quantum resources, an essential aspect of quantum resource theories that determines the value of quantum states for specific applications. It begins by defining resource measures and investigating their fundamental properties such as monotonicity under free operations and convexity. The chapter discusses distance-based resource measures, which quantify how far a given quantum state is from the set of free states. Such measures often utilize divergences and metrics explored in earlier chapters. Techniques to compute the relative entropy of a resource are also covered. To refine resource measures, the chapter introduces the concept of smoothing, which considers small deviations from the ideal state to make the measures more robust against perturbations. This approach is crucial in single-shot scenarios where finite resources are available. Furthermore, the chapter examines resource monotones and support functions, offering a comprehensive framework for the theoretical and practical assessment of quantum resources.

Cambridge University Press eBooks•Apr 10, 2025•0 citations

Distance-based resource quantification for sets of quantum measurements

Lucas Tendick, Martin Kliesch, Hermann Kampermann +1 more

The advantage that quantum systems provide for certain quantum information processing tasks over their classical counterparts can be quantified within the general framework of resource theories. Certain distance functions between quantum states have successfully been used to quantify resources like entanglement and coherence. Perhaps surprisingly, such a distance-based approach has not been adopted to study resources of quantum measurements, where other geometric quantifiers are used instead. Here, we define distance functions between sets of quantum measurements and show that they naturally induce resource monotones for convex resource theories of measurements. By focusing on a distance based on the diamond norm, we establish a hierarchy of measurement resources and derive analytical bounds on the incompatibility of any set of measurements. We show that these bounds are tight for certain projective measurements based on mutually unbiased bases and identify scenarios where different measurement resources attain the same value when quantified by our resource monotone. Our results provide a general framework to compare distance-based resources for sets of measurements and allow us to obtain limitations on Bell-type experiments.

arXiv:2205.08546•Quantum•May 15, 2023•14 citations

Quantification of the Resource Theory of Imaginarity Revisited

Yue Han, Naihong Hu

This work studies the decay of three imaginarity measures, namely the $l_1$-norm-based imaginarity, the robustness of imaginarity, and the relative-entropy-based imaginarity, under typical noise channels. For arbitrary single-qubit pure states subject to real quantum channels, we prove an exact attenuation theorem: the $l_1$-norm-based imaginarity and the robustness exhibit identical attenuation governed by a common channel-dependent factor, whereas the relative-entropy-based imaginarity additionally depends on the input-state orientation relative to the reference basis. We extend the investigation to two-qubit entangled and dual-rail states, establishing a quantitative link between photon-loss probability and residual imaginarity for photonic dual-rail encodings. For separable two-qubit states, we define a real-operation resource preorder and show that $Ω_{++}=|+\rangle\langle+|\otimes|+\rangle\langle+|$ is operationally maximal. We further distinguish operational de-imaginary power from reference-state imaginarity loss. For several real two-qubit channels we derive exact operational de-imaginary powers, while for other channels we provide analytic reference-state losses serving as benchmarks and rigorous lower bounds.

quant-pharXiv:2603.13980•Journal of Physics A Mathematical and Theoretical•Mar 17, 2026•0 citations

Resource-Induced Non-Representability of Exact Quantum Limits

Claudio Menéndez

This work studies the operational limitations on the physical realization of exact mathematical limits in quantum theory. Focusing on the zero-temperature limit, we analyze the extent to which ground-state preparation can be achieved using quantum operations constrained by finite physical resources. We introduce a general class of physically realizable quantum channels characterized by bounded interaction strength, finite implementation time, and finite control resolution. Within this resource-theoretic setting, we derive bounds on spectral localization using quantum speed limits and variance propagation arguments. These bounds imply that arbitrarily sharp spectral concentration cannot be achieved by finite-resource operations in finite time. As a consequence, the preparation of states arbitrarily close to the exact ground state is subject to resource-dependent limitations. In particular, the achievable trace distance to the ground state is bounded from below by a quantity determined by the available energy, control precision, and operational time. The result is independent of specific coarse-graining models or measurement schemes. Instead, the limitation follows from general dynamical and informational constraints associated with finite resources in quantum operations. This perspective provides a resource-theoretic interpretation of the third law of thermodynamics. Within this framework, the unattainability of absolute zero can be understood not only as a dynamical constraint but also as a consequence of operational bounds on spectral localization. These considerations also imply practical limits for ground-state preparation, quantum annealing protocols, and low-temperature quantum metrology, where finite resources impose irreducible accuracy floors. The analysis is interpreted within the broader program of Finite-Closure Geometry (FCG), which distinguishes between mathematical closure operations (such as exact limits) and the physically realizable projections produced by finite-resource dynamics. In this view, exact limits function as ideal mathematical constructs that guide theoretical descriptions but cannot be implemented exactly by finite physical processes. Related work This work complements and extends the results of Operational Non-Representability of the Zero-Temperature Limit under Finite Energy Resolution (Menéndez, 2025). The earlier paper demonstrates non-representability through explicit finite-resolution coarse-graining channels. The present work instead analyzes the problem from a more general resource-theoretic perspective, where the obstruction arises from dynamical bounds on quantum operations implemented with finite resources. In this sense, finite-resolution models appear as particular realizations within a broader class of resource-constrained dynamics. Together, the two works provide both an explicit operational example and a general dynamical perspective on the limitations associated with exact quantum limits. Conceptual index of the Finite-Closure Geometry (FCG) research program Finite-Closure Geometry (FCG): A Structural Program for Global Non-ClosureDOI: 10.5281/zenodo.18001440 Keywords quantum channels, finite resources, zero-temperature limit, third law of thermodynamics, quantum speed limits, spectral localization, ground-state preparation, quantum thermodynamics, operational limits, trace distance, resource theory, finite-closure geometry, quantum foundations, mathematical limits

•Dec 30, 2025•0 citations

Distillation and simulation in quantum information

Kun Fang

We use the techniques of convex optimization, especially semidefinite programming, to study two kinds of fundamental tasks, i.e., distillation and simulation in quantum information theory. We investigate these tasks in a unified framework of resource theory and focus on their computation and characterization with finite resources. Particularly we study the tradeoff among relevant parameters such as the number of resource copies, resource transformation rate, error tolerance and success probability. In the first part, we study the task of distillation for two different resources, maximally entangled state and maximally coherent state, representing nonlocal and local “quantumness” respectively. For entanglement distillation, we derive an efficiently computable second-order estimation of the distillation rate for general quantum states, which are tight for quantum states of practical interest. Our study overcomes the limitation of conventional research either focusing on the asymptotic rate or ignoring the computability. For the coherence distillation, we perform finite analysis for both deterministic and probabilistic scenarios. Our results unveil several new features of coherence from a resource theoretic viewpoint and contribute to an increased understanding of the fundamental properties of different sets of free operations. In the second part, we investigate the resource cost of simulating a quantum channel via quantum coherence or another quantum channel. We introduce the channel’s analogs of max-relative entropy, logarithmic robustness and max-information of quantum states, providing their operational interpretation with the channel simulation cost via different resources. Particularly, we establish the asymptotic equipartition property of the channel’s max-information, that is, it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. As applications, this asymptotic equipartition property implies the quantum reverse Shannon theorem in the presence of non-signalling correlations. From the perspective of resource theory, the worth of a resource can usually be characterized by the minimum distance to a set of useless resources under a proper distance measure. We give such characterization for all the tasks studied in this thesis, and find that the distance measure for the distillation and simulation process naturally corresponds to the quantum hypothesis testing relative entropy and the max-relative entropy, respectively.

•Jan 1, 2018•1 citation

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
Conventional resource theories quantify utility against an idealized free set F\mathcal{F}F. In practice, however, realizable states are confined to a specific supply environment E\mathcal{E}E shaped by experimental and noise constraints. We propose a framework that evaluates the relative utility of arbitrary states with respect to E\mathcal{E}E, using two reference representations: the set of states reachable by free operations (defining the attainable boundary) and the set obtained via numerical optimization (defining operational equivalence).
Two complementary methodologies are established. First, by assessing each state under its individually optimized strategy, we provide a strategy-dependent benchmark that quantifies achievable performance. Second, by deriving the optimal strategy for each state separately, we obtain a computable lower bound, yielding a strategy-independent measure of relative superiority that is independent of specific setups.
To realize these methodologies numerically, we introduce relative measures based on the generalized robustness and the relative entropy. We then establish, theoretically, a quantitative hierarchical relation between the strategy-dependent benchmark and the strategy-independent lower bound.
In a thermodynamic setting, the minimum work cost for synthesizing a target state is lower-bounded by the free-energy difference, which reflects only absolute utility. Applying our framework, we identify this bound as a strategy-independent quantification. Through two scenarios based respectively on information-theoretic distance and thermodynamic distance, we derive upper bounds on the minimum work cost for recovering entanglement in a noisy environment. We show that, at moderate and low temperatures in the low-noise regime, the thermodynamic-distance-based upper bound is tighter than the information-theoretic one.
The paper asks how to benchmark a quantum state against a constrained supply set E\mathcal EE, rather than only against free states. It constructs a free-operation reachable set RFO(E)\mathcal R^{FO}(\mathcal E)RFO(E) and larger sublevel sets containing states whose chosen resource monotone does not exceed its maximum over E\mathcal EE. Generalized robustness and relative-entropy distance to these sets define measures of relative superiority.
Set inclusion yields a hierarchy between conventional, reachable-set, and sublevel-set measures. The paper derives the robustness identity REmax⁡(ρ)=max⁡{[R(ρ)−R(E)]/[1+R(E)],0}R^{\max}_{\mathcal E}(\rho)=\max\{[R(\rho)-R(\mathcal E)]/[1+R(\mathcal E)],0\}REmax​(ρ)=max{[R(ρ)−R(E)]/[1+R(E)],0} by composing robustness decompositions. It also claims the analogous relative-entropy identity DEmax⁡(ρ)=max⁡{D(ρ)−D(E),0}D^{\max}_{\mathcal E}(\rho)=\max\{D(\rho)-D(\mathcal E),0\}DEmax​(ρ)=max{D(ρ)−D(E),0}. Its proof, however, invokes a triangle inequality and affine-path additivity that relative entropy does not generally satisfy.
The thermodynamic application introduces thermally anchored robustness: the least Gibbs-state admixture making a target reachable. Pinsker’s inequality and entropy-continuity bounds give two upper bounds on a quantity defined as the minimum free-energy gap. A noisy two-qubit Bell-state example reports a smaller anchored-robustness bound at moderate and low temperatures with low noise. These bounds concern the free-energy-gap quantity, not an operationally demonstrated synthesis cost; the paper acknowledges that actual single-shot work can exceed that gap. The example additionally assumes nondecreasing system entropy under thermal operations, which is not generally required.
Stated limitations include difficult high-dimensional reference-set characterization, potentially loose bounds, and restricted distance/noise ranges for their validity.
Chapter 10 delves into the quantification of quantum resources, an essential aspect of quantum resource theories that determines the value of quantum states for specific applications. It begins by defining resource measures and investigating their fundamental properties such as monotonicity under free operations and convexity. The chapter discusses distance-based resource measures, which quantify how far a given quantum state is from the set of free states. Such measures often utilize divergences and metrics explored in earlier chapters. Techniques to compute the relative entropy of a resource are also covered. To refine resource measures, the chapter introduces the concept of smoothing, which considers small deviations from the ideal state to make the measures more robust against perturbations. This approach is crucial in single-shot scenarios where finite resources are available. Furthermore, the chapter examines resource monotones and support functions, offering a comprehensive framework for the theoretical and practical assessment of quantum resources.
The advantage that quantum systems provide for certain quantum information processing tasks over their classical counterparts can be quantified within the general framework of resource theories. Certain distance functions between quantum states have successfully been used to quantify resources like entanglement and coherence. Perhaps surprisingly, such a distance-based approach has not been adopted to study resources of quantum measurements, where other geometric quantifiers are used instead. Here, we define distance functions between sets of quantum measurements and show that they naturally induce resource monotones for convex resource theories of measurements. By focusing on a distance based on the diamond norm, we establish a hierarchy of measurement resources and derive analytical bounds on the incompatibility of any set of measurements. We show that these bounds are tight for certain projective measurements based on mutually unbiased bases and identify scenarios where different measurement resources attain the same value when quantified by our resource monotone. Our results provide a general framework to compare distance-based resources for sets of measurements and allow us to obtain limitations on Bell-type experiments.
This work studies the decay of three imaginarity measures, namely the l1l_1l1​-norm-based imaginarity, the robustness of imaginarity, and the relative-entropy-based imaginarity, under typical noise channels. For arbitrary single-qubit pure states subject to real quantum channels, we prove an exact attenuation theorem: the l1l_1l1​-norm-based imaginarity and the robustness exhibit identical attenuation governed by a common channel-dependent factor, whereas the relative-entropy-based imaginarity additionally depends on the input-state orientation relative to the reference basis. We extend the investigation to two-qubit entangled and dual-rail states, establishing a quantitative link between photon-loss probability and residual imaginarity for photonic dual-rail encodings. For separable two-qubit states, we define a real-operation resource preorder and show that Ω++=∣+⟩⟨+∣⊗∣+⟩⟨+∣Ω_{++}=|+\rangle\langle+|\otimes|+\rangle\langle+|Ω++​=∣+⟩⟨+∣⊗∣+⟩⟨+∣ is operationally maximal. We further distinguish operational de-imaginary power from reference-state imaginarity loss. For several real two-qubit channels we derive exact operational de-imaginary powers, while for other channels we provide analytic reference-state losses serving as benchmarks and rigorous lower bounds.
This work studies the operational limitations on the physical realization of exact mathematical limits in quantum theory. Focusing on the zero-temperature limit, we analyze the extent to which ground-state preparation can be achieved using quantum operations constrained by finite physical resources. We introduce a general class of physically realizable quantum channels characterized by bounded interaction strength, finite implementation time, and finite control resolution. Within this resource-theoretic setting, we derive bounds on spectral localization using quantum speed limits and variance propagation arguments. These bounds imply that arbitrarily sharp spectral concentration cannot be achieved by finite-resource operations in finite time. As a consequence, the preparation of states arbitrarily close to the exact ground state is subject to resource-dependent limitations. In particular, the achievable trace distance to the ground state is bounded from below by a quantity determined by the available energy, control precision, and operational time. The result is independent of specific coarse-graining models or measurement schemes. Instead, the limitation follows from general dynamical and informational constraints associated with finite resources in quantum operations. This perspective provides a resource-theoretic interpretation of the third law of thermodynamics. Within this framework, the unattainability of absolute zero can be understood not only as a dynamical constraint but also as a consequence of operational bounds on spectral localization. These considerations also imply practical limits for ground-state preparation, quantum annealing protocols, and low-temperature quantum metrology, where finite resources impose irreducible accuracy floors. The analysis is interpreted within the broader program of Finite-Closure Geometry (FCG), which distinguishes between mathematical closure operations (such as exact limits) and the physically realizable projections produced by finite-resource dynamics. In this view, exact limits function as ideal mathematical constructs that guide theoretical descriptions but cannot be implemented exactly by finite physical processes. Related work This work complements and extends the results of Operational Non-Representability of the Zero-Temperature Limit under Finite Energy Resolution (Menéndez, 2025). The earlier paper demonstrates non-representability through explicit finite-resolution coarse-graining channels. The present work instead analyzes the problem from a more general resource-theoretic perspective, where the obstruction arises from dynamical bounds on quantum operations implemented with finite resources. In this sense, finite-resolution models appear as particular realizations within a broader class of resource-constrained dynamics. Together, the two works provide both an explicit operational example and a general dynamical perspective on the limitations associated with exact quantum limits. Conceptual index of the Finite-Closure Geometry (FCG) research program Finite-Closure Geometry (FCG): A Structural Program for Global Non-ClosureDOI: 10.5281/zenodo.18001440 Keywords quantum channels, finite resources, zero-temperature limit, third law of thermodynamics, quantum speed limits, spectral localization, ground-state preparation, quantum thermodynamics, operational limits, trace distance, resource theory, finite-closure geometry, quantum foundations, mathematical limits
We use the techniques of convex optimization, especially semidefinite programming, to study two kinds of fundamental tasks, i.e., distillation and simulation in quantum information theory. We investigate these tasks in a unified framework of resource theory and focus on their computation and characterization with finite resources. Particularly we study the tradeoff among relevant parameters such as the number of resource copies, resource transformation rate, error tolerance and success probability. In the first part, we study the task of distillation for two different resources, maximally entangled state and maximally coherent state, representing nonlocal and local “quantumness” respectively. For entanglement distillation, we derive an efficiently computable second-order estimation of the distillation rate for general quantum states, which are tight for quantum states of practical interest. Our study overcomes the limitation of conventional research either focusing on the asymptotic rate or ignoring the computability. For the coherence distillation, we perform finite analysis for both deterministic and probabilistic scenarios. Our results unveil several new features of coherence from a resource theoretic viewpoint and contribute to an increased understanding of the fundamental properties of different sets of free operations. In the second part, we investigate the resource cost of simulating a quantum channel via quantum coherence or another quantum channel. We introduce the channel’s analogs of max-relative entropy, logarithmic robustness and max-information of quantum states, providing their operational interpretation with the channel simulation cost via different resources. Particularly, we establish the asymptotic equipartition property of the channel’s max-information, that is, it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. As applications, this asymptotic equipartition property implies the quantum reverse Shannon theorem in the presence of non-signalling correlations. From the perspective of resource theory, the worth of a resource can usually be characterized by the minimum distance to a set of useless resources under a proper distance measure. We give such characterization for all the tasks studied in this thesis, and find that the distance measure for the distillation and simulation process naturally corresponds to the quantum hypothesis testing relative entropy and the max-relative entropy, respectively.
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 .