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:2407.19575

Bridging Classical and Quantum: Group-Theoretic Approach to Quantum Circuit Simulation

Daksh Shami

Published Jul 28, 2024• 1 citation
arXivHTMLPDF

Abstract

Efficiently simulating quantum circuits on classical computers is a fundamental challenge in quantum computing. This paper presents a novel theoretical approach that achieves substantial speedups over existing simulators for a wide class of quantum circuits. The technique leverages advanced group theory and symmetry considerations to map quantum circuits to equivalent forms amenable to efficient classical simulation. Several fundamental theorems are proven that establish the mathematical foundations of this approach, including a generalized Gottesman-Knill theorem. The potential of this method is demonstrated through theoretical analysis and preliminary benchmarks. This work contributes to the understanding of the boundary between classical and quantum computation, provides new tools for quantum circuit analysis and optimization, and opens up avenues for further research at the intersection of group theory and quantum computation. The findings may have implications for quantum algorithm design, error correction, and the development of more efficient quantum simulators.

DOI
10.48550/arxiv.2407.19575

Related papers

Lie-algebraic classical simulations for quantum computing

Matthew L. Goh, Martín Larocca, Łukasz Cincio +2 more

The classical simulation of quantum dynamics plays an important role in our understanding of quantum complexity and in the development of quantum technologies. Efficient techniques such as those based on the Gottesman-Knill theorem for Clifford circuits, tensor networks for low entanglement-generating circuits, or Wick's theorem for fermionic Gaussian states have become central tools in quantum computing. In this work, we contribute to this body of knowledge by presenting a framework for classical simulations, dubbed “ g -sim ”, which is based on the underlying Lie algebraic structure of the dynamical process. When the dimension of the algebra grows at most polynomially in the system size, there exist observables for which the simulation is efficient. Indeed, we show that g -sim enables new regimes for classical simulations, is able to deal with certain forms of noise in the evolution, as well as can be used to tackle several paradigmatic variational and nonvariational quantum computing tasks. For the former, we perform Lie-algebraic simulations to train and optimize parametrized quantum circuits (thus effectively showing that some variational models can be dequantized), design enhanced parameter initialization strategies, solve tasks of quantum circuit synthesis, and train a quantum-phase classifier. For the latter, we report large-scale noiseless and noisy simulations on benchmark problems. By comparing the limitations of g -sim and certain Wick's theorem-based simulations, we find that the two methods become inefficient for different types of states or observables, hinting at the existence of distinct, nonequivalent resources for classical simulation.

arXiv:2308.01432•Physical Review Research•Aug 22, 2025•111 citations

Generalized Clifford groups and simulation of associated quantum circuits

Stephen R. L. Clark, Richard Jozsa, Noah Linden

Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup $G$ of $U(d)$. In particular we seek $G$ such that $G\otimes G$ has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case $d = 2$ we exhaustively treat all finite irreducible subgroups of $U(2)$ and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the $n^{\rm th}$ root of $Z$ for $n \in \N$.

arXiv:quant-ph/0701103•Quantum Information and Computation•Jan 1, 2008•29 citations

On Classical Simulation of Quantum Circuits Composed of Clifford Gates

George Biswas

The Gottesman–Knill theorem asserts that quantum circuits composed solely of Clifford gates can be efficiently simulated classically. This theorem hinges on the fact that Clifford gates map Pauli strings to other Pauli strings, thereby allowing for a structured simulation process using classical computations. In this work, we break down the step-by-step procedure of the Gottesman–Knill theorem in a beginner-friendly manner, leveraging concepts such as matrix products, tensor products, commutation, anti-commutation, eigenvalues, and eigenvectors of quantum mechanical operators. Through detailed examples illustrating superposition and entanglement phenomena, we aim to provide a clear understanding of the classical simulation of Clifford gate-based quantum circuits. While we do not provide a formal proof of the theorem, we offer intuitive physical insights at each stage where necessary, empowering readers to grasp the fundamental principles underpinning this intriguing aspect of quantum computation. Quanta 2024; 13: 20–27.

arXiv:2405.13590•Quanta•Jul 29, 2024•6 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

The Stabilizer Formalism

The chapter covers a topic that has several uses—including, but not limited to, quantum error correction. We state and prove the Gottesman–Knill theorem, which says that quantum circuits over a certain limited gate set can be efficiently simulated by classical probabilistic computation. We also discuss stabilizer-based quantum error-correcting codes and provide some examples. Some background in group theory may be helpful for this chapter, but it is not required.

WORLD SCIENTIFIC eBooks•Aug 27, 2026•0 citations

Efficient classical simulations of quantum Fourier transforms and Normalizer circuits over Abelian groups

Maarten Van den Nest

The quantum Fourier transform (QFT) is an important ingredient in various quantum algorithms which achieve superpolynomial speed-ups over classical computers. In this paper we study under which conditions the QFT can be simulated efficiently classically. We introduce a class of quantum circuits, called \emph{normalizer circuits}: a normalizer circuit over a finite Abelian group is any quantum circuit comprising the QFT over the group, gates which compute automorphisms and gates which realize quadratic functions on the group. In our main result we prove that all normalizer circuits have polynomial-time classical simulations. The proof uses algorithms for linear diophantine equation solving and the monomial matrix formalism introduced in our earlier work. Our result generalizes the Gottesman-Knill theorem: in particular, Clifford circuits for $d$-level qudits arise as normalizer circuits over the group ${\mathbf Z}_d^m$. We also highlight connections between normalizer circuits and Shor's factoring algorithm, and the Abelian hidden subgroup problem in general. Finally we prove that quantum factoring cannot be realized as a normalizer circuit owing to its modular exponentiation subroutine.

