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

Theory of Computing Systems

On the Theory of Matchgate Computations

Jin‐Yi Cai, Vinay Choudhary, Pinyan Lu

Published Jun 1, 2007• 62 citations
Publisher

Abstract

Valiant has proposed a new theory of algorithmic computation based on perfect matchings and Pfaffians. We study the properties of matchgates—the basic building blocks in this new theory. We give a set of algebraic identities which completely characterizes these objects for arbitrary numbers of inputs and outputs. These identities are derived from Grassmann-Plücker identities. The 4 by 4 matchgate character matrices are of particular interest. These were used in Valiant's classical simulation of a fragment of quantum computations. For these 4 by 4 matchgates, we use Jacobi's theorem on compound matrices to prove that the invertible matchgate matrices form a multiplicative group. Our results can also be expressed in the theory of Holographic Algorithms in terms of realizable standard signatures. These results are useful in establishing limitations on the ultimate capabilities of Valiant's theory of matchgate computations and Holographic Algorithms.

DOI
10.1007/s00224-007-9092-8

Related papers

Some Results on Matchgates and Holographic Algorithms.

Jin‐Yi Cai, Vinay Choudhary

We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit [14] and his signature theory of planar-matchgate/matchgrid [16], thus unifying the two theories in expressibility. In [5], we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl"ucker identities. With this correspondence, we give a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.

Electronic colloquium on computational complexity•Jan 1, 2006•1 citation

Holographic algorithms

Jin‐Yi Cai

Leslie Valiant recently proposed a theory of holographic algorithms. These novel algorithms achieve exponential speed-ups for certain computational problems compared to naive algorithms for the same problems. The methodology uses Pfaffians and (planar) perfect matchings as basic computational primitives, and attempts to create exponential cancellations in computation. In this article we survey this new theory of matchgate computations and holographic algorithms.

ACM SIGACT News•Jun 1, 2008•8 citations

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

Holographic algorithms

J.-Y. Cai

Leslie Valiant recently proposed a theory of holographic algorithms.These novel algorithms achieve exponential speed-ups for certain computational problems compared to naive algorithms for the same problems.The methodology uses Pfaffians and (planar) perfect matchings as basic computational primitives, and attempts to create exponential cancellations in computation.In this article we survey this new theory of matchgate computations and holographic algorithms.

Current Developments in Mathematics•Jan 1, 2005•3 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

A Theory for Valiant's Matchcircuits (Extended Abstract)

Angsheng Li, Mingji Xia

The computational function of a matchgate is represented by its character matrix. In this article, we show that all nonsingular character matrices are closed under matrix inverse operation, so that for every $k$, the nonsingular character matrices of $k$-bit matchgates form a group, extending the recent work of Cai and Choudhary (2006) of the same result for the case of $k=2$, and that the single and the two-bit matchgates are universal for matchcircuits, answering a question of Valiant (2002).

arXiv:0802.2860•Leibniz international proceedings in informatics•Jan 1, 2008•4 citations
Valiant has proposed a new theory of algorithmic computation based on perfect matchings and Pfaffians. We study the properties of matchgates—the basic building blocks in this new theory. We give a set of algebraic identities which completely characterizes these objects for arbitrary numbers of inputs and outputs. These identities are derived from Grassmann-Plücker identities. The 4 by 4 matchgate character matrices are of particular interest. These were used in Valiant's classical simulation of a fragment of quantum computations. For these 4 by 4 matchgates, we use Jacobi's theorem on compound matrices to prove that the invertible matchgate matrices form a multiplicative group. Our results can also be expressed in the theory of Holographic Algorithms in terms of realizable standard signatures. These results are useful in establishing limitations on the ultimate capabilities of Valiant's theory of matchgate computations and Holographic Algorithms.
We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit [14] and his signature theory of planar-matchgate/matchgrid [16], thus unifying the two theories in expressibility. In [5], we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl"ucker identities. With this correspondence, we give a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.
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.
The computational function of a matchgate is represented by its character matrix. In this article, we show that all nonsingular character matrices are closed under matrix inverse operation, so that for every kkk, the nonsingular character matrices of kkk-bit matchgates form a group, extending the recent work of Cai and Choudhary (2006) of the same result for the case of k=2k=2k=2, and that the single and the two-bit matchgates are universal for matchcircuits, answering a question of Valiant (2002).