Explicit orthogonal and unitary designs

Abstract

We give a strongly explicit construction of $\epsilon$-approximate $k$-designs for the orthogonal group $\mathrm{O}(N)$ and the unitary group $\mathrm{U}(N)$, for $N=2^n$. Our designs are of cardinality $\mathrm{poly}(N^k/\epsilon )$ (equivalently, they have seed length $O(nk+\log (1/\epsilon )))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.