Quantum (Un)complexity: A Resource for Quantum Computation

Abstract: Under random dynamics, a system’s quantum complexity—which quantifies the difficulty of preparing a desired state from a simple, tensor-product state—increases linearly up to times exponential in the system’s size, long after most physical observables have thermalized. The observation that complexity saturation is a late stage of quantum thermalization suggests that a state’s lack of complexity, or ``uncomplexity,'' is a useful resource for quantum computation: Much as a system far from thermal equilibrium can serve as a resource in information-processing tasks, a state with high uncomplexity—i.e., a low-complexity state such as |0^n>—can be utilized as ``blank scrap paper'' for quantum computers. It is natural, therefore, to view uncomplexity through the lens of a resource theory. In a resource theory, an agent can perform any operation subject to a fixed set of simple rules, and can identify which tasks are achievable under these rules and which tasks require additional resources. We define a resource theory of uncomplexity, and then construct protocols in the resource theory for extracting uncomplexity from a state and for expending uncomplexity to imitate a state. Moreover, we show that a new quantity, the complexity entropy, quantifies the efficiencies with which we can perform uncomplexity extraction and expenditure, and thereby quantifies the resource requirements for one-shot thermodynamic erasure (Landauer erasure) under computational limitations.

Yunger Halpern, Kothakonda, Haferkamp, Munson, Eisert, and Faist (2021). arxiv.org/abs/2110.11371

HEP - theorymathematical physicsquantum physics

Audience: researchers in the topic

Purdue HET

Series comments: The recorded talks will be available on YouTube here: www.youtube.com/playlist?list=PLxU3vHZccQj64m9zsQR74D5WP1z1g4t1J