License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.110
URN: urn:nbn:de:0030-drops-157063
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15706/
Peleg, Shir ;
Volk, Ben Lee ;
Shpilka, Amir
Lower Bounds on Stabilizer Rank
Abstract
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.
BibTeX - Entry
@InProceedings{peleg_et_al:LIPIcs.ITCS.2022.110,
author = {Peleg, Shir and Volk, Ben Lee and Shpilka, Amir},
title = {{Lower Bounds on Stabilizer Rank}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {110:1--110:4},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15706},
URN = {urn:nbn:de:0030-drops-157063},
doi = {10.4230/LIPIcs.ITCS.2022.110},
annote = {Keywords: Quantum Computation, Lower Bounds, Stabilizer rank, Simulation of Quantum computers}
}
|
Keywords: |
|
Quantum Computation, Lower Bounds, Stabilizer rank, Simulation of Quantum computers |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
