Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-018 | 8th February 2006 00:00

#### On the Theory of Matchgate Computations

TR06-018
Authors: Jin-Yi Cai, Vinay Choudhary
Publication: 8th February 2006 06:02
Keywords:

Abstract:

Valiant has proposed a new theory of algorithmic
computation based on perfect matchings and the Pfaffian.
We study the properties of {\it matchgates}---the basic
building blocks in this new theory. We give a set of
algebraic identities
which completely characterize these objects in terms of
the Grassmann-Pl{\"u}cker identities.
In the important case of 4 by 4 matchgate matrices,
which was used in Valiant's classical simulation of a
fragment of quantum computations, we further realize a
group action on the character matrix of a matchgate, and
relate this information to its compound matrix. Then we use
Jacobi's theorem to prove that in this case the invertible
matchgate matrices form a multiplicative group. These results
are useful in establishing limitations on the ultimate
capabilities of Valiant's theory of matchgate computations and
his closely related theory of Holographic Algorithms.

ISSN 1433-8092 | Imprint