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] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Nonstabilizerness determining the hardness of direct fidelity estimation", Physical Review A 107 2, 022429 (2023).
[4] 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).
[5] 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).
[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] Benjamin Lovitz and Vincent Steffan, "New techniques for bounding stabilizer rank", Quantum 6, 692 (2022).
[9] Fulvio Gesmundo, "Geometry of Tensors: Open problems and research directions", arXiv:2304.10570, (2023).
[10] Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman, "The Parameterized Complexity of Quantum Verification", arXiv:2202.08119, (2022).
[11] Sahar Atallah, Michael Garn, Sania Jevtic, Yukuan Tao, and Shashank Virmani, "Efficient classical simulation of cluster state quantum circuits with alternative inputs", arXiv:2201.07655, (2022).
[12] Lucas Kocia and Genele Tulloch, "More Optimal Simulation of Universal Quantum Computers", arXiv:2202.01233, (2022).
The above citations are from Crossref's cited-by service (last updated successfully 2023-06-08 08:42:47) and SAO/NASA ADS (last updated successfully 2023-06-08 08:42:48). 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.