Improved upper bounds on the stabilizer rank of magic states

Hammam Qassim; Hakop Pashayan; David Gosset

doi:10.22331/q-2021-12-20-606

Improved upper bounds on the stabilizer rank of magic states

Hammam Qassim^1,2,3, Hakop Pashayan^1,4,5, and David Gosset^1,4,5

¹Institute for Quantum Computing, University of Waterloo, Ontario
²Department of Physics and Astronomy, University of Waterloo, Ontario
³Keysight Technologies Canada, Inc.
⁴Department of Combinatorics and Optimization, University of Waterloo, Ontario
⁵Perimeter Institute for Theoretical Physics, Waterloo, Ontario

Published:	2021-12-20, volume 5, page 606
Eprint:	arXiv:2106.07740v2
Doi:	https://doi.org/10.22331/q-2021-12-20-606
Citation:	Quantum 5, 606 (2021).

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

Abstract

In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of $m$ copies of the magic state $|T\rangle=\sqrt{2}^{-1}(|0\rangle+e^{i\pi/4}|1\rangle)$ in the limit of large $m$. In particular, we show that $|T\rangle^{\otimes m}$ can be exactly expressed as a superposition of at most $O(2^{\alpha m})$ stabilizer states, where $\alpha\leq 0.3963$, improving on the best previously known bound $\alpha \leq 0.463$. This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an $n$-qubit Clifford + T circuit $U$ with $m$ uses of the T gate to within a given inverse polynomial relative error using a runtime $\mathrm{poly}(n,m)2^{\alpha m}$. We also provide improved upper bounds on the stabilizer rank of symmetric product states $|\psi\rangle^{\otimes m}$ more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and $m$ instances of any (fixed) single-qubit $Z$-rotation gate with runtime $\text{poly}(n,m) 2^{m/2}$. We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.

► BibTeX data

