Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called "magic" state like $|T\rangle^{\otimes n}$, up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit with Clifford gates and $n$ number of $T$ gates. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the "exact" rank of $|T\rangle^{\otimes n}$, meaning the minimal size of a decomposition that exactly produces the state. However, an "approximate" rank is more realistically related to the cost of simulating quantum circuits because exact rank is not robust to errors; there are quantum states with exponentially large exact ranks but constant approximate ranks even with arbitrarily small approximation parameters. No lower bound better than $\tilde \Omega(\sqrt n)$ has been known for the approximate rank. In this paper, we improve this lower bound to $\tilde \Omega (n)$ for a wide range of the approximation parameters. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure and a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure.