Abstract:
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.
