Abstract:
The quantum complexity of a unitary or state is defined as the size of the shortest quantum computation that implements the unitary or prepares the state, and the notion has far-reaching implications spanning computer science, quantum many-body physics, and high energy theory. Complexity growth in time is a phenomenon expected to occur in holographic theories and strongly-interacting many-body systems more generally, but proving anything about the complexity of a state or unitary is notoriously difficult. By considering ensembles of systems, and using tools from quantum information theory, we will prove statements about complexity growth in various models and prove a linear growth of complexity in random quantum circuits (a simple model of local chaotic dynamics).