Efficient Approximate Unitary Designs from Random Pauli Rotations

Abstract

We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t$</tex>. Specifically, a step of the walk on the unitary or orthogonal group of dimension <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{\mathrm{n}}$</tex> is a random Pauli rotation <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$e^{\mathrm{i}\theta P/2}$</tex>. The spectral gap of this random walk is shown to be <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(1/t)$</tex>, which coincides with the best previously known bound for a random walk on the permutation group on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{0,1\}^{\mathrm{n}}$</tex>. This implies that the walk gives an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon$</tex> -approximate unitary t-design in depth <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}(\mathrm{n}t^{2}+t\log\frac{1}{\varepsilon})d$</tex> where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d=\mathrm{O}(\log \mathrm{n})$</tex> is the circuit depth to implement <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$e^{\mathrm{i}\theta P/2}$</tex>. Our simple proof uses quadratic Casimir operators of Lie algebras.