TR06-018 Authors: Jin-Yi Cai, Vinay Choudhary

Publication: 8th February 2006 06:02

Downloads: 1864

Keywords:

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.