Improved upper bounds on the stabilizer rank of magic states
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
| 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
► 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] 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] Nadish de Silva, Ming Yin, and Sergii Strelchuk, "Bases for optimising stabiliser decompositions of quantum states", Quantum Science and Technology 9 4, 045004 (2024).
[7] Aleks Kissinger and John van de Wetering, "Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions", Quantum Science and Technology 7 4, 044001 (2022).
[8] Shir Peleg, Amir Shpilka, and Ben Lee Volk, "Lower Bounds on Stabilizer Rank", Quantum 6, 652 (2022).
[9] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).
[10] Benjamin Lovitz and Vincent Steffan, "New techniques for bounding stabilizer rank", Quantum 6, 692 (2022).
[11] Jonas Helsen and Michael Walter, "Thrifty Shadow Estimation: Reusing Quantum Circuits and Bounding Tails", Physical Review Letters 131 24, 240602 (2023).
[12] 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).
[13] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Nonstabilizerness determining the hardness of direct fidelity estimation", Physical Review A 107 2, 022429 (2023).
[14] Mircea Bejan, Campbell McLauchlan, and Benjamin Béri, "Dynamical Magic Transitions in Monitored Clifford+ T Circuits", PRX Quantum 5 3, 030332 (2024).
[15] 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).
[16] 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).
[17] 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).
[18] 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).
[19] Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang, "Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates", arXiv:2305.13409, (2023).
[20] 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).
[21] Matthew Amy and Lucas Shigeru Stinchcombe, "Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums", arXiv:2408.02778, (2024).
[22] Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman, "The Parameterized Complexity of Quantum Verification", arXiv:2202.08119, (2022).
[23] 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).
[24] Matthew Sutcliffe and Aleks Kissinger, "Procedurally Optimised ZX-Diagram Cutting for Efficient T-Decomposition in Classical Simulation", arXiv:2403.10964, (2024).
[25] Matthew Sutcliffe and Aleks Kissinger, "Fast classical simulation of quantum circuits via parametric rewriting in the ZX-calculus", arXiv:2403.06777, (2024).
[26] Fulvio Gesmundo, "Geometry of Tensors: Open problems and research directions", arXiv:2304.10570, (2023).
[27] Lucas Kocia and Genele Tulloch, "More Optimal Simulation of Universal Quantum Computers", arXiv:2202.01233, (2022).
[28] Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang, "Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation", arXiv:2408.06967, (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2024-09-08 04:18:34) and SAO/NASA ADS (last updated successfully 2024-09-08 04:18:35). 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.