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] Shir Peleg, Amir Shpilka, and Ben Lee Volk, "Lower Bounds on Stabilizer Rank", Quantum 6, 652 (2022).

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

[3] Salvatore F. E. Oliviero, Lorenzo Leone, Alioscia Hamma, and Seth Lloyd, "Measuring magic on a quantum processor", arXiv:2204.00015.

[4] Sergey Bravyi, David Gosset, and Yinchen Liu, "How to simulate quantum measurement without computing marginals", arXiv:2112.08499.

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

[6] Aleks Kissinger and John van de Wetering, "Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions", arXiv:2109.01076.

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

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

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