Resource theory of quantum uncomplexity

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 construct a resource theory of uncomplexity in which the allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy, the complexity entropy, that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. We draw connections to data compression and thermodynamic information erasure under computational limitations, giving a physical interpretation to the complexity entropy. This work unleashes on many-body quantum chaotic systems the resource-theory toolkit from quantum information theory.