Lower bounds for data structures with space close to maximum imply circuit lower bounds
- Award ID(s):
- 1813930
- PAR ID:
- 10141154
- 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
-
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