Quantifying quantum states complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how random quantum circuits complexity increases. Consid
er constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitarys exact circuit complexity. We prove that this complexity grows linearly in the number of random gates, with unit probability, until saturating after exponentially many random gates. Our proof is surprisingly short, given the established difficulty of lower-bounding the exact circuit complexity. Our strategy combines differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.
Recent understanding of the thermodynamics of small-scale systems have enabled the characterization of the thermodynamic requirements of implementing quantum processes for fixed input states. Here, we extend these results to construct optimal univers
al implementations of a given process, that is, implementations that are accurate for any possible input state even after many independent and identically distributed (i.i.d.) repetitions of the process. We find that the optimal work cost rate of such an implementation is given by the thermodynamic capacity of the process, which is a single-letter and additive quantity defined as the maximal difference in relative entropy to the thermal state between the input and the output of the channel. As related results we find a new single-shot implementation of time-covariant processes and conditional erasure with nontrivial Hamiltonians, a new proof of the asymptotic equipartition property of the coherent relative entropy, and an optimal implementation of any i.i.d. process with thermal operations for a fixed i.i.d. input state. Beyond being a thermodynamic analogue of the reverse Shannon theorem for quantum channels, our results introduce a new notion of quantum typicality and present a thermodynamic application of convex-split methods.
The resource theory of thermal operations, an established model for small-scale thermodynamics, provides an extension of equilibrium thermodynamics to nonequilibrium situations. On a lattice of any dimension with any translation-invariant local Hamil
tonian, we identify a large set of translation-invariant states that can be reversibly converted to and from the thermal state with thermal operations and a small amount of coherence. These are the spatially ergodic states, i.e., states that have sharp statistics for any translation-invariant observable, and mixtures of such states with the same thermodynamic potential. As an intermediate result, we show for a general state that if the min- and the max-relative entropy to the thermal state coincide approximately, this implies the approximately reversible interconvertibility to and from the thermal state with thermal operations and a small source of coherence. Our results provide a strong link between the abstract resource theory of thermodynamics and more realistic physical systems, as we achieve a robust and operational characterization of the emergence of a thermodynamic potential in translation-invariant lattice systems.
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.
In this chapter we address the topic of quantum thermodynamics in the presence of additional observables beyond the energy of the system. In particular we discuss the special role that the generalized Gibbs ensemble plays in this theory, and derive t
his state from the perspectives of a micro-canonical ensemble, dynamical typicality and a resource-theory formulation. A notable obstacle occurs when some of the observables do not commute, and so it is impossible for the observables to simultaneously take on sharp microscopic values. We show how this can be circumvented, discuss information-theoretic aspects of the setting, and explain how thermodynamic costs can be traded between the different observables. Finally, we discuss open problems and future directions for the topic.
