Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2504.14101 · Lobachevskii Journal of Mathematics

A Streamlined Demonstration That Stabilizer Circuits Simulation Reduces to Boolean Linear Algebra

V. I. Yashin

Published Jun 1, 2025• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1134/s1995080225607842

Related papers

Improved simulation of stabilizer circuits

Scott Aaronson, Daniel Gottesman

The Gottesman-Knill theorem says that a stabilizer circuit---that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates---can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely available program called CHP (CNOT-Hadamard-phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class $\ensuremath{\bigoplus}\mathsf{L}$, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any $n$-qubit stabilizer circuit into a ``canonical form'' that requires at most $O({n}^{2}∕\mathrm{log}\phantom{\rule{0.2em}{0ex}}n)$ gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.

arXiv:quant-ph/0406196•Physical Review A•Nov 30, 2004•1,846 citations

Further improvements to stabilizer simulation theory: classical rewriting of CSS-preserving stabilizer circuits, quadratic form expansions of stabilizer operations, and framed hidden variable models

Vsevolod I. Yashin, Vladimir V. Yatsulevich, Aleksey K. Fedorov +1 more

Simulation of stabilizer circuits is a well-studied problem in quantum information processing, with a number of highly optimized algorithms available. Yet, we argue that further improvements can arise from the theoretical structure of stabilizer operations themselves. We focus on the subclass of stabilizer circuits composed of Calderbank-Shor-Steane (CSS)-preserving stabilizer operations, which naturally appear in fault-tolerant computations over CSS stabilizer codes. Using elementary circuit transformation techniques, we show that such circuits can be exactly rewritten as classical probabilistic circuits that reproduce measurement statistics. This rewriting introduces no computational overhead, in contrast to the general case of stabilizer circuits. To clarify the origin of this simplification, we introduce the standard quadratic form representation of general stabilizer operations (Clifford channels). It provides an efficient way to describe compositions of stabilizer operations and thus to simulate stabilizer circuits. CSS-preserving operations correspond to purely linear forms, which under a Walsh-Hadamard-Fourier transform yield a noncontextual hidden variable model, providing an alternative proof of the introduced rewriting. Finally, we develop a theory of reference frames for multiqubit systems, where frames are encoded by quadratic forms. This allows us to express stabilizer operations as probabilistic maps for proper reference frames. Non-CSS-preserving stabilizer circuits require dynamical modifications of reference frames, embodying a contextuality resource that leads to the computational overhead. This framework provides a new perspective on simulating stabilizer and near-stabilizer circuits within dynamically evolving quasiprobability models.

quant-pharXiv:2511.05478•Nov 10, 2025•3 citations

Classical simulation of quantum computation, the gottesman-Knill theorem, and slightly beyond

M. Van den Nest

We study classical simulation of quantum computation, taking the Gottesman-Knill theorem as a starting point. We show how each Clifford circuit can be reduced to an equivalent, manifestly simulatable circuit (normal form). This provides a simple proof of the Gottesman-Knill theorem without resorting to stabilizer techniques. The normal form highlights why Clifford circuits have such limited computational power in spite of their high entangling power. At the same time, the normal form shows how the classical simulation of Clifford circuits fits into the standard way of embedding classical computation into the quantum circuit model. This leads to simple extensions of Clifford circuits which are classically simulatable. These circuits can be efficiently simulated by classical sampling (``weak simulation'') even though the problem of exactly computing the outcomes of measurements for these circuits (``strong simulation'') is proved to be $\#\mathbf{P}$-complete---thus showing that there is a separation between weak and strong classical simulation of quantum computation.

arXiv:0811.0898•Quantum Information and Computation•Mar 1, 2010•169 citations

Clifford Simulation: Techniques and Applications

Alex Kerzner

Despite the widespread belief that quantum computers cannot be efficiently simulated classically, efficient simulation is known to be possible in certain restricted regimes. In particular, the Gottesman-Knill theorem states that Clifford circuits can be efficiently simulated. We begin this thesis by reviewing and comparing several known techniques for efficient simulation of Clifford circuits: the stabilizer formalism, CH form, affine form, and the graph state formalism. We describe each simulation method and give four different proofs of the Gottesman-Knill theorem. \n \nNext we review a recent work [15], which shows that restricting the geometry of Clifford circuits can lead to a further speedup. We give an algorithm for simulating Pauli basis measurements on a planar graph state in time $\\widetilde{O}(n^{\\omega/2})$, where $\\omega < 2.373$ is the matrix multiplication exponent. This algorithm achieves a quadratic speedup over using Clifford simulation methods directly. As an application of this algorithm, we consider a depth-$d$ Clifford circuit whose two-qubit gates act along edges of a planar graph and describe how to sample from its output distribution or compute an output probability in time $\\widetilde{O}(n^{\\omega/2}d^\\omega)$. For $d= O(\\log n)$, both of these results are quadratic speedups over using Clifford simulation methods directly. \n \nFinally, we extend these simulation algorithms to universal circuits by using stabilizer rank methods. We follow a previously known gadgetization procedure [9] to show that given a depth-$d$ Clifford+$T$ circuit with $t$ $T$ gates and whose two-qubit gates act along edges of a planar graph, we can sample from its output distribution in time $\\widetilde{O}(2^{0.7926t}n^{5/2}t^{6} d^3)$ and can compute output probabilities in time $\\widetilde{O}(2^{0.3963t}n^{3/2}t^{6} d^3)$. Previous work [9,6], applied to the case $d=O(\\log n)$, gives algorithms for sampling in time $O(2^{0.3963t} n^6 t^6)$ and computation of output probabilities in time $O(2^{0.3963t}n^3t^3)$. Our sampling algorithm offers improved scaling in $n$ but poorer scaling in the exponential term, while our algorithm for computing output probabilities offers improved scaling in $n$ with identical scaling in the exponential term.

•May 28, 2021•2 citations

QuickQudits: A Framework for Efficient Simulation of Noisy Qudit Clifford Circuits via an Extended Stabilizer Tableau Formalism

Nina Brandl, Mykyta Cherniak, Johannes Kofler +1 more

We present a comprehensive and self-contained framework for the efficient classical simulation of Clifford circuits acting on $d$-dimensional qudits, including realistic Pauli/Weyl noise via stochastic simulation. Our approach uses the stabilizer tableau formalism for qudits of arbitrary dimension and tracks both stabilizer and destabilizer generators under Clifford updates. The classical simulation remains efficient with simple algebraic Clifford update rules over $\mathbb{Z}_d$. Computational basis measurements in prime dimensions are handled by a generalized Aaronson-Gottesman (CHP) procedure. In composite dimensions, $\mathbb{Z}_d$ is not a field and the standard tableau reduction fails, so we employ an exact Smith normal form decomposition to enable efficient sampling. Noise is modelled as probabilistic mixtures of Weyl operators that act only on the tableau's phase column. For fast simulation of noisy circuits, we support Pauli frames, respectively generalized Weyl frames, and introduce a noise-pushing technique that allows all noise processes to be consolidated into a single phase update at the end of the circuit. Using this representation, circuit fidelity can be determined entirely by the single accumulated phase-shift parameter $Δτ$, reducing fidelity estimation to a simple phase check per shot. Our codebase supports tableau simulation and conventional state-vector and density-matrix backends for qudits, and also includes circuit and tableau visualisations. Additionally, we provide tests and Jupyter notebooks for validation and illustration. This framework forms the basis for a scalable, open-source strong+weak stabilizer simulator including noise and can be found publicly available at https://github.com/QUICK-JKU/QuickQudits.

quant-pharXiv:2603.23641•Mar 26, 2026•5 citations

Stabilizer Tensor Networks: Universal Quantum Simulator on a Basis of Stabilizer States

Sergi Masot-Llima, Artur García-Sáez

Efficient simulation of quantum computers relies on understanding and exploiting the properties of quantum states. This is the case for methods such as tensor networks, based on entanglement, and the tableau formalism, which represents stabilizer states. In this Letter, we integrate these two approaches to present a generalization of the tableau formalism used for Clifford circuit simulation. We explicitly prove how to update our formalism with Clifford gates, non-Clifford gates, and measurements, enabling universal circuit simulation. We also discuss how the framework allows for efficient simulation of more states, raising some interesting questions on the representation power of tensor networks and the quantum properties of resources such as entanglement and magic, and support our claims with simulations.

arXiv:2403.08724•Physical Review Letters•Dec 3, 2024•63 citations
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.
The Gottesman-Knill theorem says that a stabilizer circuit---that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates---can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely available program called CHP (CNOT-Hadamard-phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class $\ensuremath{\bigoplus}\mathsf{L}$, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any nnn-qubit stabilizer circuit into a ``canonical form'' that requires at most O(n2∕logn)O({n}^{2}∕\mathrm{log}\phantom{\rule{0.2em}{0ex}}n)O(n2∕logn) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.
Simulation of stabilizer circuits is a well-studied problem in quantum information processing, with a number of highly optimized algorithms available. Yet, we argue that further improvements can arise from the theoretical structure of stabilizer operations themselves. We focus on the subclass of stabilizer circuits composed of Calderbank-Shor-Steane (CSS)-preserving stabilizer operations, which naturally appear in fault-tolerant computations over CSS stabilizer codes. Using elementary circuit transformation techniques, we show that such circuits can be exactly rewritten as classical probabilistic circuits that reproduce measurement statistics. This rewriting introduces no computational overhead, in contrast to the general case of stabilizer circuits. To clarify the origin of this simplification, we introduce the standard quadratic form representation of general stabilizer operations (Clifford channels). It provides an efficient way to describe compositions of stabilizer operations and thus to simulate stabilizer circuits. CSS-preserving operations correspond to purely linear forms, which under a Walsh-Hadamard-Fourier transform yield a noncontextual hidden variable model, providing an alternative proof of the introduced rewriting. Finally, we develop a theory of reference frames for multiqubit systems, where frames are encoded by quadratic forms. This allows us to express stabilizer operations as probabilistic maps for proper reference frames. Non-CSS-preserving stabilizer circuits require dynamical modifications of reference frames, embodying a contextuality resource that leads to the computational overhead. This framework provides a new perspective on simulating stabilizer and near-stabilizer circuits within dynamically evolving quasiprobability models.
We study classical simulation of quantum computation, taking the Gottesman-Knill theorem as a starting point. We show how each Clifford circuit can be reduced to an equivalent, manifestly simulatable circuit (normal form). This provides a simple proof of the Gottesman-Knill theorem without resorting to stabilizer techniques. The normal form highlights why Clifford circuits have such limited computational power in spite of their high entangling power. At the same time, the normal form shows how the classical simulation of Clifford circuits fits into the standard way of embedding classical computation into the quantum circuit model. This leads to simple extensions of Clifford circuits which are classically simulatable. These circuits can be efficiently simulated by classical sampling (``weak simulation'') even though the problem of exactly computing the outcomes of measurements for these circuits (``strong simulation'') is proved to be #P\#\mathbf{P}#P-complete---thus showing that there is a separation between weak and strong classical simulation of quantum computation.
Despite the widespread belief that quantum computers cannot be efficiently simulated classically, efficient simulation is known to be possible in certain restricted regimes. In particular, the Gottesman-Knill theorem states that Clifford circuits can be efficiently simulated. We begin this thesis by reviewing and comparing several known techniques for efficient simulation of Clifford circuits: the stabilizer formalism, CH form, affine form, and the graph state formalism. We describe each simulation method and give four different proofs of the Gottesman-Knill theorem. \n \nNext we review a recent work [15], which shows that restricting the geometry of Clifford circuits can lead to a further speedup. We give an algorithm for simulating Pauli basis measurements on a planar graph state in time widetildeO(nomega/2)\\widetilde{O}(n^{\\omega/2})widetildeO(nomega/2), where omega<2.373\\omega < 2.373omega<2.373 is the matrix multiplication exponent. This algorithm achieves a quadratic speedup over using Clifford simulation methods directly. As an application of this algorithm, we consider a depth-ddd Clifford circuit whose two-qubit gates act along edges of a planar graph and describe how to sample from its output distribution or compute an output probability in time $\\widetilde{O}(n^{\\omega/2}d^\\omega)$. For d=O(logn)d= O(\\log n)d=O(logn), both of these results are quadratic speedups over using Clifford simulation methods directly. \n \nFinally, we extend these simulation algorithms to universal circuits by using stabilizer rank methods. We follow a previously known gadgetization procedure [9] to show that given a depth-ddd Clifford+TTT circuit with ttt TTT gates and whose two-qubit gates act along edges of a planar graph, we can sample from its output distribution in time widetildeO(20.7926tn5/2t6d3)\\widetilde{O}(2^{0.7926t}n^{5/2}t^{6} d^3)widetildeO(20.7926tn5/2t6d3) and can compute output probabilities in time widetildeO(20.3963tn3/2t6d3)\\widetilde{O}(2^{0.3963t}n^{3/2}t^{6} d^3)widetildeO(20.3963tn3/2t6d3). Previous work [9,6], applied to the case d=O(logn)d=O(\\log n)d=O(logn), gives algorithms for sampling in time O(20.3963tn6t6)O(2^{0.3963t} n^6 t^6)O(20.3963tn6t6) and computation of output probabilities in time O(20.3963tn3t3)O(2^{0.3963t}n^3t^3)O(20.3963tn3t3). Our sampling algorithm offers improved scaling in nnn but poorer scaling in the exponential term, while our algorithm for computing output probabilities offers improved scaling in nnn with identical scaling in the exponential term.
We present a comprehensive and self-contained framework for the efficient classical simulation of Clifford circuits acting on ddd-dimensional qudits, including realistic Pauli/Weyl noise via stochastic simulation. Our approach uses the stabilizer tableau formalism for qudits of arbitrary dimension and tracks both stabilizer and destabilizer generators under Clifford updates. The classical simulation remains efficient with simple algebraic Clifford update rules over Zd\mathbb{Z}_dZd​. Computational basis measurements in prime dimensions are handled by a generalized Aaronson-Gottesman (CHP) procedure. In composite dimensions, Zd\mathbb{Z}_dZd​ is not a field and the standard tableau reduction fails, so we employ an exact Smith normal form decomposition to enable efficient sampling. Noise is modelled as probabilistic mixtures of Weyl operators that act only on the tableau's phase column. For fast simulation of noisy circuits, we support Pauli frames, respectively generalized Weyl frames, and introduce a noise-pushing technique that allows all noise processes to be consolidated into a single phase update at the end of the circuit. Using this representation, circuit fidelity can be determined entirely by the single accumulated phase-shift parameter ΔτΔτΔτ, reducing fidelity estimation to a simple phase check per shot. Our codebase supports tableau simulation and conventional state-vector and density-matrix backends for qudits, and also includes circuit and tableau visualisations. Additionally, we provide tests and Jupyter notebooks for validation and illustration. This framework forms the basis for a scalable, open-source strong+weak stabilizer simulator including noise and can be found publicly available at https://github.com/QUICK-JKU/QuickQudits.
Efficient simulation of quantum computers relies on understanding and exploiting the properties of quantum states. This is the case for methods such as tensor networks, based on entanglement, and the tableau formalism, which represents stabilizer states. In this Letter, we integrate these two approaches to present a generalization of the tableau formalism used for Clifford circuit simulation. We explicitly prove how to update our formalism with Clifford gates, non-Clifford gates, and measurements, enabling universal circuit simulation. We also discuss how the framework allows for efficient simulation of more states, raising some interesting questions on the representation power of tensor networks and the quantum properties of resources such as entanglement and magic, and support our claims with simulations.