Efficient approximate unitary designs from random Pauli rotations

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order $t$. Specifically, a step of the walk on the unitary or orthognoal group of dimension $2^{\mathsf{n}}$ is a random Pauli rotation $e^{\mathrm{i}\theta P\mathrm{/}2}$. The spectral gap of this random walk is shown to be $\mathrm{\Omega }(1\mathrm{/}t)$, which coincides with the best previously known bound for a random walk on the permutation group on $\{0,1{\}}^{\mathsf{n}}$. This implies that the walk gives an $\epsilon$-approximate unitary $t$-design in depth $O(\mathsf{n}{t}^2+t\log 1\mathrm{/}\epsilon )d$ where $d=O(\log \mathsf{n})$ is the circuit depth to implement $e^{\mathrm{i}\theta P\mathrm{/}2}$. Our simple proof uses quadratic Casimir operators of Lie algebras.