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

Extending Matchgate Simulation Methods to Universal Quantum Circuits

Avinash Mocherla, Lingling Lao, Dan E. Browne

Published Feb 6, 2023• 25 citations
arXivHTMLPDF

Abstract

Matchgates are a family of parity-preserving two-qubit gates, nearest-neighbour circuits of which are known to be classically simulable in polynomial time. In this work, we present a simulation method to classically simulate an $\boldsymbol{n}$-qubit circuit containing $\boldsymbol{N}$ gates, $\boldsymbol{m}$ of which are universality-enabling gates and $\boldsymbol{N-m}$ of which are matchgates, in the setting of single-qubit Pauli measurements and product state inputs. The universality-enabling gates we consider include the SWAP, CZ, and CPhase gates. For fixed $\boldsymbol{m}$ as $\boldsymbol{n} \rightarrow \boldsymbol{\infty}$, the resource cost, $\boldsymbol{T}$, scales as $\boldsymbol{\mathcal{O}\left(\left(\frac{en}{m+1}\right)^{2m+2}\right)}$. For $\boldsymbol{m}$ scaling as a linear function of $\boldsymbol{n}$, however, $\boldsymbol{T}$ scale as $\boldsymbol{\mathcal{O}\left(2^{2nH\left(\frac{m+1}{n}\right)}\right)}$, where $\boldsymbol{H}(λ)$ is the binary entropy function.

DOI
10.48550/arxiv.2302.02654

Related papers

Extending matchgates into universal quantum computation

Daniel J. Brod, Ernesto F. Galvão

Matchgates are a family of two-qubit gates associated with noninteracting fermions. They are classically simulatable if acting only on nearest neighbors but become universal for quantum computation if we relax this restriction or use swap gates [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize this result by proving that any nonmatchgate parity-preserving unitary is capable of extending the computational power of matchgates into universal quantum computation. We identify the single local invariant of parity-preserving unitaries responsible for this, and discuss related results in the context of fermionic systems.

arXiv:1106.1863•Physical Review A•Aug 5, 2011•39 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

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

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•68 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•2 citations

Matchgate and space-bounded quantum computations are equivalent

Richard Jozsa, Barbara Kraus, Akimasa Miyake +1 more

Matchgates are an especially multiflorous class of two-qubit nearest-neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterize their power as coinciding with polynomial-time and logarithmic-space-bounded universal unitary quantum computation.

arXiv:0908.1467•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Nov 11, 2009•61 citations
Matchgates are a family of parity-preserving two-qubit gates, nearest-neighbour circuits of which are known to be classically simulable in polynomial time. In this work, we present a simulation method to classically simulate an n\boldsymbol{n}n-qubit circuit containing N\boldsymbol{N}N gates, m\boldsymbol{m}m of which are universality-enabling gates and N−m\boldsymbol{N-m}N−m of which are matchgates, in the setting of single-qubit Pauli measurements and product state inputs. The universality-enabling gates we consider include the SWAP, CZ, and CPhase gates. For fixed m\boldsymbol{m}m as n→∞\boldsymbol{n} \rightarrow \boldsymbol{\infty}n→∞, the resource cost, T\boldsymbol{T}T, scales as O((enm+1)2m+2)\boldsymbol{\mathcal{O}\left(\left(\frac{en}{m+1}\right)^{2m+2}\right)}O((m+1en​)2m+2). For m\boldsymbol{m}m scaling as a linear function of n\boldsymbol{n}n, however, T\boldsymbol{T}T scale as O(22nH(m+1n))\boldsymbol{\mathcal{O}\left(2^{2nH\left(\frac{m+1}{n}\right)}\right)}O(22nH(nm+1​)), where H(λ)\boldsymbol{H}(λ)H(λ) is the binary entropy function.
Matchgates are a family of two-qubit gates associated with noninteracting fermions. They are classically simulatable if acting only on nearest neighbors but become universal for quantum computation if we relax this restriction or use swap gates [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize this result by proving that any nonmatchgate parity-preserving unitary is capable of extending the computational power of matchgates into universal quantum computation. We identify the single local invariant of parity-preserving unitaries responsible for this, and discuss related results in the context of fermionic systems.
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.
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.
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.
Matchgates are an especially multiflorous class of two-qubit nearest-neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterize their power as coinciding with polynomial-time and logarithmic-space-bounded universal unitary quantum computation.