Abstract
In this talk I give an overview of classical simulation of quantum circuits based on low rank stabilizer decompositions. I also discuss recent joint work with Hammam Qassim and Hakop Pashayan (arXiv:2106.07740) in which we improve the runtime of such 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 a single-qubit magic state in the limit of large m. In particular, we show that m copies of the magic state can be exactly expressed as a superposition of at most O(2^am) stabilizer states, where a ≤ 0.3963, improving on the best previously known bound a ≤ 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^{am}.