For chaotic quantum dynamics modeled by random unitary circuits, we study the complexity of reduced density matrices of subsystems as a function of evolution time where the initial global state is a product pure state. The state complexity is defined as the minimum number of local quantum channels to generate a given state from a product state to a good approximation. In 1+1 1 + 1 d, we prove that the complexity of subsystems of length \ell ℓ smaller than half grows linearly in time T T at least up to T = \ell / 4 T = ℓ / 4 but becomes zero after time T = \ell /2 T = ℓ / 2 in the limit of a large local dimension, while the complexity of the complementary subsystem of length larger than half grows linearly in time up to exponentially late times. Using holographic correspondence, we give some evidence that the state complexity of the smaller subsystem should actually grow linearly up to time T = \ell/2 T = ℓ / 2 and then abruptly decay to zero.
For chaotic quantum dynamics modeled by random unitary circuits, we study the complexity of reduced density matrices of subsystems as a function of evolution time where the initial global state is a product pure state. The state complexity is defined as the minimum number of local quantum channels to generate a given state from a product state to a good approximation. In 1+1 1 + 1 d, we prove that the complexity of subsystems of length \ell ℓ smaller than half grows linearly in time T T at least up to T = \ell / 4 T = ℓ / 4 but becomes zero after time T = \ell /2 T = ℓ / 2 in the limit of a large local dimension, while the complexity of the complementary subsystem of length larger than half grows linearly in time up to exponentially late times. Using holographic correspondence, we give some evidence that the state complexity of the smaller subsystem should actually grow linearly up to time T = \ell/2 T = ℓ / 2 and then abruptly decay to zero.
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 circuit complexity of time-evolved pure quantum states grows linearly in time for an exponentially long time. This behavior has been proven in certain models, is conjectured to hold for generic quantum many-body systems, and is believed to be dual to the long-time growth of black hole interiors in AdS/CFT. Achieving a similar understanding for mixed states remains an important problem. In this work, we study the circuit complexity of time-evolved subsystems of pure quantum states. We find that for greater-than-half subsystem sizes, the complexity grows linearly in time for an exponentially long time, similarly to that of the full state. However, for less-than-half subsystem sizes, the complexity rises and then falls, returning to low complexity as the subsystem equilibrates. Notably, the transition between these two regimes occurs sharply at half system size. We use holographic duality to map out this picture of subsystem complexity dynamics and rigorously prove the existence of the sharp transition in random quantum circuits. Furthermore, we use holography to predict features of complexity growth at finite temperature that lie beyond the reach of techniques based on random quantum circuits. In particular, at finite temperature, we argue for an additional sharp transition at a critical less-than-half subsystem size. Below this critical value, the subsystem complexity saturates nearly instantaneously rather than exhibiting a rise and fall. This novel phenomenon, as well as an analogous transition above half system size, provides a target for future studies based on rigorous methods.
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.
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.
We study the growth of entanglement and circuit complexity in random passive linear optical networks as a function of the circuit depth. For entanglement dynamics, we start with an initial Gaussian state with all n modes equally squeezed. For random brickwork circuits, we show that entanglement, as measured by the Rényi-2 entropy, grows diffusively as a function of the depth, in contrast to the linear growth for random qubit brickwork circuits. In the other direction, for arbitrary circuit geometries we prove bounds on depths which ensure the average-case subsystem entanglement reaches within a constant factor of the maximum value in all subsystems, and bounds which ensure closeness of the random linear optical unitary to a Haar random unitary in L2 Wasserstein distance. We also consider robust circuit complexity for random one-dimensional brickwall circuits, as measured by the minimum number of gates required in any circuit that approximately implements the linear optical unitary. Viewing this as a function of the number of modes and the circuit depth, we show the robust circuit complexity for random one-dimensional brickwall circuits scales at most diffusively in the depth with high probability, again in contrast to the linear scaling for certain random qubit circuits. The corresponding Gaussian unitary U~ for the approximate implementation retains high output fidelity ∣⟨ψ∣U†U~∣ψ⟩∣2 for pure states ∣ψ⟩ with constrained expected photon-number.
We study the growth and saturation of complexity in Krylov basis in random quantum circuits. In Haar-random unitary evolution, we show that, for large system sizes, this notion of complexity grows linearly before saturating at a late-time value of d/2, where d is the Hilbert space dimension, at timescales ∼d. Our numerical analysis encompasses two classes of random circuits: brick-wall random unitary circuits and Floquet random circuits. In brick-wall case, complexity in Krylov basis exhibits dynamics consistent with Haar-random unitary evolution, while the inclusion of measurements significantly slows its growth down. For Floquet random circuits, we show that localized phases lead to reduced late-time saturation values of the complexity enabling us to probe the transition between thermal and many-body localized phases.