Improved upper bounds on the stabilizer rank of magic states

Quantum 5, 606 (2021).

https://doi.org/10.22331/q-2021-12-20-606

In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of $m$ copies of the magic state $|Trangle=sqrt{2}^{-1}(|0rangle+e^{ipi/4}|1rangle)$ in the limit of large $m$. In particular, we show that $|Trangle^{otimes m}$ can be exactly expressed as a superposition of at most $O(2^{alpha m})$ stabilizer states, where $alphaleq 0.3963$, improving on the best previously known bound $alpha leq 0.463$. This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an $n$-qubit Clifford + T circuit $U$ with $m$ uses of the T gate to within a given inverse polynomial relative error using a runtime $mathrm{poly}(n,m)2^{alpha m}$. We also provide improved upper bounds on the stabilizer rank of symmetric product states $|psirangle^{otimes m}$ more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and $m$ instances of any (fixed) single-qubit $Z$-rotation gate with runtime $text{poly}(n,m) 2^{m/2}$. We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.