2021/06/30 by Shir Peleg, Amir Shpilka, Ben Lee Volk
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Combinatorics #Complexity and Algorithms in Graphs #Degree (music) #Discrete mathematics #Low-power high-performance VLSI design #Mathematical analysis #Mathematics #Omega #Physics #Quadratic equation #Quantum Computing Algorithms and Architecture #Quantum mechanics #Rank (graph theory) #Stabilizer (aeronautics) #State (computer science) #Upper and lower bounds #cs.CC #quant-ph
paper · pdf · doi:10.22331/q-2022-02-15-652
published as Quantum 6, 652 (2022)
arxiv created 2022/02/10 · openalex publication_date 2022/02/15 · arxiv updated 2022/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
The stabilizer rank of a quantum state ψ is the minimal r such that | ψ ⟩ = ∑j=1r cj |φj ⟩ for cj ∈ ℂ and stabilizer states φ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 Ω(n) on the stabilizer rank of such states, improving a previous lower bound of Ω(√(n)) of Bravyi, Smith and Smolin (arXiv:1506.01396). Further, we prove that for a sufficiently small constant δ, the stabilizer rank of any state which is δ-close to those states is Ω(√(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 \mathbbF2n, 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.