New techniques for bounding stabilizer rank

Benjamin Lovitz1 and Vincent Steffan2

1Institute for Quantum Computing and Department of Applied Mathematics, University of Waterloo, 200 University Ave W, Waterloo, ON, Canada
2QMATH, Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


In this work, we present number-theoretic and algebraic-geometric techniques for bounding the stabilizer rank of quantum states. First, we refine a number-theoretic theorem of Moulton to exhibit an explicit sequence of product states with exponential stabilizer rank but constant approximate stabilizer rank, and to provide alternate (and simplified) proofs of the best-known asymptotic lower bounds on stabilizer rank and approximate stabilizer rank, up to a log factor. Second, we find the first non-trivial examples of quantum states with multiplicative stabilizer rank under the tensor product. Third, we introduce and study the generic stabilizer rank using algebraic-geometric techniques.

► BibTeX data

► References

[1] Sergey Bravyi, Graeme Smith, and John A. Smolin. ``Trading classical and quantum computational resources''. Physical Review X 6, 021043 (2016). doi: 10.1103/​PhysRevX.6.021043.

[2] Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by Clifford gates''. Physical Review Letters 116, 250501 (2016). doi: 10.1103/​PhysRevLett.116.250501.

[3] 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 (2019). doi: 10.22331/​q-2019-09-02-181.

[4] Hammam Qassim, Hakop Pashayan, and David Gosset. ``Improved upper bounds on the stabilizer rank of magic states''. Quantum 5, 606 (2021). doi: 10.22331/​q-2021-12-20-606.

[5] Shir Peleg, Amir Shpilka, and Ben Lee Volk. ``Lower Bounds on Stabilizer Rank''. Quantum 6, 652 (2022). doi: 10.22331/​q-2022-02-15-652.

[6] David Petrie Moulton. ``Representing powers of numbers as subset sums of small sets''. Journal of Number Theory 89, 193–211 (2001). doi: 10.1006/​jnth.2000.2646.

[7] A. A. Razborov. ``Lower bounds on the size of bounded depth circuits over a complete basis with logical addition''. Mathematical notes of the Academy of Sciences of the USSR 41, 333–338 (1987). doi: 10.1007/​BF01137685.

[8] R. Smolensky. ``Algebraic methods in the theory of lower bounds for boolean circuit complexity''. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. Pages 77–82. (1987). doi: 10.1145/​28395.28404.

[9] R. Smolensky. ``On representations by low-degree polynomials''. In Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science. Pages 130–138. (1993). doi: 10.1109/​SFCS.1993.366874.

[10] J. Landsberg and M. Michałek. ``Towards finding hay in a haystack: explicit tensors of border rank greater than 2.02m in $\mathbb{C}^m \otimes \mathbb{C}^m \otimes \mathbb{C}^m$.'' (2019). arXiv:1912.11927.

[11] Joseph Landsberg. ``Graduate studies in mathematics''. In Tensors: Geometry and Applications. Volume 128 of Graduate Studies in Mathematics. AMS (2011). doi: 10.1090/​gsm/​128.

[12] Hammam Qassim. ``Classical simulations of quantum systems using stabilizer decompositions''. PhD thesis. University of Waterloo. (2021).

[13] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. ``Lower bounds on the non-clifford resources for quantum computations''. Quantum Science and Technology 5, 035009 (2020). doi: 10.1088/​2058-9565/​ab8963.

[14] Jeroen Dehaene and Bart De Moor. ``Clifford group, stabilizer states, and linear and quadratic operations over GF(2)''. Physical Review A 68, 042318 (2003). doi: 10.1103/​PhysRevA.68.042318.

[15] Maarten Van den Nest. ``Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond''. Quantum Information and Computation 10, 258–271 (2010).

[16] Joe Harris. ``Algebraic geometry: A first course''. Graduate Texts in Mathematics. Springer New York. (2013). doi: 10.1007/​978-1-4757-2189-8.

[17] Jay Goldman and Gian-Carlo Rota. ``On the foundations of combinatorial theory IV: Finite vector spaces and Eulerian generating functions.''. Technical report. Harvard University (1970).

[18] David Gross. ``Hudson's theorem for finite-dimensional quantum systems''. Journal of Mathematical Physics 47, 122107 (2006). doi: 10.1063/​1.2393152.

[19] William Feller. ``An introduction to probability theory and its applications''. Volume 1. John Wiley and Sons. (1991). Third edition.

[20] Benjamin Lovitz and Nathaniel Johnston. ``Entangled subspaces and generic local state discrimination with pre-shared entanglement'' (2020). arXiv:2010.02876.

[21] Kil-Chan Ha and Seung-Hyeok Kye. ``Multi-partite separable states with unique decompositions and construction of three qubit entanglement with positive partial transpose''. Journal of Physics A: Mathematical and Theoretical 48, 045303 (2015). doi: 10.1088/​1751-8113/​48/​4/​045303.

[22] Benjamin Lovitz and Fedor Petrov. ``A generalization of Kruskal's theorem on tensor decomposition'' (2021). arXiv:2103.15633.

[23] Daniel Gottesman. ``Stabilizer codes and quantum error correction''. PhD thesis. California Institute of Technology. (1997).

[24] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. (2000). doi: 10.1017/​CBO9780511976667.

[25] Daniel Gottesman. ``The Heisenberg representation of quantum computers''. In 22nd International Colloquium on Group Theoretical Methods in Physics. Pages 32–43. (1998). arXiv:quant-ph/​9807006.

[26] P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan. ``On universal and fault-tolerant quantum computing: A novel basis and a new constructive proof of universality for Shor's basis''. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. (1999). doi: 10.1109/​SFFCS.1999.814621.

[27] Sergey Bravyi and Alexei Kitaev. ``Universal quantum computation with ideal clifford gates and noisy ancillas''. Physical Review A 71, 022316 (2005). doi: 10.1103/​PhysRevA.71.022316.

Cited by

[1] Shir Peleg, Amir Shpilka, and Ben Lee Volk, "Lower Bounds on Stabilizer Rank", arXiv:2106.03214.

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-28 18:59:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-05-28 18:59:47).