Improved upper bounds on the stabilizer rank of magic states

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 vertical bar T = root 2(-1)(vertical bar 0 + e(i pi/4)vertical bar 1 ) in the limit of large m. In particular, we show that vertical bar T (circle times m) can be exactly expressed as a superposition of at most O(2(alpha m)) stabilizer states, where alpha <= 0.3963, improving on the best previously known bound alpha <= 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 poly(n, m)2(alpha m). We also provide improved upper bounds on the stabilizer rank of symmetric product states vertical bar psi (circle times 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 poly(n, m)2(m/2). We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.

Automated summary

In this work, we improve the runtime of classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates by establishing new upper bounds on stabilizer ranks. Through known techniques, our algorithm approximates output probabilities of circuits with a given error using a poly(n, m)2(alpha m) runtime. Additionally, we provide improved upper bounds on the stabilizer rank of symmetric product states and suggest a method to further enhance the upper bounds through the construction of linear codes.