Lecture 2. Complexity of circuits and simulation

In this lecture, we look at a number of topics around the notion of computational power of quantum circuits. First of all, we talk about the simplest quantum communication protocols: quantum entanglement distribution, quantum teleportation, and superdense coding. Another important example is the one-bit teleportation protocol. Some set of operations is called universal if it can be used to assemble a circuit that implements arbitrary functions in the corresponding class. Some universal dictionaries for classical, reversible and quantum circuits are discussed. A discussion of the general definition of the complexity classes $\mathrm{BPP}$ and $\mathrm{BQP}$ is given and the question of their equality is formulated. Two notions of circuits simulation are introduced: weak simulation is the problem of constructing a random variable reproducing the measurement statistics of a quantum circuit; strong simulation is the problem of computing the exact value of the outcome probability. The simplest methods of strong simulation are the Schrödinger and Feynman simulation methods. The problem of reducing a weak simulation to a strong one is reduced to the problem of sampling from a distribution, and reducing a strong simulation to a weak one is equivalent to the problem of statistical estimation.