arXiv:1201.4867•Quantum Information and Computation•Nov 1, 2013•33 citations
Efficiently simulating quantum circuits on classical computers is a fundamental challenge in quantum computing. This paper presents a novel theoretical approach that achieves substantial speedups over existing simulators for a wide class of quantum circuits. The technique leverages advanced group theory and symmetry considerations to map quantum circuits to equivalent forms amenable to efficient classical simulation. Several fundamental theorems are proven that establish the mathematical foundations of this approach, including a generalized Gottesman-Knill theorem. The potential of this method is demonstrated through theoretical analysis and preliminary benchmarks. This work contributes to the understanding of the boundary between classical and quantum computation, provides new tools for quantum circuit analysis and optimization, and opens up avenues for further research at the intersection of group theory and quantum computation. The findings may have implications for quantum algorithm design, error correction, and the development of more efficient quantum simulators.
The classical simulation of quantum dynamics plays an important role in our understanding of quantum complexity and in the development of quantum technologies. Efficient techniques such as those based on the Gottesman-Knill theorem for Clifford circuits, tensor networks for low entanglement-generating circuits, or Wick's theorem for fermionic Gaussian states have become central tools in quantum computing. In this work, we contribute to this body of knowledge by presenting a framework for classical simulations, dubbed “ g -sim ”, which is based on the underlying Lie algebraic structure of the dynamical process. When the dimension of the algebra grows at most polynomially in the system size, there exist observables for which the simulation is efficient. Indeed, we show that g -sim enables new regimes for classical simulations, is able to deal with certain forms of noise in the evolution, as well as can be used to tackle several paradigmatic variational and nonvariational quantum computing tasks. For the former, we perform Lie-algebraic simulations to train and optimize parametrized quantum circuits (thus effectively showing that some variational models can be dequantized), design enhanced parameter initialization strategies, solve tasks of quantum circuit synthesis, and train a quantum-phase classifier. For the latter, we report large-scale noiseless and noisy simulations on benchmark problems. By comparing the limitations of g -sim and certain Wick's theorem-based simulations, we find that the two methods become inefficient for different types of states or observables, hinting at the existence of distinct, nonequivalent resources for classical simulation.
Quantum computations starting with computational basis states and involving only Clifford operations, are classically simulable despite the fact that they generate highly entangled states; this is the content of the Gottesman-Knill theorem. Here we isolate the ingredients of the theorem and provide generalisations of some of them with the aim of identifying new classes of simulable quantum computations. In the usual construction, Clifford operations arise as projective normalisers of the first and second tensor powers of the Pauli group. We consider replacing the Pauli group by an arbitrary finite subgroup GGG of U(d)U(d)U(d). In particular we seek GGG such that G⊗GG\otimes GG⊗G has an entangling normaliser. Via a generalisation of the Gottesman-Knill theorem the resulting normalisers lead to classes of quantum circuits that can be classically efficiently simulated. For the qubit case d=2d = 2d=2 we exhaustively treat all finite irreducible subgroups of U(2)U(2)U(2) and find that the only ones (up to unitary equivalence and trivial phase extensions) with entangling normalisers are the groups generated by X and the nthn^{\rm th}nth root of ZZZ for n∈Nn \in \Nn∈N.
The Gottesman–Knill theorem asserts that quantum circuits composed solely of Clifford gates can be efficiently simulated classically. This theorem hinges on the fact that Clifford gates map Pauli strings to other Pauli strings, thereby allowing for a structured simulation process using classical computations. In this work, we break down the step-by-step procedure of the Gottesman–Knill theorem in a beginner-friendly manner, leveraging concepts such as matrix products, tensor products, commutation, anti-commutation, eigenvalues, and eigenvectors of quantum mechanical operators. Through detailed examples illustrating superposition and entanglement phenomena, we aim to provide a clear understanding of the classical simulation of Clifford gate-based quantum circuits. While we do not provide a formal proof of the theorem, we offer intuitive physical insights at each stage where necessary, empowering readers to grasp the fundamental principles underpinning this intriguing aspect of quantum computation. Quanta 2024; 13: 20–27.
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.
The quantum Fourier transform (QFT) is an important ingredient in various quantum algorithms which achieve superpolynomial speed-ups over classical computers. In this paper we study under which conditions the QFT can be simulated efficiently classically. We introduce a class of quantum circuits, called \emph{normalizer circuits}: a normalizer circuit over a finite Abelian group is any quantum circuit comprising the QFT over the group, gates which compute automorphisms and gates which realize quadratic functions on the group. In our main result we prove that all normalizer circuits have polynomial-time classical simulations. The proof uses algorithms for linear diophantine equation solving and the monomial matrix formalism introduced in our earlier work. Our result generalizes the Gottesman-Knill theorem: in particular, Clifford circuits for ddd-level qudits arise as normalizer circuits over the group Zdm{\mathbf Z}_d^mZdm​. We also highlight connections between normalizer circuits and Shor's factoring algorithm, and the Abelian hidden subgroup problem in general. Finally we prove that quantum factoring cannot be realized as a normalizer circuit owing to its modular exponentiation subroutine.