skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: Lower bounds for data structures with space close to maximum imply circuit lower bounds
Award ID(s):
1813930
PAR ID:
10141154
Author(s) / Creator(s):
Date Published:
Journal Name:
Theory of Computing
Volume:
15
Issue:
1
ISSN:
1557-2862
Page Range / eLocation ID:
1 to 9
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. The stabilizer rank of a quantum state ψ is the minimal r such that | ψ ⟩ = ∑ j = 1 r c j | φ j ⟩ for c j ∈ C 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 \cite{BSS16}. 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 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. 
    more » « less