Complexity is not Enough for Randomness

Abstract

We study the dynamical generation of randomness in Brownian systems as a function of the degree of locality of the Hamiltonian. We first express the trace distance to a unitary design for these systems in terms of an effective equilibrium thermal partition function, and provide a set of conditions that guarantee a linear time to design. We relate the trace distance to design to spectral properties of the time-evolution operator. We apply these considerations to the Brownian $p$-SYK model as a function of the degree of locality $p$. We show that the time to design is linear, with a slope proportional to $1/p$. We corroborate that when $p$ is of order the system size this reproduces the behavior of a completely non-local Brownian model of random matrices. For the random matrix model, we reinterpret these results from the point of view of classical Brownian motion in the unitary manifold. Therefore, we find that the generation of randomness typically persists for exponentially long times in the system size, even for systems governed by highly non-local time-dependent Hamiltonians. We conjecture this to be a general property: there is no efficient way to generate approximate Haar random unitaries dynamically, unless a large degree of fine-tuning is present in the ensemble of time-dependent Hamiltonians. We contrast the slow generation of randomness to the growth of quantum complexity of the time-evolution operator. Using known bounds on circuit complexity for unitary designs, we obtain a lower bound determining that complexity grows at least linearly in time for Brownian systems. We argue that these bounds on circuit complexity are far from tight and that complexity grows at a much faster rate, at least for non-local systems.

40 pages + appendices. v3: added references

References in corpus (45)

• A bound on chaos
• Comments on the Sachdev-Ye-Kitaev model
• Black holes and the butterfly effect
• Black holes as mirrors: quantum information in random subsystems
• Fast Scramblers
• Topological phases of fermions in one dimension
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Quantum Computation as Geometry
• Black Holes and Random Matrices
• Chaos and complexity by design
• Towards the fast scrambling conjecture
• Evenly distributed unitaries: on the structure of unitary designs
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• The Second Law of Quantum Complexity
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Chaos, Complexity, and Random Matrices
• Sachdev-Ye-Kitaev Model and Thermalization on the Boundary of Many-Body Localized Fermionic Symmetry Protected Topological States
• Numerical study of fermion and boson models with infinite-range random interactions
• Towards a full solution of the large N double-scaled SYK model
• Preparing random states and benchmarking with many-body quantum chaos
• Linear growth of quantum circuit complexity
• The Structure of Bipartite Quantum States - Insights from Group Theory and Cryptography
• Optimizing quantum process tomography with unitary 2-designs
• Models of quantum complexity growth
• Chord diagrams, exact correlators in spin glasses and black hole bulk reconstruction
• Unitary designs and codes
• Phase Transition in the Density of States of Quantum Spin Glasses
• Convergence rates for arbitrary statistical moments of random quantum circuits
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Dynamical purification and the emergence of quantum state designs from the projected ensemble
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Solvable model of deep thermalization with distinct design times
• Unitary designs from statistical mechanics in random quantum circuits
• Driven quantum dynamics: will it blend?
• Mixing properties of stochastic quantum Hamiltonians
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Concentration of norms and eigenvalues of random matrices
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Chaotic Fast Scrambling At Black Holes
• Fast Scramblers, Horizons and Expander Graphs
• Average-case Speedup for Product Formulas
• Double-scaled SYK and de Sitter Holography
• dS JT Gravity and Double-Scaled SYK

Cited by in corpus (8)

• Quantum complexity in gravity, quantum field theory, and quantum information science
• Dynamics of operator size distribution in q-local quantum Brownian SYK and spin models
• Random Circuits in the Black Hole Interior
• ER for typical EPR
• Entanglement dynamics from universal low-lying modes
• Estimating time in quantum chaotic systems and black holes
• Comparing quantum complexity and quantum fidelity
• Realizing Unitary $k$-designs with a Single Quench