  Random quantum circuits are a central concept in quantum information theory
with applications ranging from demonstrations of quantum computational
advantage to descriptions of scrambling in strongly-interacting systems and
black holes. The utility of random quantum circuits in these settings stems
from their ability to rapidly generate quantum pseudo-randomness. In a seminal
paper by Brand\~ao, Harrow, and Horodecki, it was proven that the $t$-th moment
operator of local random quantum circuits on $n$ qudits with local dimension
$q$ has a spectral gap of at least $\Omega(n^{-1}t^{-5-3.1/\log(q)})$, which
implies that they are efficient constructions of approximate unitary designs.
As a first result, we use Knabe bounds for the spectral gaps of
frustration-free Hamiltonians to show that $1D$ random quantum circuits have a
spectral gap scaling as $\Omega(n^{-1})$, provided that $t$ is small compared
to the local dimension: $t^2\leq O(q)$. This implies a (nearly) linear scaling
of the circuit depth in the design order $t$. Our second result is an
unconditional spectral gap bounded below by $\Omega(n^{-1}\log^{-1}(n)
t^{-\alpha(q)})$ for random quantum circuits with all-to-all interactions. This
improves both the $n$ and $t$ scaling in design depth for the non-local model.
We show this by proving a recursion relation for the spectral gaps involving an
auxiliary random walk. Lastly, we solve the smallest non-trivial case exactly
and combine with numerics and Knabe bounds to improve the constants involved in
the spectral gap for small values of $t$.
