Lecture 12. Sparsification lemma, quasiprobabilistic decompositions of quantum circuits

In the last Lecture we discussed an important lemma about the decomposition of a state into the sum of stabiliser states. If we are given some decomposition $\lvert\psi\rangle = \sum_j c_j \lvert\phi_j\rangle$, then we can use the randomisation procedure to construct a random state $\lvert\Omega\rangle$, which is a uniform sum of stabiliser states, close to the desired result with high probability. The number of stabiliser states in the $\lvert\Omega\rangle$ decomposition is bounded by the square of the sum of the absolute values $\sum_j \lvert c_j\rvert$ in the decomposition. The idea of the sparsification lemma is close to the general technique of quantum circuits simulation by decomposition into quasiprobabilistic sums of simpler circuits.