{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T00:45:09Z","timestamp":1776300309999,"version":"3.50.1"},"reference-count":25,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NWO","award":["NETWORKS-024.002.003"],"award-info":[{"award-number":["NETWORKS-024.002.003"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We establish a link between stabilizer states, stabilizer rank, and higher-order Fourier analysis \u2013 a still-developing area of mathematics that grew out of Gowers's celebrated Fourier-analytic proof of Szemer\u00e9di's theorem \\cite{gowers1998new}. We observe that <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>-qudit stabilizer states are so-called nonclassical quadratic phase functions (defined on affine subspaces of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msubsup><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"double-struck\">F<\/mml:mi><\/mml:mrow><mml:mi>p<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msubsup><\/mml:math> where <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>p<\/mml:mi><\/mml:math> 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 \\cite{peleg2021lower} it was shown that the <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>-qubit magic state has stabilizer rank <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x03A9;<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>. Here we show that the qudit analog of the <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>-qubit magic state has stabilizer rank <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x03A9;<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>, 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.<\/jats:p>","DOI":"10.22331\/q-2022-02-09-645","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T10:28:55Z","timestamp":1644402535000},"page":"645","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":15,"title":["Stabilizer rank and higher-order Fourier analysis"],"prefix":"10.22331","volume":"6","author":[{"given":"Farrokh","family":"Labib","sequence":"first","affiliation":[{"name":"CWI, QuSoft, Science Park 123, 1098 XG Amsterdam, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2022,2,9]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Tom Bannink, Jop Bri\u00ebt, 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\u201312:11, March 2019. 10.4230\/LIPIcs.STACS.2019.12.","DOI":"10.4230\/LIPIcs.STACS.2019.12"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.116.250501"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevX.6.021043"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2019-09-02-181"},{"key":"5","unstructured":"Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. arXiv preprint arXiv:1805.01450, 2018."},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.68.042318"},{"key":"7","unstructured":"Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O\u2019Donnell, 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."},{"key":"8","unstructured":"D Gottesman. The heisenberg representation of quantum computers. 6 1998. URL https:\/\/www.osti.gov\/biblio\/319738."},{"key":"9","doi-asserted-by":"crossref","unstructured":"William Timothy Gowers. A new proof of szemer\u00e9di&apos;s theorem for arithmetic progressions of length four. Geometric & Functional Analysis GAFA, 8 (3): 529\u2013551, 1998.","DOI":"10.1007\/s000390050065"},{"key":"10","doi-asserted-by":"publisher","unstructured":"D. Gross. Hudson\u2019s theorem for finite-dimensional quantum systems. Journal of Mathematical Physics, 47 (12): 122107, 2006. 10.1063\/1.2393152.","DOI":"10.1063\/1.2393152"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Thomas H\u00e4ner 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.","DOI":"10.1145\/3126908.3126947"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Hamed Hatami, Pooya Hatami, and Shachar Lovett. Higher-order fourier analysis and applications. Foundations and Trends\u00ae in Theoretical Computer Science, 13 (4): 247\u2013448, 2019. 10.1561\/0400000064.","DOI":"10.1561\/0400000064"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/physreva.71.042315"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.86.022316"},{"key":"15","unstructured":"Zi-Wen Liu and Andreas Winter. Many-body quantum magic. arXiv preprint arXiv:2010.13817, 2020."},{"key":"16","doi-asserted-by":"publisher","unstructured":"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 &apos;08, page 547\u2013556, 2008. 10.1145\/1374376.1374454.","DOI":"10.1145\/1374376.1374454"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. 10.1017\/CBO9780511976667.","DOI":"10.1017\/CBO9780511976667"},{"key":"18","unstructured":"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."},{"key":"19","doi-asserted-by":"publisher","unstructured":"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\u2013110:4. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2022. 10.4230\/LIPIcs.ITCS.2022.110.","DOI":"10.4230\/LIPIcs.ITCS.2022.110"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Swagato Sanyal. Fourier sparsity and dimension. Theory of Computing, 15 (11): 1\u201313, 2019. 10.4086\/toc.2019.v015a011.","DOI":"10.4086\/toc.2019.v015a011"},{"key":"21","unstructured":"Mikhail Smelyanskiy, Nicolas PD Sawaya, and Al\u00e1n Aspuru-Guzik. qhipster: The quantum high performance software testing environment. arXiv preprint arXiv:1601.07195, 2016."},{"key":"22","doi-asserted-by":"crossref","unstructured":"Endre Szemer\u00e9di. On sets of integers containing no $k$ elements in arithmetic progression. Acta Arith, 27 (199-245): 2, 1975. URL http:\/\/eudml.org\/doc\/205339.","DOI":"10.4064\/aa-27-1-199-245"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Terence Tao and Tamar Ziegler. The inverse conjecture for the gowers norm over finite fields in low characteristic. Annals of Combinatorics, 16 (1): 121\u2013188, 2012. 10.1007\/s00026-011-0124-3.","DOI":"10.1007\/s00026-011-0124-3"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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\u20136:24. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 2018. 10.4230\/LIPIcs.CCC.2018.6.","DOI":"10.4230\/LIPIcs.CCC.2018.6"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-02-09-645\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T10:29:20Z","timestamp":1644402560000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-02-09-645\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":25,"URL":"https:\/\/doi.org\/10.22331\/q-2022-02-09-645","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,9]]},"article-number":"645"}}