Lecture 7. Universality of quantum circuits

In this Lecture we continued to discuss properties of quantum circuits. First of all, we considered measurements in more detail: arbitrary non-destructive and/or entangling measurements can be reduced using by ancillae and unitary gates to destructive measurements of the computational basis. Then, we discussed the simplest protocols of quantum communication: transmission of classical information through a quantum channel, generation of entanglement using a quantum channel, superdense coding, and quantum teleportation. We talked about the deferred measurement principle: measurements over a qubit can always be “deferred” until the end of the computation by using quantum control. In particular, using this principle, any classical circuit can be reduced to a unitary quantum circuit. We also proved the universality of the set of arbitrary one-qubit gates and $C\mathrm{NOT}$ gates. Finally, we introduced the class $\mathtt{BQP}$ of languages efficiently decidable quantum circuits.