Models of Quantum Complexity Growth

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.

Automated summary

The concept of quantum complexity has significant implications in various fields, but deriving lower bounds on quantum complexity for specific unitaries or states remains challenging. By studying generic models of complexity growth and connecting complexity growth with unitary k-designs, researchers can draw conclusions about the growth of complexity in quantum systems. Local random quantum circuits are shown to generate unitary transformations with linear complexity growth, supporting previous conjectures and emphasizing the importance of optimal distinguishing measurements in defining quantum complexity.