The value of lacking complexity in quantum computation

Quantum complexity is emerging as a key feature of many-body systems, including black holes, topological materials, and early quantum computers.

A state’s complexity quantifies the difficulty of preparing the state from a simple tensor product, or the difficulty of uncomputing the state to 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. I will unite the two domains, meeting Brown and Susskind’s long-standing challenge to construct a resource theory of uncomplexity. I will present the resource theory’s definition, two operational tasks analyzable in the theory, and monotones (resource-theory measures of a state’s usefulness). This work brings to many-body complexity a powerful mathematical and conceptual toolkit from quantum information theory.

References

1) NYH, Kothakonda, Haferkamp, Munson, Eisert, and Faist, Phys. Rev. A 106, 062417 (2022).
2) Haferkamp, Kothakonda, Faist, Eisert, and NYH, Nat. Phys. (2022).