Linear growth of quantum circuit complexity

The dynamics of quantum states underlies the emergence of thermodynamics and even recent theories of quantum gravity. Now it has been proven that the quantum complexity of states evolving under random operations grows linearly in time. The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates-this is the operation's exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.

Automated summary

The complexity of quantum states, which is key in quantum computing and black hole theory, has been shown to grow linearly over time under random operations. This study investigates how the complexity of random quantum circuits increases by constructing unitary operations from random two-qubit quantum gates. It is proven that the complexity grows linearly until it saturates at a threshold that is exponentially related to the number of qubits.