Lower Bounds on Stabilizer Rank

Quantum 6, 652 (2022).

https://doi.org/10.22331/q-2022-02-15-652

The $textit{stabilizer rank}$ of a quantum state $psi$ is the minimal $r$ such that $left| psi right rangle = sum_{j=1}^r c_j left|varphi_j rightrangle$ for $c_j in mathbb{C}$ and stabilizer states $varphi_j$. 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.
We prove a lower bound of $Omega(n)$ on the stabilizer rank of such states, improving a previous lower bound of $Omega(sqrt{n})$ of Bravyi, Smith and Smolin [7]. Further, we prove that for a sufficiently small constant $delta$, the stabilizer rank of any state which is $delta$-close to those states is $Omega(sqrt{n}/log n)$. This is the first non-trivial lower bound for approximate stabilizer rank.
Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of $mathbb{F}_2^n$, and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.