Stim: a fast stabilizer circuit simulator

Craig Gidney

doi:10.22331/q-2021-07-06-497

Stim: a fast stabilizer circuit simulator

Craig Gidney

Google Inc., Santa Barbara, California 93117, USA

Published:	2021-07-06, volume 5, page 497
Eprint:	arXiv:2103.02202v3
Doi:	https://doi.org/10.22331/q-2021-07-06-497
Citation:	Quantum 5, 497 (2021).

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

Abstract

This paper presents “Stim", a fast simulator for quantum stabilizer circuits. The paper explains how Stim works and compares it to existing tools. With no foreknowledge, Stim can analyze a distance 100 surface code circuit (20 thousand qubits, 8 million gates, 1 million measurements) in 15 seconds and then begin sampling full circuit shots at a rate of 1 kHz. Stim uses a stabilizer tableau representation, similar to Aaronson and Gottesman's CHP simulator, but with three main improvements. First, Stim improves the asymptotic complexity of deterministic measurement from quadratic to linear by tracking the $inverse$ of the circuit's stabilizer tableau. Second, Stim improves the constant factors of the algorithm by using a cache-friendly data layout and 256 bit wide SIMD instructions. Third, Stim only uses expensive stabilizer tableau simulation to create an initial reference sample. Further samples are collected in bulk by using that sample as a reference for batches of Pauli frames propagating through the circuit.

Featured image: Stim is significantly faster than previous tools at bulk sampling of stabilizer circuits.

Popular summary

Quantum stabilizer circuits are simple enough to be efficiently simulated, but rich enough to represent important quantum effects like teleportation and error correction. Stim can analyze many stabilizer circuits tens of times faster than previous tools, and then collect samples tens of thousands of times faster than previous tools. This is useful because analyzing and simulating stabilizer circuits is a foundational part of quantum error correction research.

► BibTeX data

