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

Jordan-Wigner formalism for classical simulation beyond binary matchgates

Richard Jozsa, Akimasa Miyake

Published Nov 13, 2013• 3 citations
OpenAlex

Abstract

The unitary matchgate circuits introduced by Valiant provide an interesting class of quantum circuits that are classically efficiently simulatable. They were shown by Terhal & DiVincenzo and Knill to be related to the physics of non-interacting fermions. The Jordan-Wigner (JW) formalism provides an efficient classical simulation of the latter, which turns out to be equivalent to the restricted case of circuits of binary (2-qubit) matchgates. Valiant's formalism allows further unitary gates: in particular we may include arbitrary 1-qubit gates on the first qubit line at any stage within a binary matchgate circuit. In this note we show how the JW formalism may be extended to provide an efficient classical simulation of such extended circuits, and we show how the simulability also follows from some elementary Lie algebra theory. The essential ingredients have been indicated previously by Knill in a condensed and abstract form, and our purpose is to make these results explicit and transparent.

Related papers

Jordan-Wigner formalism for arbitrary 2-input 2-output matchgates and their classical simulation

Richard Jozsa, Akimasa Miyake, Sergii Strelchuk

In Valiant's matchgate theory, 2-input 2-output matchgates are $4\times 4$ matrices that satisfy ten so-called matchgate identities. We prove that the set of all such matchgates (including non-unitary and non-invertible ones) coincides with the topological closure of the set of all matrices obtained as exponentials of linear combinations of the 2-qubit Jordan-Wigner (JW) operators and their quadratic products, extending a previous result of Knill. In Valiant's theory, outputs of matchgate circuits can be classically computed in poly-time. Via the JW formalism, Terhal \& DiVincenzo and Knill established a relation of a unitary class of these circuits to the efficient simulation of non-interacting fermions. We describe how the JW formalism may be used to give an efficient simulation for all cases in Valiant's simulation theorem, which in particular includes the case of non-interacting fermions generalised to allow arbitrary 1-qubit gates on the first line at any stage in the circuit. Finally we give an exposition of how these simulation results can be alternatively understood from some basic Lie algebra theory, in terms of a formalism introduced by Somma et al.

arXiv:1311.3046•Quantum Information and Computation•May 1, 2015•10 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

•Jan 1, 2008•103 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•208 citations

Jordan-Wigner formalism for arbitrary 2-input 2-output matchgates and their classical simulation

JozsaRichard, MiyakeAkimasa, StrelchukSergii

In Valiant's matchgate theory, 2-input 2-output matchgates are 4 × 4 matrices that satisfy ten so-called matchgate identities. We prove that the set of all such matchgates (including non-unitary an...

Quantum Information and Computation•May 1, 2015•0 citations

Classical simulation of noninteracting-fermion quantum circuits

Barbara M. Terhal, David Peter Divincenzo

We show that a class of quantum computations that was recently shown to be efficiently simulatable on a classical computer by Valiant [in Proceedings of the 33rd ACM Symposium on the Theory of Computing (2001), p. 114] corresponds to a physical model of noninteracting fermions in one dimension. We give an alternative proof of his result using the language of fermions and extend the result to noninteracting fermions with arbitrary pairwise interactions, where gates can be conditioned on outcomes of complete von Neumann measurements in the computational basis on other fermionic modes in the circuit. This last result is in remarkable contrast with the case of noninteracting bosons where universal quantum computation can be achieved by allowing gates to be conditioned on classical bits [E. Knill, R. Laflamme, and G. Milburn, Nature (London) 409, 46 (2001)].

arXiv:quant-ph/0108010•Physical Review A•Mar 1, 2002•328 citations

Matchgate circuit representation of fermionic Gaussian states: optimal preparation, approximation, and classical simulation

Marc Langer, Raúl Morral-Yepes, Adam Gammon-Smith +2 more

