Lecture 6. Universality in quantum circuits

In this lecture we discussed universality in the case of quantum circuits. By means of the deferred measurement principle, any quantum circuit can be effectively reduced to a unitary quantum circuit. Any unitary operation can be realized using a composition of one-qubit gates and entangling gates $C\mathrm{NOT}$. Implementing an arbitrary unitary operation may require at least $\mathcal{O}(4^n)$ elementary operations. Furthermore, we started to discuss universality in the sense of approximations, and proved the Solovey-Kitaev theorem: if a set of gates is universal on a qubit, then this set can realize any unitary operation efficiently.