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:quant-ph/0108033

Fermionic Linear Optics and Matchgates

Emanuel H. Knill

Published Aug 7, 2001• 73 citations
arXivHTMLPDF

Abstract

Fermionic linear optics is efficiently classically simulatable. Here it is shown that the set of states achievable with fermionic linear optics and particle measurements is the closure of a low dimensional Lie group. The weakness of fermionic linear optics and measurements can therefore be explained and contrasted with the strength of bosonic linear optics with particle measurements. An analysis of fermionic linear optics is used to show that the two-qubit matchgates and the simulatable matchcircuits introduced by Valiant generate a monoid of extended fermionic linear optics operators. A useful interpretation of efficient classical simulations such as this one is as a simulation of a model of non-deterministic quantum computation. Problem areas for future investigations are suggested.

DOI
10.48550/arxiv.quant-ph/0108033

Related papers

Jordan-Wigner formalism for classical simulation beyond binary matchgates

Richard Jozsa, Akimasa Miyake

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.

•Nov 13, 2013•3 citations

Efficient classical simulation of matchgate circuits with generalized inputs and measurements

Daniel J. Brod

Matchgates are a restricted set of two-qubit gates known to be classically simulable under particular conditions. Specifically, if a circuit consists only of nearest-neighbor matchgates, an efficient classical simulation is possible if either (i) the input is a computational-basis state and the simulation requires computing probabilities of multiqubit outcomes (including also adaptive measurements) or (ii) if the input is an arbitrary product state, but the output of the circuit consists of a single qubit. In this paper we extend these results to show that matchgates are classically simulable even in the most general combination of these settings, namely, if the inputs are arbitrary product states, if the measurements are over arbitrarily many output qubits, and if adaptive measurements are allowed. This remains true even for arbitrary single-qubit measurements, albeit only in a weaker notion of classical simulation. These results make for an interesting contrast with other restricted models of computation, such as Clifford circuits or (bosonic) linear optics, where the complexity of simulation varies greatly under similar modifications.

arXiv:1602.03539•Physical Review A•Jun 23, 2016•61 citations

Classical simulation of dissipative fermionic linear optics

Sergey B. Bravyi, Robert König

Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$ fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$. The steady state of the Lindblad equation can be computed in time $O(N^3)$.

arXiv:1112.2184•Dec 9, 2011•4 citations

Learning Gaussian Operations and the Matchgate Hierarchy

Josh Cudby, Sergii Strelchuk

Learning an unknown quantum process is a central task for validation of the functioning of near-term devices. The task is generally hard, requiring exponentially many measurements if no prior assumptions are made on the process. However, an interesting feature of the classically-simulable Clifford group is that unknown Clif-ford operations may be efficiently determined from a black-box implementation. We extend this result to the important class of fermionic Gaussian operations. These operations have received much attention due to their close links to fermionic linear optics. We then introduce an infinite family of unitary gates, called the Matchgate Hierarchy, with a similar structure to the Clifford Hierarchy. We show that the Clifford Hierarchy is contained within the Matchgate Hierarchy and how operations at any level of the hierarchy can be efficiently learned.

arXiv:2407.12649•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Classical simulation of dissipative fermionic linear optics

Sergey B. Bravyi, Robert König

Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of $N$~fermionic modes, our algorithm simulates any such gate in time $O(N^3)$ while a single-mode measurement is simulated in time $O(N^2)$. The steady state of the Lindblad equation can be computed in time $O(N^3)$.

Quantum Information and Computation•Nov 1, 2012•22 citations

The Computational Power of Non-interacting Particles

Daniel J. Brod

Shortened abstract: In this thesis, I study two restricted models of quantum computing related to free identical particles. Free fermions correspond to a set of two-qubit gates known as matchgates. Matchgates are classically simulable when acting on nearest neighbors on a path, but universal for quantum computing when acting on distant qubits or when SWAP gates are available. I generalize these results in two ways. First, I show that SWAP is only one in a large family of gates that uplift matchgates to quantum universality. In fact, I show that the set of all matchgates plus any nonmatchgate parity-preserving two-qubit gate is universal, and interpret this fact in terms of local invariants of two-qubit gates. Second, I investigate the power of matchgates in arbitrary connectivity graphs, showing they are universal on any connected graph other than a path or a cycle, and classically simulable on a cycle. I also prove the same dichotomy for the XY interaction. Free bosons give rise to a model known as BosonSampling. BosonSampling consists of (i) preparing a Fock state of n photons, (ii) interfering these photons in an m-mode linear interferometer, and (iii) measuring the output in the Fock basis. Sampling approximately from the resulting distribution should be classically hard, under reasonable complexity assumptions. Here I show that exact BosonSampling remains hard even if the linear-optical circuit has constant depth. I also report several experiments where three-photon interference was observed in integrated interferometers of various sizes, providing some of the first implementations of BosonSampling in this regime. The experiments also focus on the bosonic bunching behavior and on validation of BosonSampling devices. This thesis contains descriptions of the numerical analyses done on the experimental data, omitted from the corresponding publications.

