Lecture 8. Universality in approximate sense

In this Lecture we discussed whether it is possible to perform quantum computation efficiently if we have only a finite set of quantum operations available. In such a case, arbitrary quantum operations can only be expressed with some precision $\varepsilon>0$. The accuracy drops linearly as the number of operations increases. Owing to the Solovey-Kitaev theorem, we can rewrite any quantum circuit of size $\mathrm{SIZE}$ as a quantum circuit with a finite universal dictionary of gates, with size $\mathrm{SIZE}' = \mathrm{SIZE}\cdot \mathrm{polylog}\frac{\mathrm{SIZE}}{\varepsilon}$. The proof of the theorem relies on properties of the group $\mathrm{SU}(2)$. This theorem can be interpreted as guaranteeing the possibility, as in the classical case, to digitise continuous quantities. Also, this property turns out to be important for achieving fault-tolerance of quantum computations.