quantum-computing

Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones

Amolak Ratan Kalra and Pulkit Sinha

10 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractIn 2024, Kliuchnikov and Schönnenbeck showed a connection between the Barnes Wall lattices, stabilizer states and Clifford operations. In this work, we study their results and relate them to the problem of lower bounding stabilizer ranks. We show the first quantitative lower bound on stabilizer fidelity as a function of stabilizer ranks, which reproduces the linear-by-log lower bound for $\chi_{\delta}({|{H}\rangle^{ \otimes n}})$, i.e, on the approximate stabilizer rank of $|H\rangle^{\otimes n}$. In fact, we show that the lower bound holds even when the fidelity between the approximation and ${|H\rangle}^{\otimes n}$ is exponentially small, which is currently the best lower bound in this regime. Next, we define a new magic monotone for pure states, the Barnes Wall norm, and its corresponding approximate variant. We upper bound these monotones by the $CS$-count of state preparation, and also by the stabilizer ranks. In particular, the upper bound given by the $CS$-count is tight, in the sense that we exhibit states that achieve the bound. Apart from these results, we give a Fidelity Amplification algorithm, which provides a trade-off between approximation error and the stabilizer rank. As a corollary, it gives us a way to compose approximate stabilizer decompositions into approximate decompositions of their tensor products. Finally, we provide an alternate, elementary proof of the existence and density of product states with maximal stabilizer ranks, which was first proven by Lovitz and Steffan (2022), where they used results from algebraic geometry.► BibTeX data@article{Kalra2026stabilizerranks, doi = {10.22331/q-2026-07-29-2179}, url = {https://doi.org/10.22331/q-2026-07-29-2179}, title = {Stabilizer {R}anks, {B}arnes {W}all {L}attices and {M}agic {M}onotones}, author = {Kalra, Amolak Ratan and Sinha, Pulkit}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2179}, month = jul, year = {2026} }► References [1] Daniel Gottesman. ``The Heisenberg Representation of Quantum Computers'' (1998). doi: 10.48550/arXiv.quant-ph/9807006. https://doi.org/10.48550/arXiv.quant-ph/9807006 arXiv:quant-ph/9807006 [2] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Physical Review A 70 (2004). doi: 10.1103/physreva.70.052328. https://doi.org/10.1103/physreva.70.052328 [3] Sergey Bravyi, Graeme Smith, and John A. Smolin. ``Trading classical and quantum computational resources''. Phys. Rev. X 6, 021043 (2016). doi: 10.1103/PhysRevX.6.021043. https://doi.org/10.1103/PhysRevX.6.021043 [4] 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. https://doi.org/10.22331/q-2022-02-15-652 [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 (2019). doi: 10.22331/q-2019-09-02-181. https://doi.org/10.22331/q-2019-09-02-181 [6] Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by clifford gates''.

Physical Review Letters 116 (2016). doi: 10.1103/physrevlett.116.250501. https://doi.org/10.1103/physrevlett.116.250501 [7] Saeed Mehraban and Mehrdad Tahmasbi. ``Quadratic lower bounds on the approximate stabilizer rank: A probabilistic approach''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 608–619. STOC ’24. ACM (2024). doi: 10.1145/3618260.3649733. https://doi.org/10.1145/3618260.3649733 [8] Benjamin Lovitz and Vincent Steffan. ``New techniques for bounding stabilizer rank''. Quantum 6, 692 (2022). doi: 10.22331/q-2022-04-20-692. https://doi.org/10.22331/q-2022-04-20-692 [9] 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. https://doi.org/10.22331/q-2021-12-20-606 [10] Saeed Mehraban and Mehrdad Tahmasbi. ``Improved bounds for testing low stabilizer complexity states''. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Page 1222–1233. STOC '25New York, NY, USA (2025). Association for Computing Machinery. doi: 10.1145/3717823.3718228. https://doi.org/10.1145/3717823.3718228 [11] Arne Heimendahl, Felipe Montealegre-Mora, Frank Vallentin, and David Gross. ``Stabilizer extent is not multiplicative''. Quantum 5, 400 (2021). doi: 10.22331/q-2021-02-24-400. https://doi.org/10.22331/q-2021-02-24-400 [12] Vadym Kliuchnikov and Sebastian Schönnenbeck. ``Stabilizer operators and Barnes-Wall lattices'' (2024). doi: 10.48550/arXiv.2404.17677. https://doi.org/10.48550/arXiv.2404.17677 [13] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. ``Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and t gates''. Quantum Info. Comput. 13, 607–630 (2013). doi: https://doi.org/10.26421/QIC13.7-8-4. https://doi.org/10.26421/QIC13.7-8-4 [14] Neil J. Ross and Peter Selinger. ``Optimal ancilla-free Clifford+$T$ approximation of $Z$-rotations''. Quant. Inf. Comput. 16, 0901–0953 (2016). doi: 10.26421/QIC16.11-12-1. arXiv:1403.2975. https://doi.org/10.26421/QIC16.11-12-1 arXiv:1403.2975 [15] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. ``Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom''.

In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 64:1–64:20. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/LIPIcs.ITCS.2023.64. https://doi.org/10.4230/LIPIcs.ITCS.2023.64 [16] Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by clifford gates''. Phys. Rev. Lett. 116, 250501 (2016). doi: 10.1103/PhysRevLett.116.250501. https://doi.org/10.1103/PhysRevLett.116.250501 [17] John Stillwell. ``The gaussian integers''. In Elements of Number Theory. Pages 101–116.

Springer New York, New York, NY (2003). doi: 10.1007/978-0-387-21735-2_6. https://doi.org/10.1007/978-0-387-21735-2_6 [18] G. Nebe, E. M. Rains, and N. J. A. Sloane. ``A simple construction for the barnes-wall lattices''. Page 333–342. Springer US. (2002). doi: 10.1007/978-1-4615-0895-3_19. https://doi.org/10.1007/978-1-4615-0895-319 [19] Daniele Micciancio and Antonio Nicolosi. ``Efficient bounded distance decoders for barnes-wall lattices''. In 2008 IEEE International Symposium on Information Theory. Pages 2484–2488. (2008). doi: 10.1109/ISIT.2008.4595438. https://doi.org/10.1109/ISIT.2008.4595438 [20] C.D. Olds, A. Lax, G. Davidoff, and G.P. Davidoff. ``The geometry of numbers''. Number v. 41 in Anneli Lax New Mathematical Library. Mathematical Association of America. (2000). doi: 10.5948/UPO9780883859551. https://doi.org/10.5948/UPO9780883859551 [21] 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. https://doi.org/10.1088/2058-9565/ab8963Cited by[1] Srinivasan Arunachalam and Arkopal Dutt, "Learning stabilizer structure of quantum states", arXiv:2510.05890, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-07-29 12:20:13). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-07-29 12:20:12: Could not fetch cited-by data for 10.22331/q-2026-07-29-2179 from Crossref. This is normal if the DOI was registered recently.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. AbstractIn 2024, Kliuchnikov and Schönnenbeck showed a connection between the Barnes Wall lattices, stabilizer states and Clifford operations. In this work, we study their results and relate them to the problem of lower bounding stabilizer ranks. We show the first quantitative lower bound on stabilizer fidelity as a function of stabilizer ranks, which reproduces the linear-by-log lower bound for $\chi_{\delta}({|{H}\rangle^{ \otimes n}})$, i.e, on the approximate stabilizer rank of $|H\rangle^{\otimes n}$. In fact, we show that the lower bound holds even when the fidelity between the approximation and ${|H\rangle}^{\otimes n}$ is exponentially small, which is currently the best lower bound in this regime. Next, we define a new magic monotone for pure states, the Barnes Wall norm, and its corresponding approximate variant. We upper bound these monotones by the $CS$-count of state preparation, and also by the stabilizer ranks. In particular, the upper bound given by the $CS$-count is tight, in the sense that we exhibit states that achieve the bound. Apart from these results, we give a Fidelity Amplification algorithm, which provides a trade-off between approximation error and the stabilizer rank. As a corollary, it gives us a way to compose approximate stabilizer decompositions into approximate decompositions of their tensor products. Finally, we provide an alternate, elementary proof of the existence and density of product states with maximal stabilizer ranks, which was first proven by Lovitz and Steffan (2022), where they used results from algebraic geometry.► BibTeX data@article{Kalra2026stabilizerranks, doi = {10.22331/q-2026-07-29-2179}, url = {https://doi.org/10.22331/q-2026-07-29-2179}, title = {Stabilizer {R}anks, {B}arnes {W}all {L}attices and {M}agic {M}onotones}, author = {Kalra, Amolak Ratan and Sinha, Pulkit}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2179}, month = jul, year = {2026} }► References [1] Daniel Gottesman. ``The Heisenberg Representation of Quantum Computers'' (1998). doi: 10.48550/arXiv.quant-ph/9807006. https://doi.org/10.48550/arXiv.quant-ph/9807006 arXiv:quant-ph/9807006 [2] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Physical Review A 70 (2004). doi: 10.1103/physreva.70.052328. https://doi.org/10.1103/physreva.70.052328 [3] Sergey Bravyi, Graeme Smith, and John A. Smolin. ``Trading classical and quantum computational resources''. Phys. Rev. X 6, 021043 (2016). doi: 10.1103/PhysRevX.6.021043. https://doi.org/10.1103/PhysRevX.6.021043 [4] 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. https://doi.org/10.22331/q-2022-02-15-652 [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 (2019). doi: 10.22331/q-2019-09-02-181. https://doi.org/10.22331/q-2019-09-02-181 [6] Sergey Bravyi and David Gosset. ``Improved classical simulation of quantum circuits dominated by clifford gates''.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed

Discussion

0 professional contributions

Be the first to add a constructive contribution.