@article{Qassim2021improvedupperbounds,
  doi = {10.22331/q-2021-12-20-606},
  url = {https://doi.org/10.22331/q-2021-12-20-606},
  title = {Improved upper bounds on the stabilizer rank of magic states},
  author = {Qassim, Hammam and Pashayan, Hakop and Gosset, David},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {606},
  month = dec,
  year = {2021}
}

► References

[1] Hammam Qassim. Classical simulations of quantum systems using stabilizer decompositions. PhD thesis, 2021.

[2] Hector J Garcia-Ramirez. Hybrid Techniques for Simulating Quantum Circuits using the Heisenberg Representation. PhD thesis, 2014.

[3] Sergey Bravyi, Graeme Smith, and John A. Smolin. Trading classical and quantum computational resources. Physical Review X, 6(2), 2016.
https://doi.org/10.1103/PhysRevX.6.021043

[4] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by clifford gates. Physical Review Letters, 116:250501, 2016.
https://doi.org/10.1103/PhysRevLett.116.250501

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

[6] Lucas Kocia. Improved strong simulation of universal quantum circuits. arXiv:2012.11739, 2020.
arXiv:2012.11739

[7] Shir Peleg, Amir Shpilka, and Ben Lee Volk. Lower bounds on stabilizer rank. Electronic Colloquium on Computational Complexity, Report No. 77, 2021.
https://eccc.weizmann.ac.il/report/2021/077/

[8] Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit lower bounds on strong quantum simulation. IEEE Transactions on Information Theory, 66(9):5585–5600, 2020.
https://doi.org/10.1109/TIT.2020.3004427

[9] Tomoyuki Morimae and Suguru Tamaki. Fine-grained quantum computational supremacy. Quantum Information and Computation, 19(13&14):1089–1115, 2019.
https://doi.org/10.26421/QIC19.13-14-2

[10] Cupjin Huang, Michael Newman, and Mario Szegedy. Explicit lower bounds on strong simulation of quantum circuits in terms of $ t $-gate count. arXiv:1902.04764, 2019.
arXiv:1902.04764

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

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

[13] Maarten Van den Nest. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quantum Information and Computation, 10(3&4):0258–0271, 2010.
https://doi.org/10.26421/QIC10.3-4-6

[14] John Watrous. The theory of quantum information. Cambridge University Press, 2018.

[15] Florence Jessie MacWilliams and Neil James Alexander Sloane. The theory of error correcting codes, volume 16. Elsevier, 1977.

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

Cited by

[1] Matthew Amy and Lucas Shigeru Stinchcombe, "Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums", Quantum 9, 1926 (2025).

[2] Vivien Vandaele, "Lower T-count with faster algorithms", Quantum 9, 1860 (2025).

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

[4] Jonathan Steinberg and Otfried Gühne, "Finding maximal quantum resources", Physical Review A 110 6, 062428 (2024).

[5] Lingxuan Feng and Shunlong Luo, "Optimal ququint diagonal gates for generating Wigner negativity", Physical Review A 113 4, 042434 (2026).

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

[7] Xhek Turkeshi, Anatoly Dymarsky, and Piotr Sierant, "Pauli spectrum and nonstabilizerness of typical quantum many-body states", Physical Review B 111 5, 054301 (2025).

[8] Mircea Bejan, Campbell McLauchlan, and Benjamin Béri, "Dynamical Magic Transitions in Monitored Clifford+ T Circuits", PRX Quantum 5 3, 030332 (2024).

[9] Hanchen Liu, Vikram Ravindranath, and Xiao Chen, "Quantum entanglement phase transitions and computational complexity: Insights from Ising models", Physical Review B 111 2, 024312 (2025).

[10] Yifan Zhang and Yuxuan Zhang, "Classical Simulability of Quantum Circuits with Shallow Magic Depth", PRX Quantum 6 1, 010337 (2025).

[11] Wira Azmoon Ahmad and Matthew Sutcliffe, "Dynamic T-decomposition for classical simulation of quantum circuits", International Journal of Modern Physics C 2543002 (2025).

[12] Nikolaos Koukoulekidis, Hyukjoon Kwon, Hyejung H. Jee, David Jennings, and M. S. Kim, "Faster Born probability estimation via gate merging and frame optimisation", Quantum 6, 838 (2022).

[13] Rafael Aoude, Hannah Banks, Chris D. White, and Martin J. White, "Probing new physics in the top sector using quantum information", Physical Review D 113 11, 115066 (2026).

[14] Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang, Proceedings of the 57th Annual ACM Symposium on Theory of Computing 429 (2025) ISBN:9798400715105.

[15] Sergey Bravyi, David Gosset, and Yinchen Liu, "How to Simulate Quantum Measurement without Computing Marginals", Physical Review Letters 128 22, 220503 (2022).

[16] Salvatore F. E. Oliviero, Lorenzo Leone, Alioscia Hamma, and Seth Lloyd, "Measuring magic on a quantum processor", npj Quantum Information 8 1, 148 (2022).

[17] Ying-Jie 英杰 Qu 曲, Zhao 钊 Chen 陈, Wei-Jie 伟杰 Wang 王, and Hong-Yang 鸿洋 Ma 马, "Approximate error correction scheme for three-dimensional surface codes based reinforcement learning", Chinese Physics B 32 10, 100307 (2023).

[18] Sergi Masot-Llima and Artur Garcia-Saez, "Stabilizer Tensor Networks: Universal Quantum Simulator on a Basis of Stabilizer States", Physical Review Letters 133 23, 230601 (2024).

[19] Kwok Ho Wan, Zhenghao Zhong, and Ainhoa Zapirain, "Simulating magic state cultivation with few Clifford terms", Quantum 10, 2134 (2026).

[20] Salvatore F. E. Oliviero, Lorenzo Leone, and Alioscia Hamma, "Magic-state resource theory for the ground state of the transverse-field Ising model", Physical Review A 106 4, 042426 (2022).

[21] Julien Codsi and John van de Wetering, "Classically simulating intermediate-scale instantaneous quantum polynomial circuits through a random graph approach", Physical Review A 111 1, 012422 (2025).

[22] Filipa C. R. Peres and Ernesto F. Galvão, "Quantum circuit compilation and hybrid computation using Pauli-based computation", Quantum 7, 1126 (2023).

[23] Keming He, Chengkai Zhu, Hongshun Yao, Jinguo Liu, Yinan Li, and Xin Wang, "No-Go Theorems for Universal Quantum State Purification via Classically Simulable Operations", Physical Review Letters 136 9, 090204 (2026).

[24] Aleks Kissinger and John van de Wetering, "Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions", Quantum Science and Technology 7 4, 044001 (2022).

[25] Matthew Sutcliffe and Aleks Kissinger, "Fast Classical Simulation of Quantum Circuits via Parametric Rewriting in the ZX-Calculus", Electronic Proceedings in Theoretical Computer Science 426, 247 (2025).

[26] Giulio Camillo, Filipa C.R. Peres, Markus Heinrich, and Juani Bermejo-Vega, "Symmetry-Accelerated Classical Simulation of Clifford-Dominated Circuits", PRX Quantum 7 2, 020356 (2026).

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

[28] John Gargalionis, Nathan Moynihan, Sokratis Trifinopoulos, Ewan N. V. Wallace, Chris D. White, and Martin J. White, "Spin versus nonstabilizerness in gluon and graviton scattering", Physical Review D 113 1, 016007 (2026).

[29] Chris D. White and Martin J. White, "Magic states of top quarks", Physical Review D 110 11, 116016 (2024).

[30] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).

