Resource theory of quantum uncomplexity

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.

Published version

References in corpus (13)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Black holes as mirrors: quantum information in random subsystems
• Complexity and Shock Wave Geometries
• Quantum Computation as Geometry
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Chaos, Complexity, and Random Matrices
• Quantum Complexity and Negative Curvature
• Optimal control, geometry, and quantum computing
• Scrambling in Random Unitary Circuits: Exact Results
• Gibbs-Preserving Maps outperform Thermal Operations in the quantum regime
• Holographic study of entanglement and complexity for mixed states
• Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality
• Purification Complexity without Purifications

Cited by in corpus (16)

• Spread Complexity and Topological Transitions in the Kitaev Chain
• Resource theory of quantum scrambling
• Pseudomagic Quantum States
• Quantum complexity in gravity, quantum field theory, and quantum information science
• 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
• 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
• Toward a physically motivated notion of Gaussian complexity geometry
• Attention to Quantum Complexity