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:1305.6190 · Quantum Information and Computation

Classical simulation complexity of extended Clifford circuits

Richard Jozsa, M. Van den Nest

Published May 1, 2014• 97 citations
arXivHTMLPDF

Abstract

Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.

DOI
10.26421/qic14.7-8-7

Related papers

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 power of restricted quantum computational models

Mithuna Yoganathan

Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.

•Jan 5, 2021•1 citation

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

Further extensions of Clifford circuits and their classical simulation complexities

Dax Enshan Koh

Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations, which might just be slightly different, lead to circuits which are likely not. We extend the results of Jozsa and Van den Nest [Quant. Info. Comput. 14, 633 (2014)] by studying two further extensions of Clifford circuits. First, we consider how the classical simulation complexity changes when we allow for more general measurements. Second, we investigate different notions of what it means to ‘classically simulate’ a quantum circuit. These further extensions give us 24 new combinations of ingredients compared to Jozsa and Van den Nest, and we give a complete classification of their classical simulation complexities. Our results provide more examples where seemingly modest changes to the ingredients of Clifford circuits lead to “large” changes in the classical simulation complexities of the circuits, and also include new examples of extended Clifford circuits that exhibit “quantum supremacy”, in the sense that it is not possible to efficiently classically sample from the output distributions of such circuits, unless the polynomial hierarchy collapses.

arXiv:1512.07892•Quantum Information and Computation•Mar 1, 2017•32 citations

Embedding classical into quantum computation

Richard Jozsa

We describe a simple formalism for generating classes of quantum circuits that are classically efficiently simulatable and show that the efficient simulation of Clifford circuits (Gottesman-Knill theorem) and of matchgate circuits (Valiant's theorem) appear as two special cases. Viewing these simulatable classes as subsets of the space of all quantum computations, we may consider minimal extensions that suffice to regain full quantum computational power, which provides an approach to exploring the efficacy of quantum over classical computation.

arXiv:0812.4511•Dec 24, 2008•8 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
Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.
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.
Restricted models of quantum computation are ones that have less power than a universal quantum computer. We studied the consequences of removing particular properties from a universal quantum computer to discover whether those resources were important.In the first part of the thesis we studied universal quantum computers which are implemented using Clifford gates, adaptive measurements, and magic states. The Gottesman–Knill theorem shows that circuits in this form which do not use magic states can be simulated by a classical computer. We extended this result to show that all circuits in this form can be partially simulated; the same computation can be implemented using a smaller quantum computer with the assistance of some polynomial time classical computation. We also identified a subclass of these computations that can be shown to not be entirely classically simulated by any method, given certain complexity theoretic assumptions are true.In the next part of the thesis we examine the role of entanglement in noisy quantum computations. Entanglement is necessary for noiseless quantum computers to have any quantum advantage, but it is not known whether the same is true for mixed state quantum computers. We show that entanglement, unexpectedly, does play a crucial role in the most well known mixed state computer: the one clean qubit model.Finally, we investigate how closely classical simulation is related to another idea of classicality.This notion captures how easily the final state of a computation can be learnt, given samples of measurements from it. We find an extra condition under which a circuit that is classically simulable is also efficiently learnable.
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.
Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations, which might just be slightly different, lead to circuits which are likely not. We extend the results of Jozsa and Van den Nest [Quant. Info. Comput. 14, 633 (2014)] by studying two further extensions of Clifford circuits. First, we consider how the classical simulation complexity changes when we allow for more general measurements. Second, we investigate different notions of what it means to ‘classically simulate’ a quantum circuit. These further extensions give us 24 new combinations of ingredients compared to Jozsa and Van den Nest, and we give a complete classification of their classical simulation complexities. Our results provide more examples where seemingly modest changes to the ingredients of Clifford circuits lead to “large” changes in the classical simulation complexities of the circuits, and also include new examples of extended Clifford circuits that exhibit “quantum supremacy”, in the sense that it is not possible to efficiently classically sample from the output distributions of such circuits, unless the polynomial hierarchy collapses.
We describe a simple formalism for generating classes of quantum circuits that are classically efficiently simulatable and show that the efficient simulation of Clifford circuits (Gottesman-Knill theorem) and of matchgate circuits (Valiant's theorem) appear as two special cases. Viewing these simulatable classes as subsets of the space of all quantum computations, we may consider minimal extensions that suffice to regain full quantum computational power, which provides an approach to exploring the efficacy of quantum over classical computation.
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.