Fast Stabiliser Simulation with Quadratic Form Expansions

Abstract

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 $O(n^2)$ time matching the overall complexity of other simulation techniques [arXiv:quant-ph/0406196, arXiv:quant-ph/0504117, arXiv:1808.00128]. 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 $O(n)$, for a stabiliser code subject to Pauli noise -- matching what is possible using techniques developed by Gidney [arXiv:2103.02202] without the need to store which operations have thus far been simulated.

51 pages; only change are reference format (for Quantum journal)

References in corpus (8)

• Surface codes: Towards practical large-scale quantum computation
• Multi-party entanglement in graph states
• Stim: a fast stabilizer circuit simulator
• Entanglement purification and quantum error correction
• Fast simulation of stabilizer circuits using a graph state representation
• Effective fault-tolerant quantum computation with slow measurements
• Quantum computing and polynomial equations over the finite field Z_2
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank

Cited by in corpus (5)

• Symbolic Synthesis of Clifford Circuits and Beyond
• Fast algorithms for classical specifications of stabiliser states and Clifford gates
• An Extensible Quantum Network Simulator Built on ns-3: Q2NS Design and Evaluation
• Characterization of non-adaptive Clifford channels
• A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra