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

Clifford Simulation: Techniques and Applications

Alex Kerzner

Published May 28, 2021• 2 citations
OpenAlex

Abstract

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.

Related papers

Fast simulation of planar Clifford circuits

David Gosset, Daniel Grier, Alex Kerzner +1 more

A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as nω/2 < n1.19 which samples from the output distribution obtained by measuring all n qubits of a planar graph state in given Pauli bases. Here ω is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime.A key ingredient is a mapping which, given a tree decomposition of some graph G , produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise ntω−1 where t is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over F2 in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.

arXiv:2009.03218•Quantum•Feb 12, 2024•7 citations

Classical simulations of Abelian-group normalizer circuits with intermediate measurements

Juan Bermejo-Vega, Maarten Van den Nest

Quantum normalizer circuits were recently introduced as generalizations of Clifford circuits: a normalizer circuit over a finite Abelian group G is composed of the quantum Fourier transform (QFT) over G, together with gates which compute quadratic functions and automorphisms. In \cite{VDNest_12_QFTs} it was shown that every normalizer circuit can be simulated efficiently classically. This result provides a nontrivial example of a family of quantum circuits that cannot yield exponential speed-ups in spite of usage of the QFT, the latter being a central quantum algorithmic primitive. Here we extend the aforementioned result in several ways. Most importantly, we show that normalizer circuits supplemented with intermediate measurements can also be simulated efficiently classically, even when the computation proceeds adaptively. This yields a generalization of the Gottesman-Knill theorem (valid for n-qubit Clifford operations) to quantum circuits described by arbitrary finite Abelian groups. Moreover, our simulations are twofold: we present efficient classical algorithms to sample the measurement probability distribution of any adaptive-normalizer computation, as well as to compute the amplitudes of the state vector in every step of it. Finally we develop a generalization of the stabilizer formalism relative to arbitrary finite Abelian groups: for example we characterize how to update stabilizers under generalized Pauli measurements and provide a normal form of the amplitudes of generalized stabilizer states using quadratic functions and subgroup cosets.

arXiv:1210.3637•Quantum Information and Computation•Mar 1, 2014•29 citations

Classical simulations of quantum systems using stabilizer decompositions

Hammam Qassim

One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from $O(\\ell n^2)$ to $O(m n^2)$, where $\\ell$ is the total number of gates in the circuit, and $m$ is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever $\\ell \\gg m$. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of $\\ket{\\psi}^{\\otimes m}$, where $\\ket{\\psi}$ is either a magic state or an equatorial state. \nFor any single qubit magic state $\\ket{\\psi}$, we find stabilizer decompositions of $\\ket{\\psi}^{\\otimes m}$ with $2^{m\\log_2(3)/4}$ terms. This improves on the best known bound of $2^{m \\log_2(7)/6}$. \nSimilarly, for any single qubit equatorial state $\\ket{\\psi}$, we give a stabilizer decomposition of $\\ket{\\psi}^{\\otimes m}$ with $2^{m/2}$ terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail, $d$-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo $d > 2$. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd $d$, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even $d$ case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.

•Feb 19, 2021•4 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.

Quantum Information and Computation•Mar 1, 2010•82 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 #P-complete--thus showing that there is a separation between weak and strong classical simulation of quantum computation.

arXiv:0811.0898•Nov 6, 2008•31 citations

Simulation of quantum circuits by low-rank stabilizer decompositions

Sergey B. Bravyi, Dan E. Browne, Padraic Calpin +3 more

Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of \ns\nt\na\nb\ni\nl\ni\nz\ne\nr\n \nrank\n, which for a pure state \nψ\n is defined to be the smallest integer \nχ\n such that \nψ\n is a superposition of \nχ\n stabilizer states. Here we develop a comprehensive mathematical theory of the stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of \nχ\n∼\n10\n6\n stabilizer states and sample from the full \nn\n-bit output distribution, improving on previous simulations which used \n∼\n10\n3\n stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 \nT\n gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.

