Lecture 11. Projective and unitary designs, random stabilizer states generation, weak simulation of stabilizer circuits with magic

In this Lecture, we talked about the notion of projective and unitary designs, how to generate random stabilizer states, and how to perform weak simulation of stabilizer circuits with magic. A projective design is a set of pure states on a Hilbert space that is sufficiently “symmetric” – this symmetry is expressed by the ability to reduce integrals over Haar's measure to averages over the design. Similarly, a unitary design is a sufficiently “symmetric” family of unitary operators. The set of stabilizer states and the Clifford group are $3$-designs. To sample from these sets, one can use various algorithms. Using these algorithms, it is possible to efficiently estimate some important quantities using randomization. To perform a weak simulation of $\mathrm{Clifford}+T$ circuit, one can randomly select possible outcomes on magic injection gadgets, approximate the magic states by the sum of stabilizer states, and generate measurement results bit-by-bit using strong simulation methods.