Fermionic Gaussian states (FGSs) and the associated matchgate circuits play a central role in quantum information theory and condensed matter physics. Despite being possibly highly entangled, they can still be efficiently simulated on classical computers. We address the question of how to optimally create such states when using matchgate circuits acting on product states. To this end, we derive lower bounds on the number of gates required to prepare an arbitrary pure FGS: We establish both an asymptotic bound on the minimal gate count over general nearest-neighbor gate sets and an exact bound for circuits composed solely of matchgates. We present explicit algorithms whose constructions saturate these bounds, thereby proving their optimality. We furthermore determine when an FGS can be prepared with a circuit of any given depth, and derive an algorithm that constructs such a circuit whenever this condition is satisfied, either exactly or approximately. Our results have direct applications to (approximate) state preparation and to disentangling procedures. Moreover, we introduce a new classical simulation algorithm for matchgate circuits, based entirely on manipulating the generating circuits of the FGSs. Finally, we briefly study an extension of our framework for $t$-doped Gaussian states and circuits.

quant-pharXiv:2603.05675•Mar 9, 2026•0 citations
The unitary matchgate circuits introduced by Valiant provide an interesting class of quantum circuits that are classically efficiently simulatable. They were shown by Terhal & DiVincenzo and Knill to be related to the physics of non-interacting fermions. The Jordan-Wigner (JW) formalism provides an efficient classical simulation of the latter, which turns out to be equivalent to the restricted case of circuits of binary (2-qubit) matchgates. Valiant's formalism allows further unitary gates: in particular we may include arbitrary 1-qubit gates on the first qubit line at any stage within a binary matchgate circuit. In this note we show how the JW formalism may be extended to provide an efficient classical simulation of such extended circuits, and we show how the simulability also follows from some elementary Lie algebra theory. The essential ingredients have been indicated previously by Knill in a condensed and abstract form, and our purpose is to make these results explicit and transparent.
In Valiant's matchgate theory, 2-input 2-output matchgates are 4×44\times 44×4 matrices that satisfy ten so-called matchgate identities. We prove that the set of all such matchgates (including non-unitary and non-invertible ones) coincides with the topological closure of the set of all matrices obtained as exponentials of linear combinations of the 2-qubit Jordan-Wigner (JW) operators and their quadratic products, extending a previous result of Knill. In Valiant's theory, outputs of matchgate circuits can be classically computed in poly-time. Via the JW formalism, Terhal \& DiVincenzo and Knill established a relation of a unitary class of these circuits to the efficient simulation of non-interacting fermions. We describe how the JW formalism may be used to give an efficient simulation for all cases in Valiant's simulation theorem, which in particular includes the case of non-interacting fermions generalised to allow arbitrary 1-qubit gates on the first line at any stage in the circuit. Finally we give an exposition of how these simulation results can be alternatively understood from some basic Lie algebra theory, in terms of a formalism introduced by Somma et al.
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
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.
We show that a class of quantum computations that was recently shown to be efficiently simulatable on a classical computer by Valiant [in Proceedings of the 33rd ACM Symposium on the Theory of Computing (2001), p. 114] corresponds to a physical model of noninteracting fermions in one dimension. We give an alternative proof of his result using the language of fermions and extend the result to noninteracting fermions with arbitrary pairwise interactions, where gates can be conditioned on outcomes of complete von Neumann measurements in the computational basis on other fermionic modes in the circuit. This last result is in remarkable contrast with the case of noninteracting bosons where universal quantum computation can be achieved by allowing gates to be conditioned on classical bits [E. Knill, R. Laflamme, and G. Milburn, Nature (London) 409, 46 (2001)].
Fermionic Gaussian states (FGSs) and the associated matchgate circuits play a central role in quantum information theory and condensed matter physics. Despite being possibly highly entangled, they can still be efficiently simulated on classical computers. We address the question of how to optimally create such states when using matchgate circuits acting on product states. To this end, we derive lower bounds on the number of gates required to prepare an arbitrary pure FGS: We establish both an asymptotic bound on the minimal gate count over general nearest-neighbor gate sets and an exact bound for circuits composed solely of matchgates. We present explicit algorithms whose constructions saturate these bounds, thereby proving their optimality. We furthermore determine when an FGS can be prepared with a circuit of any given depth, and derive an algorithm that constructs such a circuit whenever this condition is satisfied, either exactly or approximately. Our results have direct applications to (approximate) state preparation and to disentangling procedures. Moreover, we introduce a new classical simulation algorithm for matchgate circuits, based entirely on manipulating the generating circuits of the FGSs. Finally, we briefly study an extension of our framework for ttt-doped Gaussian states and circuits.