Saturation and recurrence of quantum complexity in random local quantum dynamics

Abstract

Quantum complexity is a measure of the minimal number of elementary operations required to approximately prepare a given state or unitary channel. Recently, this concept has found applications beyond quantum computing -- in studying the dynamics of quantum many-body systems and the long-time properties of AdS black holes. In this context Brown and Susskind \cite{BrownSusskind17} conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly-exponential times. In this work we prove the saturation and recurrence of complexity in two models of chaotic time evolutions based on (i) random local quantum circuits and (ii) stochastic local Hamiltonian evolution. Our results advance an understanding of the long-time behaviour of chaotic quantum systems and could shed light on the physics of black hole interiors. From a technical perspective our results are based on establishing new quantitative connections between the Haar measure and high-degree approximate designs, as well as the fact that random quantum circuits of sufficiently high depth converge to approximate designs.

arXiv comment57 pages, 6 figures, comments and suggestions are welcome, major changes in v2: new title, simplified reasoning based on global gaps, inclusion of SLH model of random evolutions, numerous narrative changes throughout the text, new author

References in corpus (45)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Eternal Black Holes in AdS
• Black holes as mirrors: quantum information in random subsystems
• Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order
• Complexity and Shock Wave Geometries
• Time Evolution of Entanglement Entropy from Black Hole Interiors
• Operator Spreading in Random Unitary Circuits
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Complexity, action, and black holes
• Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws
• Quantum Computation as Geometry
• Towards the fast scrambling conjecture
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• The Second Law of Quantum Complexity
• Chaos, Complexity, and Random Matrices
• Complexity and entanglement for thermofield double states
• Quantum Computation as Gravity
• Circuit complexity for free fermions
• Truncations of random unitary matrices
• Linear growth of quantum circuit complexity
• Complexity as a novel probe of quantum quenches: universal scalings and purifications
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Efficient Discrete Approximations of Quantum Gates
• Models of quantum complexity growth
• Quantum Complexity of Time Evolution with Chaotic Hamiltonians
• Decoupling with random quantum circuits
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Complexity for Conformal Field Theories in General Dimensions
• Exact convergence times for generation of random bipartite entanglement
• Operator Dynamics in Brownian Quantum Circuit
• Large Deviation Bounds for k-designs
• Entangling power and quantum circuit complexity
• Mixing properties of stochastic quantum Hamiltonians
• A relation between Krylov and Nielsen complexity
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• On the sub-Gaussianity of the Beta and Dirichlet distributions
• A Quantum Complexity Lowerbound from Differential Geometry
• EFT Diagrammatica II: Tracing the UV origin of bosonic D6 CPV and D8 SMEFT operators
• Fluctuations of subsystem entropies at late times
• Universality in long-distance geometry and quantum complexity
• Operational Quantum Average-Case Distances
• Polynomial Equivalence of Complexity Geometries
• Calculable lower bounds on the efficiency of universal sets of quantum gates

Cited by in corpus (5)

• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Random Circuits in the Black Hole Interior
• Fundamental solutions of heat equation on unitary groups establish an improved relation between $\epsilon$-nets and approximate unitary $t$-designs
• Shallow quantum circuit for generating extremely low-entangled approximate state designs
• Comparing quantum complexity and quantum fidelity