Universality verification for a set of quantum gates

We establish a relationship between the notion of universal quantum gates and the notion of unitary $t$-designs. We show that a set of qudit gates $\mathcal{S}\subset U\left(d\right)$ is universal if and only if $\mathcal{S}$ forms a $\delta$-approximate $t\left(d\right)$-design, where $\delta <1, t\left(2\right)=6$, and $t\left(d\right)=4$ for $d\ge 3$. Moreover, we argue that from the application point of view sets $\mathcal{S}$ with the $\delta$ close to 1 should be regarded as nonuniversal. We also provide a second, more algebraic, criterion for the universality verification. It says that $\mathcal{S}\subset U\left(d\right)$ is universal if and only if the matrices that commute with $\{U^{\otimes t\left(d\right)}\otimes {\overline{U}}^{\otimes t\left(d\right)}|U\in \mathcal{S}\}$ commute also with $\{U^{\otimes t\left(d\right)}\otimes {\overline{U}}^{\otimes t\left(d\right)}|U\in U\left(d\right)\}$, where $t\left(2\right)=3$, and $t\left(d\right)=2$ for $d\ge 3$. Finally, we show that the complexity of checking this algebraic criterion scales polynomially with the dimension $d$.