[31] Jonas Helsen and Michael Walter, "Thrifty Shadow Estimation: Reusing Quantum Circuits and Bounding Tails", Physical Review Letters 131 24, 240602 (2023).

[32] Matthew Sutcliffe and Aleks Kissinger, "Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation", Electronic Proceedings in Theoretical Computer Science 406, 63 (2024).

[33] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Nonstabilizerness determining the hardness of direct fidelity estimation", Physical Review A 107 2, 022429 (2023).

[34] Sitan Chen, Weiyuan Gong, and Qi Ye, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1086 (2024) ISBN:979-8-3315-1674-1.

[35] Filipa C R Peres, Rafael Wagner, and Ernesto F Galvão, "Non-stabilizerness and entanglement from cat-state injection", New Journal of Physics 26 1, 013051 (2024).

[36] Azar C. Nakhl, Ben Harper, Maxwell West, Neil Dowling, Martin Sevior, Thomas Quella, and Muhammad Usman, "Stabilizer Tensor Networks with Magic State Injection", Physical Review Letters 134 19, 190602 (2025).

[37] Adam Husted Kjelstrøm, Andreas Pavlogiannis, and Jaco van de Pol, "Efficient Simulation of High-Level Quantum Gates", Quantum 10, 2093 (2026).

[38] M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, and R. Sweke, "One T Gate Makes Distribution Learning Hard", Physical Review Letters 130 24, 240602 (2023).

[39] Vivien Vandaele, Simon Martiel, Simon Perdrix, and Christophe Vuillot, " Optimal Hadamard Gate Count for Clifford+ T Synthesis of Pauli Rotations Sequences ", ACM Transactions on Quantum Computing 5 1, 1 (2024).

[40] Guedong Park, Hyukjoon Kwon, and Hyunseok Jeong, "Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions", Physical Review Letters 133 22, 220601 (2024).

[41] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates", Quantum 9, 1907 (2025).

[42] Amolak Ratan Kalra and Pulkit Sinha, "Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones", Quantum 10, 2179 (2026).

[43] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer, and Jay M. Gambetta, "Assessing the Benefits and Risks of Quantum Computers", arXiv:2401.16317, (2024).

[44] Andrey Boris Khesin, "Quantum Computing from Graphs", arXiv:2501.17959, (2025).

[45] Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman, "The Parameterized Complexity of Quantum Verification", arXiv:2202.08119, (2022).

[46] Matthew Sutcliffe and Aleks Kissinger, "Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation", arXiv:2403.10964, (2024).

[47] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao, and Shashank Virmani, "Efficient classical simulation of cluster state quantum circuits with alternative inputs", Quantum 8, 1243 (2024).

[48] Matthew Sutcliffe and Aleks Kissinger, "Fast Classical Simulation of Quantum Circuits via Parametric Rewriting in the ZX-Calculus", arXiv:2403.06777, (2024).

[49] Kwok Ho Wan and Zhenghao Zhong, "Cutting stabiliser decompositions of magic state cultivation with ZX-calculus", arXiv:2509.01224, (2025).

[50] Fulvio Gesmundo, "Geometry of Tensors: Open problems and research directions", arXiv:2304.10570, (2023).

[51] Henry Lamm, "No Quantum Utility from Hadron Masses? No, Quantum Utility from Hadron Masses!", arXiv:2603.00946, (2026).

[52] Lucas Kocia and Genele Tulloch, "More Optimal Simulation of Universal Quantum Computers", arXiv:2202.01233, (2022).

[53] Florian Cottier and Ulysse Chabaud, "Lower Bounds on Coherent State Rank", arXiv:2604.00766, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 16:40:44) and SAO/NASA ADS (last updated successfully 2026-08-17 16:40:51). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.