Lecture 10. Strong simulation of stabilizer circuits with magic

In this Lecture, we discussed some results about strong simulation of stabilizer circuits with magic. First of all, we discussed an algorithm that reduces an arbitrary stabiliser scheme with magic to an adaptive sequence of Pauli measurements over magic states. Such a reduction allows one to perform a significant part of the computation on a classical computer, leaving only the essentially quantum part of the computation. Ideas of such reduction can be useful in strong simulation of stabilizer circuits with magic. Indeed, the probability of a particular outcome can be reduced to a Pauli-projection average over magic states. Then, by decomposing the magic state into a sum of stabilizer states, one can estimate the probability of the outcome. The time required for such estimation grows exponentially with the number of magic states.