ECCC-Report TR21-077https://eccc.weizmann.ac.il/report/2021/077Comments and Revisions published for TR21-077en-usSun, 06 Jun 2021 22:23:20 +0300
Paper TR21-077
| Lower Bounds on Stabilizer Rank |
Shir Peleg,
Amir Shpilka,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2021/077The 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 \right\rangle$ 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 [BSS16]. 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.
Sun, 06 Jun 2021 22:23:20 +0300https://eccc.weizmann.ac.il/report/2021/077