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:0802.2860 · Leibniz international proceedings in informatics

A Theory for Valiant's Matchcircuits (Extended Abstract)

Angsheng Li, Mingji Xia

Published Jan 1, 2008• 4 citations
arXivHTMLPDF

Abstract

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).

DOI
10.4230/lipics.stacs.2008.1368

Related papers

On the Theory of Matchgate Computations

Jin‐Yi Cai, Vinay Choudhary, Pinyan Lu

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.

Theory of Computing Systems•Jun 1, 2007•62 citations

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

Valiant’s Holant Theorem and Matchgate Tensors

Jin‐Yi Cai, Vinay Choudhary

Lecture notes in computer science•Jan 1, 2006•46 citations

On the construction of stabilizer codes with an arbitrary binary matrix

Yongsoo Hwang, Byung-Soo Choi, Moongu Jeon

Quantum Information Processing•Mar 23, 2012•1 citation

Contraction of matchgate tensor networks on non-planar graphs

Sergey B. Bravyi

A tensor network is a product of tensors associated with vertices of some graph $G$ such that every edge of $G$ represents a summation (contraction) over a matching pair of indexes. It was shown recently by Valiant, Cai, and Choudhary that tensor networks can be efficiently contracted on planar graphs if components of every tensor obey a system of quadratic equations known as matchgate identities. Such tensors are referred to as matchgate tensors. The present paper provides an alternative approach to contraction of matchgate tensor networks that easily extends to non-planar graphs. Specifically, it is shown that a matchgate tensor network on a graph $G$ of genus $g$ with $n$ vertices can be contracted in time $T=poly(n) + 2^{2g} O(m^3)$ where $m$ is the minimum number of edges one has to remove from $G$ in order to make it planar. Our approach makes use of anticommuting (Grassmann) variables and Gaussian integrals.

arXiv:0801.2989•Jan 18, 2008•1 citation

Some Results on Matchgates and Holographic Algorithms

Jin‐Yi Cai, Vinay Choudhary

Lecture notes in computer science•Jan 1, 2006•30 citations
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).
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.
A tensor network is a product of tensors associated with vertices of some graph GGG such that every edge of GGG represents a summation (contraction) over a matching pair of indexes. It was shown recently by Valiant, Cai, and Choudhary that tensor networks can be efficiently contracted on planar graphs if components of every tensor obey a system of quadratic equations known as matchgate identities. Such tensors are referred to as matchgate tensors. The present paper provides an alternative approach to contraction of matchgate tensor networks that easily extends to non-planar graphs. Specifically, it is shown that a matchgate tensor network on a graph GGG of genus ggg with nnn vertices can be contracted in time T=poly(n)+22gO(m3)T=poly(n) + 2^{2g} O(m^3)T=poly(n)+22gO(m3) where mmm is the minimum number of edges one has to remove from GGG in order to make it planar. Our approach makes use of anticommuting (Grassmann) variables and Gaussian integrals.