•Sep 2, 2019•223 citations
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.
A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as nω/2 < n1.19 which samples from the output distribution obtained by measuring all n qubits of a planar graph state in given Pauli bases. Here ω is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime.A key ingredient is a mapping which, given a tree decomposition of some graph G , produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise ntω−1 where t is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over F2 in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.
Quantum normalizer circuits were recently introduced as generalizations of Clifford circuits: a normalizer circuit over a finite Abelian group G is composed of the quantum Fourier transform (QFT) over G, together with gates which compute quadratic functions and automorphisms. In \cite{VDNest_12_QFTs} it was shown that every normalizer circuit can be simulated efficiently classically. This result provides a nontrivial example of a family of quantum circuits that cannot yield exponential speed-ups in spite of usage of the QFT, the latter being a central quantum algorithmic primitive. Here we extend the aforementioned result in several ways. Most importantly, we show that normalizer circuits supplemented with intermediate measurements can also be simulated efficiently classically, even when the computation proceeds adaptively. This yields a generalization of the Gottesman-Knill theorem (valid for n-qubit Clifford operations) to quantum circuits described by arbitrary finite Abelian groups. Moreover, our simulations are twofold: we present efficient classical algorithms to sample the measurement probability distribution of any adaptive-normalizer computation, as well as to compute the amplitudes of the state vector in every step of it. Finally we develop a generalization of the stabilizer formalism relative to arbitrary finite Abelian groups: for example we characterize how to update stabilizers under generalized Pauli measurements and provide a normal form of the amplitudes of generalized stabilizer states using quadratic functions and subgroup cosets.
One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states. \nIf the number of non-Clifford gates in the circuit is small, such simulations can be very effective. \nThis thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from O(elln2)O(\\ell n^2)O(elln2) to O(mn2)O(m n^2)O(mn2), where ell\\ellell is the total number of gates in the circuit, and mmm is the number of non-Clifford gates. \nSince this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever ellggm\\ell \\gg mellggm. \nOur method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources. \n \nFurthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of ketpsiotimesm\\ket{\\psi}^{\\otimes m}ketpsiotimesm, where ketpsi\\ket{\\psi}ketpsi is either a magic state or an equatorial state. \nFor any single qubit magic state ketpsi\\ket{\\psi}ketpsi, we find stabilizer decompositions of ketpsiotimesm\\ket{\\psi}^{\\otimes m}ketpsiotimesm with 2mlog2(3)/42^{m\\log_2(3)/4}2mlog2​(3)/4 terms. This improves on the best known bound of 2mlog2(7)/62^{m \\log_2(7)/6}2mlog2​(7)/6. \nSimilarly, for any single qubit equatorial state ketpsi\\ket{\\psi}ketpsi, we give a stabilizer decomposition of ketpsiotimesm\\ket{\\psi}^{\\otimes m}ketpsiotimesm with 2m/22^{m/2}2m/2 terms. \nTo our knowledge no such decompositions were previously known. \nThese results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way. \n \nWe also consider certain obstructions to classical simulations. \nIt has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits. \nLinear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits. \n \nWhile binary LCSs have been studied in detail, ddd-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo d>2d > 2d>2. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd ddd, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even ddd case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap.
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.
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-complete--thus showing that there is a separation between weak and strong classical simulation of quantum computation.
Recent work has explored using the stabilizer formalism to classically simulate quantum circuits containing a few non-Clifford gates. The computational cost of such methods is directly related to the notion of \ns\nt\na\nb\ni\nl\ni\nz\ne\nr\n \nrank\n, which for a pure state \nψ\n is defined to be the smallest integer \nχ\n such that \nψ\n is a superposition of \nχ\n stabilizer states. Here we develop a comprehensive mathematical theory of the stabilizer rank and the related approximate stabilizer rank. We also present a suite of classical simulation algorithms with broader applicability and significantly improved performance over the previous state-of-the-art. A new feature is the capability to simulate circuits composed of Clifford gates and arbitrary diagonal gates, extending the reach of a previous algorithm specialized to the Clifford+T gate set. We implemented the new simulation methods and used them to simulate quantum algorithms with 40-50 qubits and over 60 non-Clifford gates, without resorting to high-performance computers. We report a simulation of the Quantum Approximate Optimization Algorithm in which we process superpositions of \nχ\n∼\n10\n6\n stabilizer states and sample from the full \nn\n-bit output distribution, improving on previous simulations which used \n∼\n10\n3\n stabilizer states and sampled only from single-qubit marginals. We also simulated instances of the Hidden Shift algorithm with circuits including up to 64 \nT\n gates or 16 CCZ gates; these simulations showcase the performance gains available by optimizing the decomposition of a circuit's non-Clifford components.