arXiv:1412.7637•Dec 24, 2014•0 citations
Fermionic linear optics is efficiently classically simulatable. Here it is shown that the set of states achievable with fermionic linear optics and particle measurements is the closure of a low dimensional Lie group. The weakness of fermionic linear optics and measurements can therefore be explained and contrasted with the strength of bosonic linear optics with particle measurements. An analysis of fermionic linear optics is used to show that the two-qubit matchgates and the simulatable matchcircuits introduced by Valiant generate a monoid of extended fermionic linear optics operators. A useful interpretation of efficient classical simulations such as this one is as a simulation of a model of non-deterministic quantum computation. Problem areas for future investigations are suggested.
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.
Matchgates are a restricted set of two-qubit gates known to be classically simulable under particular conditions. Specifically, if a circuit consists only of nearest-neighbor matchgates, an efficient classical simulation is possible if either (i) the input is a computational-basis state and the simulation requires computing probabilities of multiqubit outcomes (including also adaptive measurements) or (ii) if the input is an arbitrary product state, but the output of the circuit consists of a single qubit. In this paper we extend these results to show that matchgates are classically simulable even in the most general combination of these settings, namely, if the inputs are arbitrary product states, if the measurements are over arbitrarily many output qubits, and if adaptive measurements are allowed. This remains true even for arbitrary single-qubit measurements, albeit only in a weaker notion of classical simulation. These results make for an interesting contrast with other restricted models of computation, such as Clifford circuits or (bosonic) linear optics, where the complexity of simulation varies greatly under similar modifications.
Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of NNN fermionic modes, our algorithm simulates any such gate in time O(N3)O(N^3)O(N3) while a single-mode measurement is simulated in time O(N2)O(N^2)O(N2). The steady state of the Lindblad equation can be computed in time O(N3)O(N^3)O(N3).
Learning an unknown quantum process is a central task for validation of the functioning of near-term devices. The task is generally hard, requiring exponentially many measurements if no prior assumptions are made on the process. However, an interesting feature of the classically-simulable Clifford group is that unknown Clif-ford operations may be efficiently determined from a black-box implementation. We extend this result to the important class of fermionic Gaussian operations. These operations have received much attention due to their close links to fermionic linear optics. We then introduce an infinite family of unitary gates, called the Matchgate Hierarchy, with a similar structure to the Clifford Hierarchy. We show that the Clifford Hierarchy is contained within the Matchgate Hierarchy and how operations at any level of the hierarchy can be efficiently learned.
Fermionic linear optics is a limited form of quantum computation which is known to be efficiently simulable on a classical computer. We revisit and extend this result by enlarging the set of available computational gates: in addition to unitaries and measurements, we allow dissipative evolution governed by a Markovian master equation with linear Lindblad operators. We show that this more general form of fermionic computation is also simulable efficiently by classical means. Given a system of NNN~fermionic modes, our algorithm simulates any such gate in time O(N3)O(N^3)O(N3) while a single-mode measurement is simulated in time O(N2)O(N^2)O(N2). The steady state of the Lindblad equation can be computed in time O(N3)O(N^3)O(N3).
Shortened abstract: In this thesis, I study two restricted models of quantum computing related to free identical particles. Free fermions correspond to a set of two-qubit gates known as matchgates. Matchgates are classically simulable when acting on nearest neighbors on a path, but universal for quantum computing when acting on distant qubits or when SWAP gates are available. I generalize these results in two ways. First, I show that SWAP is only one in a large family of gates that uplift matchgates to quantum universality. In fact, I show that the set of all matchgates plus any nonmatchgate parity-preserving two-qubit gate is universal, and interpret this fact in terms of local invariants of two-qubit gates. Second, I investigate the power of matchgates in arbitrary connectivity graphs, showing they are universal on any connected graph other than a path or a cycle, and classically simulable on a cycle. I also prove the same dichotomy for the XY interaction. Free bosons give rise to a model known as BosonSampling. BosonSampling consists of (i) preparing a Fock state of n photons, (ii) interfering these photons in an m-mode linear interferometer, and (iii) measuring the output in the Fock basis. Sampling approximately from the resulting distribution should be classically hard, under reasonable complexity assumptions. Here I show that exact BosonSampling remains hard even if the linear-optical circuit has constant depth. I also report several experiments where three-photon interference was observed in integrated interferometers of various sizes, providing some of the first implementations of BosonSampling in this regime. The experiments also focus on the bosonic bunching behavior and on validation of BosonSampling devices. This thesis contains descriptions of the numerical analyses done on the experimental data, omitted from the corresponding publications.