Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-018 | 8th February 2006 00:00

On the Theory of Matchgate Computations


Authors: Jin-Yi Cai, Vinay Choudhary
Publication: 8th February 2006 06:02
Downloads: 3354


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