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 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 a quantitative connection between spectral gaps of random walks on the unitary group and the property of approximate equidistribution, which turns out to be crucial for establishing saturation and recurrence.

The talk is based on a joint work with Marcin Kotowski, Nick Hunter Jones and Michał Horodecki, preprint arXiv:2205.09734 (accepted for publication in Physical Review X).