Complexity-constrained quantum thermodynamics

Abstract

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, via a complexity-constrained process, is quantified by the state's complexity entropy. 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 complexity relative entropy. 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 and determine the complexity entropy's behavior under random circuits. 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 complexity conditional entropy, 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 time, as quantified by complexity.

17 pages (6 figures) + appendices (41 pages)

References in corpus (86)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Characterizing Quantum Supremacy in Near-Term Devices
• Classification of Gapped Symmetric Phases in 1D Spin Systems
• The role of quantum information in thermodynamics --- a topical review
• Complexity Equals Action
• Fundamental limitations for quantum and nano thermodynamics
• Complexity and Shock Wave Geometries
• Description of quantum coherence in thermodynamic processes requires constraints beyond free energy
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• The second laws of quantum thermodynamics
• Entropic Uncertainty Relations and their Applications
• Complexity, action, and black holes
• The Resource Theory of Quantum States Out of Thermal Equilibrium
• Quantum Computation as Geometry
• Min- and Max- Relative Entropies and a New Entanglement Monotone
• Unitary-projective entanglement dynamics
• Exact relaxation in a class of non-equilibrium quantum lattice systems
• Chaos and complexity by design
• The thermodynamic meaning of negative entropy
• Work extraction and thermodynamics for individual quantum systems
• Quantum Information Processing with Finite Resources -- Mathematical Foundations
• Local random quantum circuits are approximate polynomial-designs
• Leftover Hashing Against Quantum Side Information
• One-Shot Classical-Quantum Capacity and Hypothesis Testing
• The Second Law of Quantum Complexity
• Most quantum states are too entangled to be useful as computational resources
• A Hierarchy of Information Quantities for Finite Block Length Analysis of Quantum Tasks
• Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints
• The mother of all protocols: Restructuring quantum information's family tree
• Truly work-like work extraction
• Complexity and entanglement for thermofield double states
• Experimental Realization of a Measurement-Induced Entanglement Phase Transition on a Superconducting Quantum Processor
• A decoupling approach to the quantum capacity
• Linear growth of quantum circuit complexity
• Topological Order at Non-zero Temperature
• The work value of information
• The Minimal Work Cost of Information Processing
• Computational advantage of quantum random sampling
• Optimal control, geometry, and quantum computing
• One-shot decoupling
• Does Complexity Equal Anything?
• Are random pure states useful for quantum computation?
• Models of quantum complexity growth
• Gibbs-Preserving Maps outperform Thermal Operations in the quantum regime
• Optimal quantum source coding with quantum information at the encoder and decoder
• On entropy growth and the hardness of simulating time evolution
• Chain Rules for Smooth Min- and Max-Entropies
• Nishimori's cat: stable long-range entanglement from finite-depth unitaries and weak measurements
• Landauer vs. Nernst: What is the True Cost of Cooling a Quantum System?
• Decoupling with random quantum circuits
• Quantum complexity and topological phases of matter
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Quasiclassical Coarse Graining and Thermodynamic Entropy
• Beyond heat baths: Generalized resource theories for small-scale thermodynamics
• Quantum coarse-grained entropy and thermodynamics
• A measure of majorisation emerging from single-shot statistical mechanics
• Mid-circuit measurements on a single species neutral alkali atom quantum processor
• Decoupling with unitary approximate two-designs
• The ghost in the radiation: Robust encodings of the black hole interior
• Complexity Growth in Integrable and Chaotic Models
• Quantum Relative Lorenz Curves
• Entangling power and quantum circuit complexity
• Circuit Complexity across a Topological Phase Transition
• Introducing one-shot work into fluctuation relations
• Post-Quench Evolution of Complexity and Entanglement in a Topological System
• A smooth entropy approach to quantum hypothesis testing and the classical capacity of quantum channels
• Fundamental work cost of quantum processes
• Beyond heat baths II: Framework for generalized thermodynamic resource theories
• Dynamical phase transitions in sampling complexity
• What is the probability of a thermodynamical transition?
• Reexamination of Pure Qubit Work Extraction
• Smoothed generalized free energies for thermodynamics
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Almost all quantum channels are equidistant
• Nonanalyticity of circuit complexity across topological phase transitions
• Latent Computational Complexity of Symmetry-Protected Topological Order with Fractional Symmetry
• Resource theory of quantum uncomplexity
• Surpassing the Carnot Efficiency by extracting imperfect work
• Preparing topological PEPS on a quantum computer
• Chain rules for quantum Rényi entropies
• Quantum work statistics and resource theories: bridging the gap through Renyi divergences
• Interactive Protocols for Classically-Verifiable Quantum Advantage
• Relations between Dissipated Work and Rényi Divergences
• Maximum one-shot dissipated work from Renyi divergences
• Quantum complexity phase transitions in monitored random circuits
• Toward the nonequilibrium thermodynamic analog of complexity and the Jarzynski identity

Cited by in corpus (6)

• Quantum complexity in gravity, quantum field theory, and quantum information science
• Non-Clifford Cost of Random Unitaries
• Artificially intelligent Maxwell's demon for optimal control of open quantum systems
• Minimizing Dissipation via Interacting Environments: Quadratic Convergence to Landauer Bound
• Adaptively secure unitary designs with constant non-Clifford cost
• Time-cost-error trade-off relation in thermodynamics: The third law and beyond