TY - JOUR T1 - Complexity-constrained quantum thermodynamics Y1 - 2024 A1 - Anthony Munson A1 - Naga Bhavya Teja Kothakonda A1 - Jonas Haferkamp A1 - Nicole Yunger Halpern A1 - Jens Eisert A1 - Philippe Faist AB -

Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process's complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n-qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state, via a complexity-constrained process, is quantified by the state's complexity entropy. The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the complexity relative entropy. The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer's ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy and determine the complexity entropy's behavior under random circuits. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a complexity conditional entropy, which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of time, as quantified by complexity.

UR - https://arxiv.org/abs/2403.04828 ER - TY - JOUR T1 - Linear growth of quantum circuit complexity JF - Nat. Phys. Y1 - 2022 A1 - Jonas Haferkamp A1 - Philippe Faist A1 - Naga B. T. Kothakonda A1 - Jens Eisert A1 - Nicole Yunger Halpern AB -

The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.

U5 - https://doi.org/10.1038/s41567-022-01539-6 ER - TY - JOUR T1 - Resource theory of quantum uncomplexity JF - Physical Review A Y1 - 2022 A1 - Nicole Yunger Halpern A1 - Naga B. T. Kothakonda A1 - Jonas Haferkamp A1 - Anthony Munson A1 - Jens Eisert A1 - Philippe Faist AB -

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.

VL - 106 UR - https://arxiv.org/abs/2110.11371 U5 - 10.1103/physreva.106.062417 ER - TY - JOUR T1 - Resource theory of quantum uncomplexity Y1 - 2021 A1 - Nicole Yunger Halpern A1 - Naga B. T. Kothakonda A1 - Jonas Haferkamp A1 - Anthony Munson A1 - Jens Eisert A1 - Philippe Faist AB -

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.

UR - https://arxiv.org/abs/2110.11371 ER - TY - JOUR T1 - Continuous symmetries and approximate quantum error correction JF - Phys. Rev. X Y1 - 2020 A1 - Philippe Faist A1 - Sepehr Nezami A1 - Victor V. Albert A1 - Grant Salton A1 - Fernando Pastawski A1 - Patrick Hayden A1 - John Preskill AB -

Quantum error correction and symmetry arise in many areas of physics, including many-body systems, metrology in the presence of noise, fault-tolerant computation, and holographic quantum gravity. Here we study the compatibility of these two important principles. If a logical quantum system is encoded into n physical subsystems, we say that the code is covariant with respect to a symmetry group G if a G transformation on the logical system can be realized by performing transformations on the individual subsystems. For a G-covariant code with G a continuous group, we derive a lower bound on the error correction infidelity following erasure of a subsystem. This bound approaches zero when the number of subsystems n or the dimension d of each subsystem is large. We exhibit codes achieving approximately the same scaling of infidelity with n or d as the lower bound. Leveraging tools from representation theory, we prove an approximate version of the Eastin-Knill theorem: If a code admits a universal set of transversal gates and corrects erasure with fixed accuracy, then, for each logical qubit, we need a number of physical qubits per subsystem that is inversely proportional to the error parameter. We construct codes covariant with respect to the full logical unitary group, achieving good accuracy for large d (using random codes) or n (using codes based on W-states). We systematically construct codes covariant with respect to general groups, obtaining natural generalizations of qubit codes to, for instance, oscillators and rotors. In the context of the AdS/CFT correspondence, our approach provides insight into how time evolution in the bulk corresponds to time evolution on the boundary without violating the Eastin-Knill theorem, and our five-rotor code can be stacked to form a covariant holographic code.

VL - 10 UR - https://arxiv.org/abs/1902.07714 CP - 041018 U5 - https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.041018 ER -