Lower Bounds on Stabilizer Rank

The stabilizer rank of a quantum state ψ is the minimal integer r such that ψ can be written as a linear combination of r stabilizer states. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n-th tensor power of single-qubit magic states. In this talk we'll present a recent improved lower bound of Ω(n) on the stabilizer rank of such states, and an Ω(sqrt{n}/log n) lower bound on the rank of any state which approximates them to a high enough accuracy. Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of the boolean cube, along with some tools from computational complexity theory.  Reference: Peleg, Shir, Amir Shpilka, and Ben Lee Volk. "Lower Bounds on Stabilizer Rank." arXiv preprint arXiv:2106.03214 (2021).