For a Haar random set$\mathcal {S}\subset U(d)$of quantum gates we consider the uniform measure$\nu_{\mathcal {S}}$whose support is given by$\mathcal {S}$. The measure$\nu _{\mathcal {S}}$can be regarded as a$\delta (\nu _{\mathcal {S}},t)$-approximate$t$-design,$t\in \mathbb {Z}_{+}$. We propose a random matrix model that aims to describe the probability distribution of$\delta (\nu _{\mathcal {S}},t)$for any$t$. Our model is given by a block diagonal matrix whose blocks are independent, given by Gaussian or Ginibre ensembles, and their number, size and type is determined by$t$. We prove that, the operator norm of this matrix,$\delta ({t})$, is the random variable to which$\sqrt {|\mathcal {S}|}\delta (\nu _{\mathcal {S}},t)$converges in distribution when the number of elements in$\mathcal {S}$grows to infinity. Moreover, we characterize our model giving explicit bounds on the tail probabilities$\mathbb {P}(\delta (t)>2+\epsilon)$, for any$\epsilon >0$. We also show that our model satisfies the so-called spectral gap conjecture, i.e. we prove that with the probability 1 there is$t\in \mathbb {Z}_{+}$such that$\sup _{k\in \mathbb {Z}_{+}}\delta (k)=\delta (t)$. Numerical simulations give convincing evidence that the proposed model is actually almost exact for any cardinality of$\mathcal {S}$. The heuristic explanation of this phenomenon, that we provide, leads us to conjecture that the tail probabilities$\mathbb {P}(\sqrt {\mathcal {S}}\delta (\nu _{\mathcal {S}},t)>2+\epsilon)$are bounded from above by the tail probabilities$\mathbb {P}(\delta (t)>2+\epsilon)$of our random matrix model. In particular our conjecture implies that a Haar random set$\mathcal {S}\subset U(d)$satisfies the spectral gap conjecture with the probability 1.

Epsilon-nets and approximate unitary$t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. In this work we study quantitative connections between these two notions. Specifically, we prove that, for$d$dimensional Hilbert space, unitaries constituting$\delta $-approximate$t$-expanders form$\epsilon $-nets for$t\simeq \frac {d^{5/2}}{ \epsilon }$and$\delta \simeq \left ({\frac { \epsilon ^{3/2}}{d}}\right)^{d^{2}}$. We also show that for arbitrary$t$,$\epsilon $-nets can be used to construct$\delta $-approximate unitary$t$-designs for$\delta \simeq \epsilon t$, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary$t$design necessary to obtain an$\epsilon $-net must grow at least as fast as$\frac {1}{ \epsilon }$(for fixed dimension) and not slower than$d^{2}$(for fixed$\epsilon $). This shows near optimality of our result connecting$t$-designs and$\epsilon $-nets. We apply our findings in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in (Brandão et al., 2016). Importantly, our gate sets need not to be symmetric (i.e., contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider compilation of quantum gates and prove a non-constructive Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.