Stabilizer rank and higher-order Fourier analysis

Farrokh Labib

doi:10.22331/q-2022-02-09-645

Warning: Invalid argument supplied for foreach() in /home/www/wordpress/wp-content/plugins/o3po/includes/class-o3po-crossref.php on line 189

Stabilizer rank and higher-order Fourier analysis

Farrokh Labib

CWI, QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands

Published:	2022-02-09, volume 6, page 645
Eprint:	arXiv:2107.10551v2
Doi:	https://doi.org/10.22331/q-2022-02-09-645
Citation:	Quantum 6, 645 (2022).

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

Abstract

We establish a link between stabilizer states, stabilizer rank, and higher-order Fourier analysis – a still-developing area of mathematics that grew out of Gowers's celebrated Fourier-analytic proof of Szemerédi's theorem [10]. We observe that $n$-qudit stabilizer states are so-called nonclassical quadratic phase functions (defined on affine subspaces of $\mathbb{F}_p^n$ where $p$ is the dimension of the qudit) which are fundamental objects in higher-order Fourier analysis. This allows us to import tools from this theory to analyze the stabilizer rank of quantum states. Quite recently, in [20] it was shown that the $n$-qubit magic state has stabilizer rank $\Omega(n)$. Here we show that the qudit analog of the $n$-qubit magic state has stabilizer rank $\Omega(n)$, generalizing their result to qudits of any prime dimension. Our proof techniques use explicitly tools from higher-order Fourier analysis. We believe this example motivates the further exploration of applications of higher-order Fourier analysis in quantum information theory.

► BibTeX data

@article{Labib2022stabilizerrank,
  doi = {10.22331/q-2022-02-09-645},
  url = {https://doi.org/10.22331/q-2022-02-09-645},
  title = {Stabilizer rank and higher-order {F}ourier analysis},
  author = {Labib, Farrokh},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {645},
  month = feb,
  year = {2022}
}

► References

[1] Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee. Bounding quantum-classical separations for classes of nonlocal games. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pages 12:1–12:11, March 2019. 10.4230/LIPIcs.STACS.2019.12.
https://doi.org/10.4230/LIPIcs.STACS.2019.12

[2] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by clifford gates. Phys. Rev. Lett., 116: 250501, Jun 2016. 10.1103/PhysRevLett.116.250501.
https://doi.org/10.1103/PhysRevLett.116.250501

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

[4] Sergey Bravyi, Graeme Smith, and John A. Smolin. Trading classical and quantum computational resources. Phys. Rev. X, 6: 021043, Jun 2016. 10.1103/PhysRevX.6.021043.
https://doi.org/10.1103/PhysRevX.6.021043

[5] 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. 10.22331/q-2019-09-02-181.
https://doi.org/10.22331/q-2019-09-02-181

[6] Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. arXiv preprint arXiv:1805.01450, 2018.
arXiv:1805.01450

[7] 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. 10.1103/PhysRevA.68.042318.
https://doi.org/10.1103/PhysRevA.68.042318

[8] 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. Preprint available at https://simons. berkeley. edu/sites/default/files/openprobsmerged. pdf, 2014.

[9] D Gottesman. The heisenberg representation of quantum computers. 6 1998. URL https://www.osti.gov/biblio/319738.
https://www.osti.gov/biblio/319738

[10] William Timothy Gowers. A new proof of szemerédi's theorem for arithmetic progressions of length four. Geometric & Functional Analysis GAFA, 8 (3): 529–551, 1998.

[11] D. Gross. Hudson’s theorem for finite-dimensional quantum systems. Journal of Mathematical Physics, 47 (12): 122107, 2006. 10.1063/1.2393152.
https://doi.org/10.1063/1.2393152

[12] Thomas Häner and Damian S. Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. ACM, 2017. 10.1145/3126908.3126947.
https://doi.org/10.1145/3126908.3126947

[13] Hamed Hatami, Pooya Hatami, and Shachar Lovett. Higher-order fourier analysis and applications. Foundations and Trends® in Theoretical Computer Science, 13 (4): 247–448, 2019. 10.1561/0400000064.
https://doi.org/10.1561/0400000064

[14] Erik Hostens, Jeroen Dehaene, and Bart De Moor. Stabilizer states and clifford operations for systems of arbitrary dimensions and modular arithmetic. Physical Review A, 71 (4), apr 2005. 10.1103/physreva.71.042315.
https://doi.org/10.1103/physreva.71.042315

[15] Mark Howard and Jiri Vala. Qudit versions of the qubit $\pi$/8 gate. Physical Review A, 86 (2): 022316, 2012. 10.1103/PhysRevA.86.022316.
https://doi.org/10.1103/PhysRevA.86.022316

[16] Zi-Wen Liu and Andreas Winter. Many-body quantum magic. arXiv preprint arXiv:2010.13817, 2020.
arXiv:2010.13817

[17] Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky. Inverse conjecture for the gowers norm is false. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC '08, page 547–556, 2008. 10.1145/1374376.1374454.
https://doi.org/10.1145/1374376.1374454

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

[19] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, and Robert Wisnieff. Breaking the 49-qubit barrier in the simulation of quantum circuits. arXiv preprint arXiv:1710.05867, 15, 2017.
arXiv:1710.05867

[20] Shir Peleg, Ben Lee Volk, and Amir Shpilka. Lower Bounds on Stabilizer Rank. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 110:1–110:4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. 10.4230/LIPIcs.ITCS.2022.110.
https://doi.org/10.4230/LIPIcs.ITCS.2022.110

[21] Swagato Sanyal. Fourier sparsity and dimension. Theory of Computing, 15 (11): 1–13, 2019. 10.4086/toc.2019.v015a011.
https://doi.org/10.4086/toc.2019.v015a011

[22] Mikhail Smelyanskiy, Nicolas PD Sawaya, and Alán Aspuru-Guzik. qhipster: The quantum high performance software testing environment. arXiv preprint arXiv:1601.07195, 2016.
arXiv:1601.07195

[23] Endre Szemerédi. On sets of integers containing no $k$ elements in arithmetic progression. Acta Arith, 27 (199-245): 2, 1975. URL http://eudml.org/doc/205339.
http://eudml.org/doc/205339

[24] Terence Tao and Tamar Ziegler. The inverse conjecture for the gowers norm over finite fields in low characteristic. Annals of Combinatorics, 16 (1): 121–188, 2012. 10.1007/s00026-011-0124-3.
https://doi.org/10.1007/s00026-011-0124-3

[25] Richard 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 Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:24. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. 10.4230/LIPIcs.CCC.2018.6.
https://doi.org/10.4230/LIPIcs.CCC.2018.6

Cited by

[1] Nadish de Silva, Ming Yin, and Sergii Strelchuk, "Bases for optimising stabiliser decompositions of quantum states", Quantum Science and Technology 9 4, 045004 (2024).

[2] Shir Peleg, Amir Shpilka, and Ben Lee Volk, "Lower Bounds on Stabilizer Rank", Quantum 6, 652 (2022).

[3] Saeed Mehraban and Mehrdad Tahmasbi, "Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach", arXiv:2305.10277, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2024-09-16 23:24:06). 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 2024-09-16 23:24:05).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.