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}\ensuremath{\subset}U(d)$ is universal if and only if $\mathcal{S}$ forms a $\ensuremath{\delta}$-approximate $t(d)$-design, where $\ensuremath{\delta}<1, t(2)=6$, and $t(d)=4$ for $d\ensuremath{\ge}3$. Moreover, we argue that from the application point of view sets $\mathcal{S}$ with the $\ensuremath{\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}\ensuremath{\subset}U(d)$ is universal if and only if the matrices that commute with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}\mathcal{S}}$ commute also with ${{U}^{\ensuremath{\bigotimes}t(d)}\ensuremath{\bigotimes}{\overline{U}}^{\ensuremath{\bigotimes}t(d)}|U\ensuremath{\in}U(d)}$, where $t(2)=3$, and $t(d)=2$ for $d\ensuremath{\ge}3$. Finally, we show that the complexity of checking this algebraic criterion scales polynomially with the dimension $d$.