ECCC-Report TR06-018https://eccc.weizmann.ac.il/report/2006/018Comments and Revisions published for TR06-018en-usWed, 08 Feb 2006 06:02:02 +0200
Paper TR06-018
| On the Theory of Matchgate Computations |
Jin-Yi Cai,
Vinay Choudhary
https://eccc.weizmann.ac.il/report/2006/018Valiant 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.
Wed, 08 Feb 2006 06:02:02 +0200https://eccc.weizmann.ac.il/report/2006/018