Abstract
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 Ω(n⁻¹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 Ω(n⁻¹), provided that t is small compared to the local dimension: t²≤ 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 Ω(n⁻¹log⁻¹(n) t^-α(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.