Matrix concentration inequalities and efficiency of random universal sets of quantum gates

For a random set $\mathcal{S}\subset U(d)$ of quantum gates we provide bounds on the probability that $\mathcal{S}$ forms a $\delta$-approximate $t$-design. In particular we have found that for $\mathcal{S}$ drawn from an exact $t$-design the probability that it forms a $\delta$-approximate $t$-design satisfies the inequality $$\mathbb{P}$\left(\delta \geq x \right)\leq 2D_t , \frac{e^{-|$\mathcal{S}$| x , $\mathrm{a}\mathrm{r}\mathrm{c}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}$(x)}}{(1-x^2)^{|$\mathcal{S}$|/2}} = O\left( 2D_t \left( \frac{e^{-x^2}}{\sqrt{1-x^2}} \right)^{|$\mathcal{S}$|} \right)$,where$D_t$ is a sum over dimensions of unique irreducible representations appearing in the decomposition of $U\mapsto U^{\otimes t}\otimes {\bar{U}}^{\otimes t}$. We use our results to show that to obtain a $\delta$-approximate $t$-design with probability $P$ one needs $O({\delta }^{-2}(t\log (d)-\log (1-P)))$ many random gates. We also analyze how $\delta$ concentrates around its expected value $\mathbb{E}\delta$ for random $\mathcal{S}$. Our results are valid for both symmetric and non-symmetric sets of gates.