2026-07-22T11:36:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15706 2024-03-06T10:56:00Z ddc:004 open_access

Lower Bounds on Stabilizer Rank Peleg, Shir Volk, Ben Lee Shpilka, Amir Quantum Computation Lower Bounds Stabilizer rank Simulation of Quantum computers The stabilizer rank of a quantum state ψ is the minimal r such that |ψ⟩ = ∑_{j = 1}^r c_j |φ_j⟩ for c_j ∈ ℂ 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 [Bravyi et al., 2016]. 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 𝔽₂ⁿ, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shir Peleg and Ben Lee Volk and Amir Shpilka 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.110 urn:nbn:de:0030-drops-157063 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.110 eng https://creativecommons.org/licenses/by/4.0/legalcode