Name
Abstract | ||
|---|---|---|
The stabilizer rank of a quantum state psi is the minimal r such that vertical bar psi > = Sigma(r)(j=1) c(j) vertical bar phi(j)> for c(j) is an element of C and stabilizer states phi(j). The running time of several classical simulation methods for quantum circuits is determined by the stabi-lizer rank of the n-th tensor power of single-qubit magic states. We prove a lower bound of Omega(n) on the stabilizer rank of such states, im-proving a previous lower bound of Omega(root n) of Bravyi, Smith and Smolin [7]. Further, we prove that for a sufficiently small constant delta, the stabilizer rank of any state which is delta-close to those states is Omega(root 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 approxi-mations and correlation bounds against the majority function. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.22331/q-2022-02-15-652 | QUANTUM |
DocType | Volume | ISSN |
Journal | 6 | 2521-327X |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shir Peleg | 1 | 0 | 0.34 |
| Amir Shpilka | 2 | 1095 | 64.27 |
| Ben Lee Volk | 3 | 0 | 0.34 |