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 orthogonal group of dimension$2^{\mathrm{n}}$is a random Pauli rotation$e^{\mathrm{i}\theta P/2}$. The spectral gap of this random walk is shown to be$\Omega(1/t)$, which coincides with the best previously known bound for a random walk on the permutation group on$\{0,1\}^{\mathrm{n}}$. This implies that the walk gives an$\varepsilon$-approximate unitary t-design in depth$\mathcal{O}(\mathrm{n}t^{2}+t\log\frac{1}{\varepsilon})d$where$d=\mathrm{O}(\log \mathrm{n})$is the circuit depth to implement$e^{\mathrm{i}\theta P/2}$. Our simple proof uses quadratic Casimir operators of Lie algebras.