# Lower Bounds on Stabilizer Rank

Shir Peleg1, Amir Shpilka1, and Ben Lee Volk2

1Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel
2Efi Arazi School of Computer Science, Reichman University, Herzliya, Israel

### Abstract

The $\textit{stabilizer rank}$ of a quantum state $\psi$ is the minimal $r$ such that $\left| \psi \right \rangle = \sum_{j=1}^r c_j \left|\varphi_j \right\rangle$ for $c_j \in \mathbb{C}$ and stabilizer states $\varphi_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 $\Omega(n)$ on the stabilizer rank of such states, improving a previous lower bound of $\Omega(\sqrt{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(\sqrt{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 $\mathbb{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.

### ► References

[1] Scott Aaronson and Alex Arkhipov. The Computational Complexity of Linear Optics. Theory Comput., 9:143–252, 2013. doi:10.4086/​toc.2013.v009a004.
https:/​/​doi.org/​10.4086/​toc.2013.v009a004

[2] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A, 70:052328, Nov 2004. doi:10.1103/​PhysRevA.70.052328.
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328

[3] Ethan Bernstein and Umesh V. Vazirani. Quantum Complexity Theory. SIAM J. Comput., 26(5):1411–1473, 1997. doi:10.1137/​S0097539796300921.
https:/​/​doi.org/​10.1137/​S0097539796300921

[4] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum, 3:181, September 2019. doi:10.22331/​q-2019-09-02-181.
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[5] Sergey Bravyi and David Gosset. Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates. Phys. Rev. Lett., 116:250501, Jun 2016. doi:10.1103/​PhysRevLett.116.250501.
https:/​/​doi.org/​10.1103/​PhysRevLett.116.250501

[6] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71:022316, Feb 2005. doi:10.1103/​PhysRevA.71.022316.
https:/​/​doi.org/​10.1103/​PhysRevA.71.022316

[7] Sergey Bravyi, Graeme Smith, and John A. Smolin. Trading Classical and Quantum Computational Resources. Phys. Rev. X, 6:021043, Jun 2016. doi:10.1103/​PhysRevX.6.021043.
https:/​/​doi.org/​10.1103/​PhysRevX.6.021043

[8] Jeroen Dehaene and Bart De Moor. Clifford group, stabilizer states, and linear and quadratic operations over GF(2). Phys. Rev. A, 68:042318, Oct 2003. doi:10.1103/​PhysRevA.68.042318.
https:/​/​doi.org/​10.1103/​PhysRevA.68.042318

[9] Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O'Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer. Real Analysis in Computer Science: A collection of Open Problems. Simons Institute, 2014. URL: https:/​/​simons.berkeley.edu/​sites/​default/​files/​openprobsmerged.pdf.
https:/​/​simons.berkeley.edu/​sites/​default/​files/​openprobsmerged.pdf

[10] Daniel Gottesman. Stabilizer Codes and Quantum Error Correction. Dissertation (Ph.D.), California Institute of Technology, 1997. doi:10.7907/​rzr7-dt72.
https:/​/​doi.org/​10.7907/​rzr7-dt72

[11] Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 212–219. ACM, 1996. doi:10.1145/​237814.237866.
https:/​/​doi.org/​10.1145/​237814.237866

[12] Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit Lower Bounds on Strong Quantum Simulation. IEEE Trans. Inf. Theory, 66(9):5585–5600, 2020. doi:10.1109/​TIT.2020.3004427.
https:/​/​doi.org/​10.1109/​TIT.2020.3004427

[13] Daniel J. Kleitman. On a combinatorial conjecture of Erdös. Journal of Combinatorial Theory, 1(2):209–214, 1966. doi:10.1016/​S0021-9800(66)80027-3.
https:/​/​doi.org/​10.1016/​S0021-9800(66)80027-3

[14] Lucas Kocia. Improved Strong Simulation of Universal Quantum Circuits. arXiv preprint arXiv:2012.11739, 2020. URL: https:/​/​arxiv.org/​abs/​2012.11739.
arXiv:2012.11739

[15] Farrokh Labib. Stabilizer rank and higher-order Fourier analysis. arXiv preprint arXiv:2107.10551, 2021. URL: https:/​/​arxiv.org/​abs/​2107.10551.
https:/​/​doi.org/​10.22331/​q-2022-02-09-645
arXiv:2107.10551

[16] Benjamin Lovitz and Vincent Steffan. New techniques for bounding stabilizer rank. arXiv preprint arXiv:2110.07781, 2021. URL: https:/​/​arxiv.org/​abs/​2110.07781.
arXiv:2110.07781

[17] Tomoyuki Morimae and Suguru Tamaki. Fine-grained quantum computational supremacy. Quant. Inf. Comput., 19:1089, 2019. doi:10.26421/​QIC19.13-14-2.
https:/​/​doi.org/​10.26421/​QIC19.13-14-2

[18] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press, 2016. doi:10.1017/​CBO9780511976667.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[19] Hammam Qassim, Hakop Pashayan, and David Gosset. Improved upper bounds on the stabilizer rank of magic states. Quantum, 5:606, December 2021. doi:10.22331/​q-2021-12-20-606.
https:/​/​doi.org/​10.22331/​q-2021-12-20-606

[20] Ran Raz and Avishay Tal. Oracle separation of BQP and PH. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 13–23. ACM, 2019. doi:10.1145/​3313276.3316315.
https:/​/​doi.org/​10.1145/​3313276.3316315

[21] Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mat. Zametki, 41:598–607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987. doi:10.1007/​BF01137685.
https:/​/​doi.org/​10.1007/​BF01137685

[22] Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput., 26(5):1484–1509, 1997. doi:10.1137/​S0097539795293172.
https:/​/​doi.org/​10.1137/​S0097539795293172

[23] Daniel R. Simon. On the Power of Quantum Computation. SIAM J. Comput., 26(5):1474–1483, 1997. doi:10.1137/​S0097539796298637.
https:/​/​doi.org/​10.1137/​S0097539796298637

[24] Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 77–82. ACM, 1987. doi:10.1145/​28395.28404.
https:/​/​doi.org/​10.1145/​28395.28404

[25] Roman Smolensky. On Representations by Low-Degree Polynomials. In 34th Annual Symposium on Foundations of Computer Science, pages 130–138. IEEE Computer Society, 1993. doi:10.1109/​SFCS.1993.366874.
https:/​/​doi.org/​10.1109/​SFCS.1993.366874

[26] Maarten Van den Nest. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quant. Inf. Comput., 10:258, 2010. doi:10.26421/​QIC10.3-4-6.
https:/​/​doi.org/​10.26421/​QIC10.3-4-6

[27] R. Ryan Williams. Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials. In 33rd Computational Complexity Conference, CCC 2018, volume 102 of LIPIcs, pages 6:1–6:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi:10.4230/​LIPIcs.CCC.2018.6.
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2018.6

### Cited by

[1] Benjamin Lovitz and Vincent Steffan, "New techniques for bounding stabilizer rank", Quantum 6, 692 (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2022-05-28 21:17:06). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2022-05-28 21:17:06).