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 $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/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{\}}^{\mathsf{n}}$. This implies that the walk gives an $\epsilon$-approximate unitary $t$-design in depth $O(\mathsf{n}{t}^2+t\log 1/\epsilon )d$ where $d=O(\log \mathsf{n})$ is the circuit depth to implement $e^{\mathrm{i}\theta P/2}$. Our simple proof uses quadratic Casimir operators of Lie algebras.

arXiv comment21 pages, 1 figure

References in corpus (12)

• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Evenly distributed unitaries: on the structure of unitary designs
• Random Quantum Circuits are Approximate 2-designs
• Local random quantum circuits are approximate polynomial-designs
• Models of quantum complexity growth
• Unitary designs and codes
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• Efficient unitary designs with nearly time-independent Hamiltonian dynamics
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
• Efficient unitary designs and pseudorandom unitaries from permutations
• Efficient Unitary T-designs from Random Sums

Cited by in corpus (3)

• Designs from magic-augmented Clifford circuits
• Anticoncentration is (almost) all you need
• Sample Optimal and Memory Efficient Quantum State Tomography