Theory of Computing
-------------------
Title : Matchgates Revisited
Authors : Jin-Yi Cai and Aaron Gorenstein
Volume : 10
Number : 7
Pages : 167-197
URL : https://theoryofcomputing.org/articles/v010a007
Abstract
--------
We study a collection of concepts and theorems that laid the
foundation of matchgate computation. This includes the signature
theory of planar matchgates, and the parallel theory of characters of
not necessarily planar matchgates. Our aim is to present a unified
and, whenever possible, simplified account of this challenging theory.
Our results include: (1) A direct proof that the Matchgate Identities
(MGI) are necessary and sufficient conditions for matchgate
signatures. This proof is self-contained and does not go through the
character theory. (2) A proof that the MGI already imply the Parity
Condition. (3) A simplified construction of a crossover gadget. This
is used in the proof of sufficiency of the MGI for matchgate
signatures. This is also used to give a proof of equivalence between
the signature theory and the character theory which permits omittable
nodes. (4) A direct construction of matchgates realizing all
matchgate-realizable symmetric signatures.