Spring 2020

Improved Upper Bounds on the Stabilizer Rank of Magic States

Friday, Jul. 16, 2021 10:30 am11:15 am

Add to Calendar


David Gosset (University of Waterloo)



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}. 

PDF icon Slides870.53 KB