Lower Bounds on Stabilizer Rank

Abstract

The stabilizer rank of a quantum state $\psi$ is the minimal $r$ such that $|\psi ⟩={\sum }_{j=1}^r{c}_j|{\phi }_j⟩$ for $c_j\in \mathbb{C}$ and stabilizer states ${\phi }_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 (arXiv:1506.01396). 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.

References in corpus (10)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Improved upper bounds on the stabilizer rank of magic states
• Stabilizer rank and higher-order Fourier analysis
• Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials

Cited by in corpus (3)

• Improved upper bounds on the stabilizer rank of magic states
• Stabilizer rank and higher-order Fourier analysis
• New techniques for bounding stabilizer rank