Simulating Clifford + few-T circuits

Question

I want to simulate large stabilizer circuits (H/S/CNOT/MEASURE/feedforward) with a small number of T gates mixed in. How can I do this in a way that scales exponentially only in the number of T gates? Are there existing implementations?

Answer 1

Taking your comment to Kiro to its logical conclusion, the answer is 'yes'. The basic idea is to decompose the T gate 'magic' state $\tfrac{1}{\sqrt 2}\bigl(\lvert 0 \rangle + \mathrm{e}^{i \pi / 4} \lvert 1 \rangle \bigr)$ as a linear combination of stabiliser states. (If you do this for several magic states, this produces an exponentially large linear combination.) Representing the T-gate states involved as density operators, together with any other stabiliser states introduced as inputs or as auxiliary work-space, we can use this expansion to compute the probability of any particular Pauli measurement outcome, such as a standard basis measurement on a single qubit, after performing a stabiliser circuit and gate teleportations of the T gates.

The basic idea behind this can be improved by noting that there is more than one way to expand the T-gate state as a linear combination — particularly if you consider decompositions of several T-gate states at once, rather than expanding each T-gate state independently, and if furthermore you are happy with an approximate simulation rather than an exact one (see e.g. [Bravyi+Gossett 2016] and [Campbell+Howard 2017]).