  Recently, the dynamics of quantum systems that involve both unitary evolution
and quantum measurements have attracted attention due to the exotic phenomenon
of measurement-induced phase transitions. The latter refers to a sudden change
in a property of a state of $n$ qubits, such as its entanglement entropy,
depending on the rate at which individual qubits are measured. At the same
time, quantum complexity emerged as a key quantity for the identification of
complex behaviour in quantum many-body dynamics. In this work, we investigate
the dynamics of the quantum state complexity in monitored random circuits,
where $n$ qubits evolve according to a random unitary circuit and are
individually measured with a fixed probability at each time step. We find that
the evolution of the exact quantum state complexity undergoes a phase
transition when changing the measurement rate. Below a critical measurement
rate, the complexity grows at least linearly in time until saturating to a
value $e^{\Omega(n)}$. Above, the complexity does not exceed
$\operatorname{poly}(n)$. In our proof, we make use of percolation theory to
find paths along which an exponentially long quantum computation can be run
below the critical rate, and to identify events where the state complexity is
reset to zero above the critical rate. We lower bound the exact state
complexity in the former regime using recently developed techniques from
algebraic geometry. Our results combine quantum complexity growth, phase
transitions, and computation with measurements to help understand the behavior
of monitored random circuits and to make progress towards determining the
computational power of measurements in many-body systems.
