Improved upper bounds on the stabilizer rank of magic states

Hammam Qassim1,2,3, Hakop Pashayan1,4,5, and David Gosset1,4,5

1Institute for Quantum Computing, University of Waterloo, Ontario
2Department of Physics and Astronomy, University of Waterloo, Ontario
3Keysight Technologies Canada, Inc.
4Department of Combinatorics and Optimization, University of Waterloo, Ontario
5Perimeter Institute for Theoretical Physics, Waterloo, Ontario

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


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

► 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.

[4] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by clifford gates. Physical Review Letters, 116:250501, 2016.

[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.

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

[7] Shir Peleg, Amir Shpilka, and Ben Lee Volk. Lower bounds on stabilizer rank. Electronic Colloquium on Computational Complexity, Report No. 77, 2021.

[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.

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

[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.

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

[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.

[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.

[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.

Cited by

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

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

[3] 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).

[4] 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).

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

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

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

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

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

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

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

[12] 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).

[13] 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).

[14] 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).

[15] 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).

[16] 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).

[17] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates", arXiv:2305.13409, (2023).

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

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

[20] 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).

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

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

[23] Matthew Sutcliffe and Aleks Kissinger, "Fast classical simulation of quantum circuits via parametric rewriting in the ZX-calculus", arXiv:2403.06777, (2024).

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