Quantum circuit complexity is a fundamental concept whose importance permeates quantum information, computation, many-body physics and high-energy physics. While extensively studied in closed systems, its characterization and behaviors in the widely important setting where the system is embedded within a larger one -- encompassing measurement-assisted state preparation -- lack systematic understanding. We introduce the notion of embedded complexity that characterizes the complexity of projected states and measurement operators in this general setting incorporating auxiliary systems and measurements. For random circuits and certain strongly interacting time-independent Hamiltonian dynamics, we show that the embedded complexity is lower-bounded by the circuit volume -- the total number of gates acting on both the subsystem and its complement. This strengthens the complexity linear growth theorems, enriches the understanding of deep thermalization, and indicates that measurement-assisted methods generically cannot yield significant advantages in state preparation cost, contrary to expectations. We further demonstrate a spacetime conversion of certain circuit models that concentrates circuit volume onto a subsystem, and showcase applications for random circuit sampling and shadow tomography. Our theory establishes a unified framework for space and time aspects of quantum circuit complexity, yielding profound new insights and applications across quantum information and physics.
Quantum circuit complexity is a fundamental concept whose importance permeates quantum information, computation, many-body physics and high-energy physics. While extensively studied in closed systems, its characterization and behaviors in the widely important setting where the system is embedded within a larger one -- encompassing measurement-assisted state preparation -- lack systematic understanding. We introduce the notion of embedded complexity that characterizes the complexity of projected states and measurement operators in this general setting incorporating auxiliary systems and measurements. For random circuits and certain strongly interacting time-independent Hamiltonian dynamics, we show that the embedded complexity is lower-bounded by the circuit volume -- the total number of gates acting on both the subsystem and its complement. This strengthens the complexity linear growth theorems, enriches the understanding of deep thermalization, and indicates that measurement-assisted methods generically cannot yield significant advantages in state preparation cost, contrary to expectations. We further demonstrate a spacetime conversion of certain circuit models that concentrates circuit volume onto a subsystem, and showcase applications for random circuit sampling and shadow tomography. Our theory establishes a unified framework for space and time aspects of quantum circuit complexity, yielding profound new insights and applications across quantum information and physics.
Abstract Quantum circuit complexity is a pivotal concept in quantum information, quantum many-body physics, and high-energy physics. While extensively studied for closed systems, the characterization and dynamics of circuit complexity are little understood for the situation where the system is embedded within a larger system, which encompasses measurement-assisted state preparation. To address this gap, we introduce the notion of embedded complexity, which accounts for both system extensions and measurements. We study the complexity of projected states in a subsystem after measuring its complement and find that in random circuits, the embedded complexity is lower-bounded by the circuit volume---the total number of gates affecting both the subsystem and its complement. This finding indicates that the total cost of preparing the projected state cannot be reduced by leveraging ancillary qubits and measurements in general. Our result underscores the operational meaning of circuit volume, as it characterizes the embedded complexity of the generated state. Specifically, for random circuits or Clifford circuits, we demonstrate a spacetime conversion that concentrates circuit volume onto a subsystem via a random gate teleportation approach. In scenarios of deep thermalization where the system interacts extensively with a larger system, our analysis suggests that the resulting projected states exhibit high complexity. Additionally, we introduce a shadow tomography protocol that employs only ancillary random states and Bell state measurements, circumventing the need to evolve the input state and thereby simplifying experimental controls.
The quantum circuit complexity of an evolving many-body quantum system is believed to exhibit a sustained growth, maintained for timescales much longer than the onset of thermalization. Most previous works have focused on models which violate energy conservation, such as random unitary circuits. Here we study generic, local time-independent Hamiltonian dynamics. We unconditionally prove that for generic local Hamiltonians and typical initial product states at high effective temperature, the robust quantum circuit complexity must grow over a very long period of time, attaining an exponentially large value at late times. Our approach relies on two structural properties that we prove rigorously: (i) generic local Hamiltonians satisfy generalized spectral no-resonance conditions of arbitrary order, and (ii) typical high-temperature product states are effectively supported in exponentially many energy eigenstates. These properties have been widely assumed without proof in prior works. As corollaries of this result, we show the late-time state displays robust volume-law entanglement that is irremovable by polynomial-size circuits, and we establish a no fast-forwarding result for generic local Hamiltonians. We also lower bound the complexity of preparing sufficiently large subsystems with local quantum channels, in contrast with sufficiently small thermalizing regions which we show retain low complexity at late times.
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.
This work proposes quantum circuit complexity—the minimal number of elementary operations needed to implement a quantum transformation—be established as a legitimate physical observable. We prove that circuit complexity satisfies all requirements for physical observables, including self-adjointness, gauge invariance, and a consistent measurement theory with well-defined uncertainty relations. We develop complete protocols for measuring complexity in quantum systems and demonstrate its connections to gauge theory and quantum gravity. Our results suggest that computational requirements may constitute physical laws as fundamental as energy conservation. This framework grants insights into the relationship between quantum information, gravity, and the emergence of spacetime geometry while offering practical methods for experimental verification. Our results indicate that the physical universe may be governed by both energetic and computational constraints, with profound implications for our understanding of fundamental physics.
Quantum complexity has emerged as a natural probe of chaos, thermalization, and the black hole interior on timescales long after local observables have equilibrated. However, its time evolution has been studied almost exclusively in subsystems confined to a single connected region. We show, using complementary tools from holography and random quantum circuits, that noncontiguous subsystems composed of multiple disjoint regions give rise to qualitatively new physics compared to the contiguous case. First, at finite temperature, a subsystem occupying less than half of the total system can carry high complexity at late times, even as the complexity of its larger complement remains low. This inversion of the usual hierarchy is intrinsically thermal: it vanishes in the infinite-temperature limit, which is the regime modeled by random quantum circuits. Second, if a subsystem's complexity equilibrates at an early time, then fragmenting it into m disjoint components can further reduce this timescale by a factor of m, a phenomenon we exhibit in both holography and random quantum circuits. These results not only sharpen the correspondence between geometric and computational notions of complexity, but also motivate the search for novel complexity phenomena in quantum dynamics.
Entanglement and circuit complexity are fundamental concepts in quantum information theory which turned out to have considerable applications in various contexts ranging from many-body systems and condensed matter theory to quantum gravity and black hole physics. In order to find connections between these aspects, an insightful approach consists in comparing the complexity with some entanglement measures of a given bipartition, as for instance the Von Neumann entanglement entropy. Since, for a system in a given quantum state, the bipartite entanglement can be determined once a spatial subsystem and its complement are chosen, this comparison has to be made considering the complexity of reduced density matrices. This motivates the development of techniques for determining the circuit complexity of mixed states. In this thesis, focussing on free bosonic systems, we study the circuit complexity of mixed Gaussian states by employing the Fisher information geometry for the covariance matrices. This approach allows computing the complexity between reduced density matrices (subsystem complexity), as well as the complexity between thermal states. It also leads to a precise prescription for computing the spectrum and the basis complexity and the temporal evolution of the subsystem complexity after global and local quantum quenches. The study of the subsystem complexity of a given bipartition and a complete characterisation of its entanglement requires the detailed knowledge of the corresponding reduced density matrix, or, equivalently, of the entanglement Hamiltonian. A part of this thesis is devoted to determining the entanglement Hamiltonians in free theories. At equilibrium, we consider gapless systems, with the aim of recovering the underlying CFT results, and gapped lattice models. The evolution of entanglement Hamiltonians in quantum chains after a global quench is also studied. In addition, other entanglement quantifiers, as the entanglement spectrum and the contour for the entanglement entropies, are discussed in some of these settings. Finally, motivated by theoretical and experimental advances, we also address the issue of how the entanglement splits into the different charge sectors of a system endowed with a U(1) symmetry. We focus in particular on massive theories, either continuous or on the lattice, and we try to understand whether the entanglement equipartition, which is known to characterise gapless systems, survives away from criticality.