Quantum (Un)complexity: A resource for quantum computation - Anthony Christopher Munson

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.

Meeting ID: 935 9861 1120 Passcode: 904671