  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. The former constitute subsets of
unitary channels that are epsilon-close to any unitary channel in the diamond
norm. The latter are ensembles of unitaries that (approximately) recover Haar
averages of polynomials in entries of unitary channels up to order $t$.
  In this work we establish quantitative connections between these two notions.
Specifically, we prove that, for a fixed dimension $d$ of the Hilbert space,
unitaries constituting $\delta$-approximate $t$-expanders form $\epsilon$-nets
for $t\simeq\frac{d^{5/2}}{\epsilon}$ and
$\delta=\left(\frac{\epsilon^{3/2}}{d}\right)^{d^2}$. We also show that
$\epsilon$-nets can be used to construct $\delta$-approximate unitary
$t$-designs for $\delta= \epsilon t$. Finally, we prove that the degree of an
exact unitary $t$-design necessary to obtain an $\epsilon$-net must grow at
least fast as $\frac1\epsilon$ (for fixed $d$) 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. Our gate sets need not to be symmetric (i.e. contain gates
together with their inverses) or consist of gates with algebraic entries. We
also show a non-constructive version of the 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.
