Fast simulation of stabilizer circuits using a graph state representation

Abstract

According to the Gottesman-Knill theorem, a class of quantum circuits, namely the so-called stabilizer circuits, can be simulated efficiently on a classical computer. We introduce a new algorithm for this task, which is based on the graph-state formalism. It shows significant improvement in comparison to an existing algorithm, given by Gottesman and Aaronson, in terms of speed and of the number of qubits the simulator can handle. We also present an implementation.

v2: significantly improved presentation; accepted by PRA

References in corpus (12)

• Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
• Good Quantum Error-Correcting Codes Exist
• Persistent entanglement in arrays of interacting particles
• Measurement-based quantum computation with cluster states
• Improved Simulation of Stabilizer Circuits
• Quantum privacy amplification and the security of quantum cryptography over noisy channels
• Multiple Particle Interference and Quantum Error Correction
• Multi-party entanglement in graph states
• Quantum error-correcting codes associated with graphs
• Graphical description of the action of local Clifford transformations on graph states
• Multi-Particle Entanglement Purification Protocols
• Multiparticle entanglement purification for graph states

Cited by in corpus (93)

• Ultracold atomic gases in optical lattices: mimicking condensed matter physics and beyond
• Positive Wigner functions render classical simulation of quantum computation efficient
• Stim: a fast stabilizer circuit simulator
• Simulation of quantum circuits by low-rank stabilizer decompositions
• NetSquid, a NETwork Simulator for QUantum Information using Discrete events
• Learning-based quantum error mitigation
• Layered architecture for quantum computing
• Optimizing Quantum Error Correction Codes with Reinforcement Learning
• The ZX-calculus is complete for stabilizer quantum mechanics
• Measurement-induced criticality and entanglement clusters: a study of 1D and 2D Clifford circuits
• Classical simulation versus universality in measurement based quantum computation
• Efficient Representation of Topologically Ordered States with Restricted Boltzmann Machines
• Long-range big quantum-data transmission
• Errors and pseudo-thresholds for incoherent and coherent noise
• Compact Gaussian quantum computation by multi-pixel homodyne detection
• Augmenting Density Matrix Renormalization Group with Clifford Circuits
• Complex Quantum Networks: a Topical Review
• Fault-tolerant quantum computation with non-deterministic entangling gates
• Mapping graph state orbits under local complementation
• Transport and entanglement growth in long-range random Clifford circuits
• Protecting quantum memories using coherent parity check codes
• Error statistics and scalability of quantum error mitigation formulas
• A single $T$-gate makes distribution learning hard
• Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
• Practical Topological Cluster State Quantum Computing Requires Loss Below 1%
• Modeling Pauli measurements on graph states with nearest-neighbor classical communication
• Fast Stabiliser Simulation with Quadratic Form Expansions
• Entanglement in highly symmetric multipartite quantum states
• Hard limits on the postselectability of optical graph states
• Logical independence and quantum randomness
• Simulating the Transverse Ising Model on a Quantum Computer: Error Correction with the Surface Code
• Fragility of quantum correlations and coherence in a multipartite photonic system
• Solving search problems by strongly simulating quantum circuits
• Mana and thermalization: probing the feasibility of near-Clifford Hamiltonian simulation
• Quantum communication cost of preparing multipartite entanglement
• Bipartite separability and non-local quantum operations on graphs
• Classical Ising model test for quantum circuits
• Compilation of algorithm-specific graph states for quantum circuits
• Symbolic Execution for Quantum Error Correction Programs
• Loss-tolerant teleportation on large stabilizer states
• Efficient Formal Verification of Quantum Error Correcting Programs
• Logic Synthesis for Fault-Tolerant Quantum Computers
• Measurement-Based Time Evolution for Quantum Simulation of Fermionic Systems
• An introduction to one-way quantum computing in distributed architectures
• Efficient Entanglement Measure for Graph States
• Noisy Stabilizer Formalism
• Disentangling critical quantum spin chains with Clifford circuits
• State complexity and quantum computation
• Discrete Wigner Function Derivation of the Aaronson-Gottesman Tableau Algorithm
• SANQ: A Simulation Framework for Architecting Noisy Intermediate-Scale Quantum Computing System
• Quantum simulation using noisy unitary circuits and measurements
• Analytical Error Analysis of Clifford Gates by the Fault-Path Tracer Method
• Designing fault-tolerant circuits using detector error models
• Randomized Benchmarking of Clifford Operators
• Universal quantum gates, artificial neurons and pattern recognition simulated by \textit{LC} resonators
• Improved Graph Formalism for Quantum Circuit Simulation
• Imperfect quantum networks with tailored resource states
• Quantum Complexity: restrictions on algorithms and architectures
• Scalable evaluation of quantum-circuit error loss using Clifford sampling
• Qudit Shadow Estimation Based on the Clifford Group and the Power of a Single Magic Gate
• Fast simulation of planar Clifford circuits
• An Exact Link between Nonlocal Nonstabilizerness and Operator Entanglement
• Multipartite Nonlocality in Clifford Networks
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Normalizer Circuits and Quantum Computation
• Effectiveness of the syndrome extraction circuit with flag qubits on IBM quantum hardware
• Fast algorithms for classical specifications of stabiliser states and Clifford gates
• Transforming graph states via Bell state measurements
• Nonclassical correlations in subsystems of globally entangled quantum states
• Stabilizer states and local realism
• Tensor Rank and Other Multipartite Entanglement Measures of Graph States
• Entanglement of weighted graphs uncovers transitions in variable-range interacting models
• Clifford Manipulations of Stabilizer States: A graphical rule book for Clifford unitaries and measurements on cluster states, and application to photonic quantum computing
• On Classical Simulation of Quantum Circuits Composed of Clifford Gates
• Superconducting qubits in the millions: the potential and limitations of modularity
• Multipartite Greenberger-Horne-Zeilinger Entanglement in Monitored Random Clifford Circuits
• Minimally Universal Parity Quantum Computing
• On The Stabilizer Formalism And Its Generalization
• Characterization of non-adaptive Clifford channels
• Multipartite separability of density matrices of graphs
• QMC: A Model Checker for Quantum Systems
• Entanglement preservation in tripartite quantum systems under dephasing dynamics
• Faster manipulation of large quantum circuits using wire label reference diagrams
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• High-performance parallel classical scheme for simulating shallow quantum circuits
• A streamlined demonstration that stabilizer circuits simulation reduces to Boolean linear algebra
• Quantum Error Correction of Time-Correlated Errors
• Quantum Monte Carlo and Stabilizer States
• One-Way Quantum Computer Simulation
• Comparison of spin-qubit architectures for quantum error-correcting codes
• Simulating Special but Natural Quantum Circuits
• Clifford Gates in the Holant Framework