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.