  Quantifying quantum states' complexity is a key problem in various subfields
of science, from quantum computing to black-hole physics. We prove a prominent
conjecture by Brown and Susskind about how random quantum circuits' complexity
increases. Consider constructing a unitary from Haar-random two-qubit quantum
gates. Implementing the unitary exactly requires a circuit of some minimal
number of gates - the unitary's exact circuit complexity. We prove that this
complexity grows linearly with the number of random gates, with unit
probability, until saturating after exponentially many random gates. Our proof
is surprisingly short, given the established difficulty of lower-bounding the
exact circuit complexity. Our strategy combines differential topology and
elementary algebraic geometry with an inductive construction of Clifford
circuits.
