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 (29)

• Surface codes: Towards practical large-scale quantum computation
• Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
• Good Quantum Error-Correcting Codes Exist
• Quantum Teleportation is a Universal Computational Primitive
• Improved Simulation of Stabilizer Circuits
• Quantum Error Correction for Quantum Memories
• Multi-party entanglement in graph states
• Quantum Error Correction for Beginners
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Stim: a fast stabilizer circuit simulator
• Quantum Error Correction: An Introductory Guide
• Hudson's Theorem for finite-dimensional quantum systems
• Entanglement purification and quantum error correction
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Quantum error correction with only two extra qubits
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Fast simulation of stabilizer circuits using a graph state representation
• Effective fault-tolerant quantum computation with slow measurements
• Towards Large-scale Functional Verification of Universal Quantum Circuits
• Fault-tolerant quantum computing with color codes
• Minimally complex ion traps as modules for quantum communication and computing
• Semi-Clifford operations, structure of ${\mathcal{C}}_k$ hierarchy, and gate complexity for fault-tolerant quantum computation
• Quantum linear network coding for entanglement distribution in restricted architectures
• Quantum computing and polynomial equations over the finite field Z_2
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
• Classical simulation complexity of extended Clifford circuits

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