A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra

Abstract

Gottesman-Knill theorem states that computations on stabilizer circuits can be simulated on a classical computer, conventional simulation algorithms extensively use linear algebra over bit strings. For instance, given a non-adaptive stabilizer circuit, the problem of computing the probability of a given outcome (strong simulation) is known to be log-space reducible to solving the system of linear equations over Boolean variables, which is commonly done by Gaussian elimination. This note aims to make the connection between stabilizer circuits and Boolean linear algebra even more explicit. To do this, we extend the stabilizer tableau formalism to include stabilizer tableau descriptions of arbitrary stabilizer operations (Clifford channels). Finding the tableau corresponding to the composition of two channels becomes a linear algebra problem. Any stabilizer circuit rewrites to a diagram with stabilizer tableaux on vertices, contracting an edge means to take the composition of channels, to compute the result of the circuit means to fully contract the diagram. Thus, simulating stabilizer circuits reduces to a sequence of Gaussian eliminations. This approach gives a new perspective on explaining the work of stabilizer tableau methods (reproducing the asymptotics) and creates opportunity for exploring various tensor-contraction techniques in stabilizer simulation.

12 pages, 1 table, typos corrected, references added

References in corpus (24)

• Improved Simulation of Stabilizer Circuits
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Multi-party entanglement in graph states
• Stim: a fast stabilizer circuit simulator
• Hudson's Theorem for finite-dimensional quantum systems
• 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
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• Fast simulation of stabilizer circuits using a graph state representation
• Entanglement on mixed stabiliser states--I: Normal Forms and Reduction Procedures
• Standard Form of Qudit Stabilizer Groups
• Efficient Multiplication of Dense Matrices over GF(2)
• Quantum Lego: Building Quantum Error Correction Codes from Tensor Networks
• Stabilizer Tensor Networks: universal quantum simulator on a basis of stabilizer states
• How to simulate quantum measurement without computing marginals
• Fast Stabiliser Simulation with Quadratic Form Expansions
• Tripartite Entanglement in Qudit Stabilizer States and Application in Quantum Error Correction
• A Simplified Stabilizer ZX-calculus
• Spekkens' toy model in all dimensions and its relationship with stabilizer quantum mechanics
• The axiomatic and the operational approaches to resource theories of magic do not coincide
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Quantum Computing from Graphs
• Characterization of non-adaptive Clifford channels