@article{Gidney2021stimfaststabilizer,
  doi = {10.22331/q-2021-07-06-497},
  url = {https://doi.org/10.22331/q-2021-07-06-497},
  title = {Stim: a fast stabilizer circuit simulator},
  author = {Gidney, Craig},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {497},
  month = jul,
  year = {2021}
}

► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328

[2] Thomas Alexander, Lev Bishop, Andrew Cross, Jay Gambetta, Ali Javadi-Abhari, Blake Johnson, and John Smolin. "a new openqasm for a new era of dynamic circuits". https://medium.com/qiskit/a-new-openqasm-for-a-new-era-of-dynamic-circuits-87f031cac49, 2020. Accessed: 2021-01-26.
https://medium.com/qiskit/a-new-openqasm-for-a-new-era-of-dynamic-circuits-87f031cac49

[3] Simon Anders and Hans J Briegel. Fast simulation of stabilizer circuits using a graph-state representation. Physical Review A, 73 (2): 022334, 2006. 10.1103/PhysRevA.73.022334.
https://doi.org/10.1103/PhysRevA.73.022334

[4] Dave Bacon. Operator quantum error-correcting subsystems for self-correcting quantum memories. Physical Review A, 73 (1): 012340, 2006. 10.1103/PhysRevA.73.012340.
https://doi.org/10.1103/PhysRevA.73.012340

[5] Sergey Bravyi and Dmitri Maslov. Hadamard-free circuits expose the structure of the clifford group. arXiv preprint arXiv:2003.09412, 2020. URL https://arxiv.org/abs/2003.09412.
arXiv:2003.09412

[6] 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. 10.22331/q-2019-09-02-181.
https://doi.org/10.22331/q-2019-09-02-181

[7] Kaifeng Bu and Dax Enshan Koh. Efficient classical simulation of clifford circuits with nonstabilizer input states. Physical review letters, 123 (17): 170502, 2019. 10.1103/PhysRevLett.123.170502.
https://doi.org/10.1103/PhysRevLett.123.170502

[8] Rui Chao, Michael E Beverland, Nicolas Delfosse, and Jeongwan Haah. Optimization of the surface code design for majorana-based qubits. Quantum, 4: 352, 2020. 10.22331/q-2020-10-28-352.
https://doi.org/10.22331/q-2020-10-28-352

[9] Qiskit Contributors. Qiskit: An open-source framework for quantum computing. 2019. 10.5281/zenodo.2562110.
https://doi.org/10.5281/zenodo.2562110

[10] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86: 032324, 2012. URL https://doi.org/10.1103/PhysRevA.86.032324. arXiv:1208.0928.
https://doi.org/10.1103/PhysRevA.86.032324
arXiv:1208.0928

[11] Craig Gidney and Austin G Fowler. Efficient magic state factories with a catalyzed $|ccz\rangle$ to $2|t\rangle $ transformation. Quantum, 3: 135, 2019. 10.22331/q-2019-04-30-135.
https://doi.org/10.22331/q-2019-04-30-135

[12] Craig Gidney, Austin Fowler, and Michael Newman. Informal private conversations about simulation bottlenecks, 2021.

[13] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv preprint quant-ph/9705052, 1997. URL https://arxiv.org/abs/quant-ph/9705052.
arXiv:quant-ph/9705052

[14] David Gross. Hudson’s theorem for finite-dimensional quantum systems. Journal of mathematical physics, 47 (12): 122107, 2006. 10.1063/1.2393152.
https://doi.org/10.1063/1.2393152

[15] Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, 2012. 10.1088/1367-2630/14/12/123011.
https://doi.org/10.1088/1367-2630/14/12/123011

[16] Jakob Nielsen Hořeňovský. "response times: The 3 important limits". https://www.nngroup.com/articles/response-times-3-important-limits/, 1993. Accessed: 2021-01-26.
https://www.nngroup.com/articles/response-times-3-important-limits/

[17] Martin Hořeňovský. "generating random numbers using c++ standard library: the problems". https://codingnest.com/generating-random-numbers-using-c-standard-library-the-problems/, 2020. Accessed: 2021-01-26.
https://codingnest.com/generating-random-numbers-using-c-standard-library-the-problems/

[18] "Yack" (https://quantumcomputing.stackexchange.com/users/11887/yack). Answer to "how many n-qubit stabilizer states are there?". Quantum Stack Exchange, 2020. URL https://quantumcomputing.stackexchange.com/a/11781/119. URL:https://quantumcomputing.stackexchange.com/a/11781/119 (version: 2021-01-27).
https://quantumcomputing.stackexchange.com/a/11781/119

[19] Yifei Huang and Peter Love. Approximate stabilizer rank and improved weak simulation of clifford-dominated circuits for qudits. Physical Review A, 99 (5): 052307, 2019. 10.1103/PhysRevA.99.052307.
https://doi.org/10.1103/PhysRevA.99.052307

[20] Yifei Huang and Peter Love. Feynman-path-type simulation using stabilizer projector decomposition of unitaries. Physical Review A, 103 (2), February 2021. 10.1103/physreva.103.022428. URL https://doi.org/10.1103/physreva.103.022428.
https://doi.org/10.1103/physreva.103.022428

[21] Intel. Intel intrinsics guide (_mm256_and_si256). https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm256_and_si256&expand=301, 2021. Accessed: 2021-01-26.
https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm256_and_si256&expand=301

[22] Angela Karanjai, Joel J Wallman, and Stephen D Bartlett. Contextuality bounds the efficiency of classical simulation of quantum processes. arXiv preprint arXiv:1802.07744, 2018. URL https://arxiv.org/abs/1802.07744.
arXiv:1802.07744

[23] Emanuel Knill. Quantum computing with realistically noisy devices. Nature, 434 (7029): 39–44, 2005. 10.1038/nature03350.
https://doi.org/10.1038/nature03350

[24] Shota Nagayama, Austin G Fowler, Dominic Horsman, Simon J Devitt, and Rodney Van Meter. Surface code error correction on a defective lattice. New Journal of Physics, 19 (2): 023050, 2017. 10.1088/1367-2630/aa5918.
https://doi.org/10.1088/1367-2630/aa5918

[25] Jakob Nielsen. Usability engineering. Morgan Kaufmann, 1994.

[26] Peter Norvig. "approximate timing for various operations on a typical pc". http://norvig.com/21-days.html#answers, 2014. Accessed: 2021-01-26.
http://norvig.com/21-days.html#answers

[27] Patrick Rall, Daniel Liang, Jeremy Cook, and William Kretschmer. Simulation of qubit quantum circuits via pauli propagation. Physical Review A, 99 (6): 062337, 2019. 10.1103/PhysRevA.99.062337.
https://doi.org/10.1103/PhysRevA.99.062337

[28] Quantum AI team and collaborators. Cirq, October 2020. URL https://doi.org/10.5281/zenodo.4062499.
https://doi.org/10.5281/zenodo.4062499

[29] Matthew Ware, Guilhem Ribeill, Diego Riste, Colm Ryan, Blake Johnson, and Marcus P da Silva. Experimental pauli-frame randomization on a superconducting qubit. In APS March Meeting Abstracts, volume 2017, pages L46–004, 2017. 10.1103/PhysRevA.103.042604.
https://doi.org/10.1103/PhysRevA.103.042604

[30] Wikipedia. Advanced Vector Extensions — Wikipedia, the free encyclopedia. http://en.wikipedia.org/w/index.php?title=Advanced%20Vector%20Extensions&oldid=1021841294, 2021. [Online; accessed 11-May-2021].
http://en.wikipedia.org/w/index.php?title=Advanced%20Vector%20Extensions&oldid=1021841294

Cited by

[1] Xhek Turkeshi, "Measurement-induced criticality as a data-structure transition", Physical Review B 106 14, 144313 (2022).

[2] Thien Nguyen, Dmitry Lyakh, Eugene Dumitrescu, David Clark, Jeff Larkin, and Alexander McCaskey, "Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale", ACM Transactions on Quantum Computing 4 1, 1 (2023).

[3] Lucas Berent, Lukas Burgholzer, and Robert Wille, Proceedings of the 28th Asia and South Pacific Design Automation Conference 709 (2023) ISBN:9781450397834.

[4] Piotr Sierant, Marco Schirò, Maciej Lewenstein, and Xhek Turkeshi, "Measurement-induced phase transitions in (d+1) -dimensional stabilizer circuits", Physical Review B 106 21, 214316 (2022).

[5] Piotr Sierant and Xhek Turkeshi, "Controlling Entanglement at Absorbing State Phase Transitions in Random Circuits", Physical Review Letters 130 12, 120402 (2023).

[6] Leandro Stefanazzi, Kenneth Treptow, Neal Wilcer, Chris Stoughton, Collin Bradford, Sho Uemura, Silvia Zorzetti, Salvatore Montella, Gustavo Cancelo, Sara Sussman, Andrew Houck, Shefali Saxena, Horacio Arnaldi, Ankur Agrawal, Helin Zhang, Chunyang Ding, and David I. Schuster, "The QICK (Quantum Instrumentation Control Kit): Readout and control for qubits and detectors", Review of Scientific Instruments 93 4, 044709 (2022).

[7] Piotr Sierant and Xhek Turkeshi, "Universal Behavior beyond Multifractality of Wave Functions at Measurement-Induced Phase Transitions", Physical Review Letters 128 13, 130605 (2022).

[8] Oscar Higgott, "PyMatching: A Python Package for Decoding Quantum Codes with Minimum-Weight Perfect Matching", ACM Transactions on Quantum Computing 3 3, 1 (2022).

[9] Ilkwon Byun, Junpyo Kim, Dongmoon Min, Ikki Nagaoka, Kosuke Fukumitsu, Iori Ishikawa, Teruo Tanimoto, Masamitsu Tanaka, Koji Inoue, and Jangwoo Kim, Proceedings of the 49th Annual International Symposium on Computer Architecture 366 (2022) ISBN:9781450386104.

[10] Thomas Grurl, Christoph Pichler, Jürgen Fuß, and Robert Wille, 2023 36th International Conference on VLSI Design and 2023 22nd International Conference on Embedded Systems (VLSID) 301 (2023) ISBN:979-8-3503-4678-7.

[11] Niel de Beaudrap and Steven Herbert, "Fast Stabiliser Simulation with Quadratic Form Expansions", Quantum 6, 803 (2022).

[12] Craig Gidney, Michael Newman, and Matt McEwen, "Benchmarking the Planar Honeycomb Code", Quantum 6, 813 (2022).

[13] Craig Gidney, Michael Newman, Austin Fowler, and Michael Broughton, "A Fault-Tolerant Honeycomb Memory", Quantum 5, 605 (2021).

[14] Max McGinley, Sthitadhi Roy, and S. A. Parameswaran, "Absolutely Stable Spatiotemporal Order in Noisy Quantum Systems", Physical Review Letters 129 9, 090404 (2022).

[15] Adrien Suau, Gabriel Staffelbach, and Aida Todri-Sanial, "qprof: A gprof-Inspired Quantum Profiler", ACM Transactions on Quantum Computing 4 1, 1 (2023).

[16] Thomas R. Scruby, Michael Vasmer, and Dan E. Browne, "Non-Pauli errors in the three-dimensional surface code", Physical Review Research 4 4, 043052 (2022).

[17] Neereja Sundaresan, Theodore J. Yoder, Youngseok Kim, Muyuan Li, Edward H. Chen, Grace Harper, Ted Thorbeck, Andrew W. Cross, Antonio D. Córcoles, and Maika Takita, "Demonstrating multi-round subsystem quantum error correction using matching and maximum likelihood decoders", Nature Communications 14 1, 2852 (2023).

[18] Alexander Tianlin Hu and Andrey Boris Khesin, "Improved graph formalism for quantum circuit simulation", Physical Review A 105 2, 022432 (2022).

[19] Anbang Wu, Gushu Li, Hezi Zhang, Gian Giacomo Guerreschi, Yufei Ding, and Yuan Xie, Proceedings of the 49th Annual International Symposium on Computer Architecture 337 (2022) ISBN:9781450386104.

[20] Jaime Alvarado-Valiente, Javier Romero-Álvarez, Enrique Moguel, José García-Alonso, and Juan M. Murillo, "Technological diversity of quantum computing providers: a comparative study and a proposal for API Gateway integration", Software Quality Journal (2023).

[21] Oscar Higgott, Thomas C. Bohdanowicz, Aleksander Kubica, Steven T. Flammia, and Earl T. Campbell, "Fragile boundaries of tailored surface codes and improved decoding of circuit-level noise", arXiv:2203.04948, (2022).

[22] Craig Gidney and Dave Bacon, "Less Bacon More Threshold", arXiv:2305.12046, (2023).

[23] Craig Gidney, "Inplace Access to the Surface Code Y Basis", arXiv:2302.07395, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-05-29 13:32:24) and SAO/NASA ADS (last updated successfully 2023-05-29 13:32:25). 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.