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

Embedding classical into quantum computation

Richard Jozsa

Published Dec 24, 2008• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0812.4511

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

Classical simulation complexity of extended Clifford circuits

Richard Jozsa, M. Van den Nest

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.

arXiv:1305.6190•Quantum Information and Computation•May 1, 2014•97 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

Matchgates and classical simulation of quantum circuits

Richard Jozsa, Akimasa Miyake

Let G ( A , B ) denote the two-qubit gate that acts as the one-qubit SU (2) gates A and B in the even and odd parity subspaces, respectively, of two qubits. Using a Clifford algebra formalism, we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allow the same gates to act only on n.n. and next n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan–Wigner representation of a Clifford algebra, we show how one may generalize the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits.

arXiv:0804.4050•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jul 22, 2008•260 citations

Matchgates and classical simulation of quantum circuits

Richard Jozsa, Akimasa Miyake, ,

Let G(A, B) denote the 2-qubit gate which acts as the 1-qubit SU(2) gates A and B in the even and odd parity subspaces respectively, of two qubits. Using a Clifford algebra formalism we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allowing the same gates to act only on n.n. and next-n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan-Wigner representation of a Clifford algebra, we show how one may generalise the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits. 1

•Dec 8, 2008•114 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
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.
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.
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.
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.
Let G ( A , B ) denote the two-qubit gate that acts as the one-qubit SU (2) gates A and B in the even and odd parity subspaces, respectively, of two qubits. Using a Clifford algebra formalism, we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allow the same gates to act only on n.n. and next n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan–Wigner representation of a Clifford algebra, we show how one may generalize the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits.
Let G(A, B) denote the 2-qubit gate which acts as the 1-qubit SU(2) gates A and B in the even and odd parity subspaces respectively, of two qubits. Using a Clifford algebra formalism we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allowing the same gates to act only on n.n. and next-n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan-Wigner representation of a Clifford algebra, we show how one may generalise the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits. 1
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.