Fast Stabiliser Simulation with Quadratic Form Expansions

Niel de Beaudrap1 and Steven Herbert2,3

1Department of Informatics, University of Sussex, UK
2Quantinuum (Cambridge Quantum), Terrington House, 13-15 Hills Rd, Cambridge, CB2 1NL, UK
3Department of Computer Science and Technology, University of Cambridge, UK

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


This paper builds on the idea of simulating stabiliser circuits through transformations of {quadratic form expansions}. This is a representation of a quantum state which specifies a formula for the expansion in the standard basis, describing real and imaginary relative phases using a degree-2 polynomial over the integers. We show how, with deft management of the quadratic form expansion representation, we may simulate individual stabiliser operations in $\mathcal{O}(n^2)$ time matching the overall complexity of other simulation techniques [1,2,3]. Our techniques provide economies of scale in the time to simulate simultaneous measurements of all (or nearly all) qubits in the standard basis. Our techniques also allow single-qubit measurements with deterministic outcomes to be simulated in constant time. We also describe throughout how these bounds may be tightened when the expansion of the state in the standard basis has relatively few terms (has low `rank'), or can be specified by sparse matrices. Specifically, this allows us to simulate a `local' stabiliser syndrome measurement in time $\mathcal{O}(n)$, for a stabiliser code subject to Pauli noise --- matching what is possible using techniques developed by Gidney [4] without the need to store which operations have thus far been simulated.

► BibTeX data

► References

[1] S. Aaronson and D. Gottesman, ``Improved simulation of stabilizer circuits,'' Physical Review A, vol. 70, no. 5, nov 2004. [Online]. Available: https:/​/​​10.1103/​physreva.70.052328 0pt.

[2] S. Anders and H. J. Briegel, ``Fast simulation of stabilizer circuits using a graph-state representation,'' Physical Review A, vol. 73, no. 2, Feb 2006. [Online]. Available: http:/​/​​10.1103/​PhysRevA.73.022334 0pt.

[3] S. Bravyi, G. Smith, and J. A. Smolin, ``Trading classical and quantum computational resources,'' Physical Review X, vol. 6, no. 2, Jun 2016. [Online]. Available: http:/​/​​10.1103/​PhysRevX.6.021043 0pt.

[4] C. Gidney, ``Stim: a fast stabilizer circuit simulator,'' Quantum, vol. 5, p. 497, jul 2021. [Online]. Available: https:/​/​​10.22331/​q-2021-07-06-497 0pt.

[5] P. Shor, ``Algorithms for quantum computation: discrete logarithms and factoring,'' pp. 124–134, 1994. [Online]. Available: https:/​/​​10.1109/​SFCS.1994.365700 0pt.

[6] L. K. Grover, ``A fast quantum mechanical algorithm for database search,'' in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ser. STOC '96. New York, NY, USA: Association for Computing Machinery, 1996, p. 212–219. [Online]. Available: https:/​/​​10.1145/​237814.237866 0pt.

[7] D. Gottesman, ``The Heisenberg Representation of Quantum Computers,'' arXiv e-prints, Jul 1998. [Online]. Available: https:/​/​​10.48550/​ARXIV.QUANT-PH/​9807006 0pt.

[8] S. J. Devitt, W. J. Munro, and K. Nemoto, ``Quantum error correction for beginners,'' Reports on Progress in Physics, vol. 76, no. 7, p. 076001, Jun 2013. [Online]. Available: http:/​/​​10.1088/​0034-4885/​76/​7/​076001 0pt.

[9] B. M. Terhal, ``Quantum error correction for quantum memories,'' Reviews of Modern Physics, vol. 87, no. 2, p. 307–346, Apr 2015. [Online]. Available: http:/​/​​10.1103/​RevModPhys.87.307 0pt.

[10] J. Roffe, ``Quantum error correction: an introductory guide,'' Contemporary Physics, vol. 60, no. 3, p. 226–245, Jul 2019. [Online]. Available: http:/​/​​10.1080/​00107514.2019.1667078 0pt.

[11] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, ``Simulation of quantum circuits by low-rank stabilizer decompositions,'' Quantum, vol. 3, p. 181, Sep 2019. [Online]. Available: http:/​/​​10.22331/​q-2019-09-02-181 0pt.

[12] N. de Beaudrap, V. Danos, E. Kashefi, and M. Roetteler, ``Quadratic form expansions for unitaries,'' in Theory of Quantum Computation, Communication, and Cryptography, Y. Kawano and M. Mosca, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 29–46. [Online]. Available: https:/​/​​10.1007/​978-3-540-89304-2_4 0pt.

[13] A. R. Calderbank and P. W. Shor, ``Good quantum error-correcting codes exist,'' Physical Review A, vol. 54, no. 2, p. 1098–1105, Aug 1996. [Online]. Available: http:/​/​​10.1103/​PhysRevA.54.1098 0pt.

[14] J. Dehaene and B. de Moor, ``Clifford group, stabilizer states, and linear and quadratic operations over GF(2),'' Physical Review A, vol. 68, no. 4, p. 042318, Oct 2003. [Online]. Available: https:/​/​​10.1103/​physreva.68.042318 0pt.

[15] M. Van Den Nest, ``Classical simulation of quantum computation, the gottesman-knill theorem, and slightly beyond,'' Quantum Info. Comput., vol. 10, no. 3, Mar 2010. [Online]. Available: https:/​/​​10.26421/​QIC10.3-4-6 0pt.

[16] J. Bermejo-Vega and M. Van Den Nest, ``Classical simulations of abelian-group normalizer circuits with intermediate measurements,'' Quantum Information and Computation, vol. 14, no. 3&4, pp. 181–0216, March 2014. [Online]. Available: https:/​/​​10.26421/​QIC14.3-4-1 0pt.

[17] M. Amy, ``Towards large-scale functional verification of universal quantum circuits,'' Electronic Proceedings in Theoretical Computer Science, vol. 287, p. 1–21, Jan 2019. [Online]. Available: http:/​/​​10.4204/​EPTCS.287.1 0pt.

[18] D. Gross, ``Hudson’s theorem for finite-dimensional quantum systems,'' Journal of Mathematical Physics, vol. 47, no. 12, p. 122107, Dec 2006. [Online]. Available: http:/​/​​10.1063/​1.2393152 0pt.

[19] N. de Beaudrap and S. Herbert, ``Quantum linear network coding for entanglement distribution in restricted architectures,'' Quantum, vol. 4, p. 356, nov 2020. [Online]. Available: https:/​/​​10.22331/​q-2020-11-01-356 0pt.

[20] C. Guan and K. W. Regan, ``Stabilizer circuits, quadratic forms, and computing matrix rank,'' 2019. [Online]. Available: https:/​/​​10.48550/​arxiv.1904.00101 0pt.

[21] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th ed. USA: Cambridge University Press, 2011. [Online]. Available: https:/​/​​10.1017/​CBO9780511976667 0pt.

[22] R. Jozsa and M. Van Den Nest, ``Classical simulation complexity of extended clifford circuits,'' Quantum Info. Comput., vol. 14, no. 7&8, p. 633–648, May 2014. [Online]. Available: https:/​/​​10.48550/​arxiv.1305.6190 0pt.

[23] S. Bravyi and D. Gosset, ``Improved classical simulation of quantum circuits dominated by clifford gates,'' Physical Review Letters, vol. 116, no. 25, Jun 2016. [Online]. Available: http:/​/​​10.1103/​PhysRevLett.116.250501 0pt.

[24] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, ``Surface codes: Towards practical large-scale quantum computation,'' Physical Review A, vol. 86, no. 3, Sep 2012. [Online]. Available: http:/​/​​10.1103/​PhysRevA.86.032324 0pt.

[25] A. J. Landahl, J. T. Anderson, and P. R. Rice, ``Fault-tolerant quantum computing with color codes,'' 2011. [Online]. Available: https:/​/​​10.48550/​arxiv.1108.5738 0pt.

[26] R. Chao and B. W. Reichardt, ``Quantum error correction with only two extra qubits,'' Physical Review Letters, vol. 121, no. 5, Aug 2018. [Online]. Available: http:/​/​​10.1103/​PhysRevLett.121.050502 0pt.

[27] P. W. Shor, ``Fault-tolerant quantum computation,'' in Proceedings of the 37th Annual Symposium on Foundations of Computer Science, ser. FOCS '96. USA: IEEE Computer Society, 1996, p. 56. [Online]. Available: https:/​/​​10.1109/​SFCS.1996.548464 0pt.

[28] D. P. DiVincenzo and P. Aliferis, ``Effective fault-tolerant quantum computation with slow measurements,'' Physical Review Letters, vol. 98, no. 2, Jan 2007. [Online]. Available: http:/​/​​10.1103/​PhysRevLett.98.020501 0pt.

[29] C. H. Bennett, G. Brassard, S. Popescu, B. Schumacher, J. A. Smolin, and W. K. Wootters, ``Purification of noisy entanglement and faithful teleportation via noisy channels,'' Phys. Rev. Lett., vol. 76, pp. 722–725, Jan 1996. [Online]. Available: https:/​/​​10.1103/​physrevlett.76.722 0pt.

[30] R. Nigmatullin, C. J. Ballance, N. de Beaudrap, and S. C. Benjamin, ``Minimally complex ion traps as modules for quantum communication and computing,'' New Journal of Physics, vol. 18, no. 10, p. 103028, 2016. [Online]. Available: https:/​/​​10.1088/​1367-2630/​18/​10/​103028 0pt.

[31] W. Dür and H. J. Briegel, ``Entanglement purification and quantum error correction,'' Reports on Progress in Physics, vol. 70, no. 8, p. 1381–1424, Jul 2007. [Online]. Available: http:/​/​​10.1088/​0034-4885/​70/​8/​R03 0pt.

[32] C. M. Dawson, A. P. Hines, D. Mortimer, H. L. Haselgrove, M. A. Nielsen, and T. J. Osborne, ``Quantum computing and polynomial equations over the finite field Z2,'' Quantum Info. Comput., vol. 5, no. 2, p. 102–112, Mar. 2005. [Online]. Available: https:/​/​​10.48550/​arxiv.quant-ph/​0408129 0pt.

[33] M. Hein, J. Eisert, and H. J. Briegel, ``Multiparty entanglement in graph states,'' Physical Review A, vol. 69, no. 6, Jun 2004. [Online]. Available: http:/​/​​10.1103/​PhysRevA.69.062311 0pt.

[34] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Nest, and H. Briegel, ``Entanglement in graph states and its applications,'' Quantum Computers, Algorithms and Chaos, vol. 162, 03 2006. [Online]. Available: https:/​/​​10.3254/​978-1-61499-018-5-115 0pt.

[35] L. E. Heyfron and E. T. Campbell, ``An efficient quantum compiler that reduces T count,'' Quantum Science and Technology, vol. 4, no. 1, p. 015004, sep 2018. [Online]. Available: https:/​/​​10.1088/​2058-9565/​aad604 0pt.

[36] D. Gottesman and I. L. Chuang, ``Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations,'' Nature, vol. 402, no. 6760, pp. 390–393, 1999. [Online]. Available: https:/​/​​10.1038/​46503 0pt.

[37] B. Zeng, X. Chen, and I. L. Chuang, ``Semi-clifford operations, structure of ${\mathcal{c}}_{k}$ hierarchy, and gate complexity for fault-tolerant quantum computation,'' Phys. Rev. A, vol. 77, p. 042313, Apr 2008. [Online]. Available: https:/​/​​10.1103/​PhysRevA.77.042313 0pt.

[38] A. Edgington, ``Simplex: a fast simulator for Clifford circuits.'' [Online]. Available: https:/​/​​CQCL/​simplex/​releases/​tag/​v1.4.0 0pt.

Cited by

[1] Matthew Amy, Owen Bennett-Gibbs, and Neil J. Ross, "Symbolic Synthesis of Clifford Circuits and Beyond", Electronic Proceedings in Theoretical Computer Science 394, 343 (2023).

[2] Matthew Amy, Owen Bennett-Gibbs, and Neil J. Ross, "Symbolic Synthesis of Clifford Circuits and Beyond", arXiv:2204.14205, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-18 10:36:59) and SAO/NASA ADS (last updated successfully 2024-06-18 10:37:01). The list may be incomplete as not all publishers provide suitable and complete citation data.