Incompressibility and Spectral Gaps of Random Circuits

Random reversible and quantum circuits form random walks on the alternating group Alt(2n) and unitary group SU(2n), respectively, with each random gate as one step of the walk. Existing bounds on the spectral gap for the t-th moment of these random walks have inverse-polynomial dependence in both n and t. We prove that the gap for random reversible circuits is Ω(n−3) for all t≥1, and the gap for random quantum circuits is Ω(n−3) for t ≤ Θ(2n/2).Importantly, these gaps are independent of t in the respective regimes. We can further improve both gaps to n−1/polylog(n, t) for t ≤ 2Θ(n), which is tight up to polylog factors in n and t. Our spectral gap results have a number of consequences:1)Random reversible circuits with $\mathcal{O}\left( {{n^4}t} \right)$ gates form multiplicative-error t-wise independent (even) permutations for all t ≥ 1; for t ≤ Θ(2n/6.1), we show that $\tilde {\mathcal{O}}\left( {{n^2}t} \right)$ gates suffice.2)Random quantum circuits with $\mathcal{O}\left( {{n^4}t} \right)$ gates form multiplicative-error unitary t-designs for t ≤Θ(2n/2); for t ≤ Θ(22n/5), we show that $\tilde {\mathcal{O}}\left( {{n^2}t} \right)$ gates suffice.3)The robust quantum circuit complexity of random quantum circuits grows linearly for an exponentially long time, proving the robust Brown–Susskind conjecture [1], [2]. We also show an analogous result for random reversible circuits.Our spectral gap bounds are proven by reducing random quantum circuits to a more structured walk: a modification of the "PFC ensemble" from [3] together with an expander on the alternating group due to Kassabov [4], for which we give an efficient implementation using reversible circuits. In our reduction, we approximate the structured walk with local random circuits without losing the gap, which uses tools from the study of frustration-free Hamiltonians.