Resource theory of quantum uncomplexity
arXiv:2110.11371 · doi:10.1103/PhysRevA.106.062417
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.
arXiv commentPublished version
References in corpus (101)
- Quantum entanglement
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantifying Coherence
- Black holes as mirrors: quantum information in random subsystems
- Quantum Resource Theories
- Characterizing Quantum Supremacy in Near-Term Devices
- Classification of Gapped Symmetric Phases in 1D Spin Systems
- Operational Resource Theory of Coherence
- On the Power of One Bit of Quantum Information
- Complexity Equals Action
- Fundamental limitations for quantum and nano thermodynamics
- Complexity and Shock Wave Geometries
- Complexity, action, and black holes
- The Resource Theory of Quantum States Out of Thermal Equilibrium
- Quantum Computation as Geometry
- The Physics and Mathematics of the Second Law of Thermodynamics
- The Resource Theory of Stabilizer Computation
- From Classical to Quantum Shannon Theory
- Chaos and complexity by design
- Positive Wigner functions render classical simulation of quantum computation efficient
- Application of a resource theory for magic states to fault-tolerant quantum computing
- Negative Quasi-Probability as a Resource for Quantum Computation
- The resource theory of informational nonequilibrium in thermodynamics
- How to quantify coherence: Distinguishing speakable and unspeakable notions
- 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
- Chaos, Complexity, and Random Matrices
- Reversible transformations from pure to mixed states, and the unique measure of information
- General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks
- Information as a resource in distributed quantum systems
- Quantum Complexity and Negative Curvature
- Topological Order at Non-zero Temperature
- Linear growth of quantum circuit complexity
- Microcanonical and resource-theoretic derivations of the thermal state of a quantum system with noncommuting charges
- Many-body quantum magic
- Thermodynamics of quantum systems with multiple conserved quantities
- Optimal control, geometry, and quantum computing
- Comparison of Quantum Channels by Superchannels
- Operational Resource Theory of Quantum Channels
- Subsystem Complexity and Holography
- Scrambling in Random Unitary Circuits: Exact Results
- Optimal sequence of quantum measurements in the sense of Stein's lemma in quantum hypothesis testing
- Thermodynamic resource theories, non-commutativity and maximum entropy principles
- Gibbs-Preserving Maps outperform Thermal Operations in the quantum regime
- Models of quantum complexity growth
- Quantifying Operations with an Application to Coherence
- Quantum Complexity of Time Evolution with Chaotic Hamiltonians
- The Typical-State Paradox: Diagnosing Horizons with Complexity
- Complexity of Mixed States in QFT and Holography
- Structure of the resource theory of quantum coherence
- Conformal field theories are magical
- Towards resource theory of coherence in distributed scenarios
- Resource Theory of Coherence - Beyond States
- Resource theory of coherence based on positive-operator-valued measures
- How to quantify a dynamical quantum resource
- Quantum chaos in the Brownian SYK model with large finite : OTOCs and tripartite information
- Beyond heat baths: Generalized resource theories for small-scale thermodynamics
- Elementary Thermal Operations
- A Resource Theory for Work and Heat
- Experimental progress on quantum coherence: detection, quantification, and manipulation
- Complexity Growth in Integrable and Chaotic Models
- Dynamical Resource Theory of Quantum Coherence
- Heat-Bath Algorithmic Cooling with optimal thermalization strategies
- Quantifying Quantum Coherence in Experimentally-Observed Neutrino Oscillations
- Entangling power and quantum circuit complexity
- Circuit Complexity across a Topological Phase Transition
- Post-Quench Evolution of Complexity and Entanglement in a Topological System
- Generalized Entropies
- A smooth entropy approach to quantum hypothesis testing and the classical capacity of quantum channels
- Quantification and manipulation of magic states
- Beyond heat baths II: Framework for generalized thermodynamic resource theories
- Dynamical phase transitions in sampling complexity
- How difficult is it to prepare a quantum state?
- Entanglement and Complexity of Purification in (1+1)-dimensional free Conformal Field Theories
- Optimal work extraction from quantum states by photo-assisted Cooper pair tunneling
- Characterization of an operational quantum resource in a critical many-body system
- Fundamental limitations on photoisomerization from thermodynamic resource theories
- Coherent fluctuation relations: from the abstract to the concrete
- Microcanonical thermodynamics in general physical theories
- Nonanalyticity of circuit complexity across topological phase transitions
- Latent Computational Complexity of Symmetry-Protected Topological Order with Fractional Symmetry
- Preparing topological PEPS on a quantum computer
- Holographic second laws of black hole thermodynamics
- Quantifying quantum coherence in polariton condensates
- Toward physical realizations of thermodynamic resource theories
- Holographic study of entanglement and complexity for mixed states
- Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
- Cayley graphs and complexity geometry
- Holographic complexity for Lifshitz system
- Quantifying the difference between many-body quantum states
- Quantum complexity and the virial theorem
- Identifying quantum phase transitions via geometric measures of nonclassicality
- Complexity and uncomplexity during energy injection
- Bounding the resources for thermalizing many-body localized systems
- Toward the nonequilibrium thermodynamic analog of complexity and the Jarzynski identity
- Partial Distinguishability as a Coherence Resource in Boson Sampling
- Experimental detection of microscopic environments using thermodynamic observables
- Dynamics of quantum resources in regular and Majorana fermion systems
- Purification Complexity without Purifications
Cited by in corpus (18)
- Linear growth of quantum circuit complexity
- Spread Complexity and Topological Transitions in the Kitaev Chain
- Resource theory of quantum scrambling
- Quantum complexity in gravity, quantum field theory, and quantum information science
- Pseudomagic Quantum States
- Magic of Random Matrix Product States
- Complexity-constrained quantum thermodynamics
- Quantum complexity phase transitions in monitored random circuits
- Wavefunction branching: when you can't tell pure states from mixed states
- A Compendious Review of Majorization-Based Resource Theories: Quantum Information and Quantum Thermodynamics
- Toward the nonequilibrium thermodynamic analog of complexity and the Jarzynski identity
- Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity
- Coherence and Imaginarity as Resources in Quantum Circuit Complexity
- Wasserstein Complexity of Quantum Circuits
- Non-stabilizerness and entanglement from cat-state injection
- Resource-Dependent Complexity of Quantum Channels
- Attention to Quantum Complexity
- Toward a physically motivated notion of Gaussian complexity geometry