Lecture 5. Multi-qubit operations

At the beginning of the lecture, we discussed how many elementary operations are required to implement any given gate with accuracy $\varepsilon$. The Solovey-Kitaev theorem states that solving such a problem requires $\mathcal{O}\left(\mathrm{log}^c\frac{1}{\varepsilon}\right)$ operations, and the information-theoretic lower bound is $\mathcal{\Omega}\left(\mathrm{log}\frac{1}{\varepsilon}\right)$. Also, various types of noise are considered on a single qubit: depolarization, dephasing, amplitude damping, and measurement of observables. Then we started talking about multi-qubit systems. We discussed the properties of entangled states, such as Bell states, and the simplest entangling operations $CX$ and $CZ$.