A collapse theorem for holographic algorithms with matchgates on domain size at most 4

Holographic algorithms with matchgates are a novel approach to design polynomial time computation. They use Kasteleyn's algorithm for perfect matchings, and more importantly a holographic reduction. The two fundamental parameters of a holographic reduction are the domain size k of the underlying problem and the basis size ℓ  . A holographic reduction transforms the computation to matchgates by a linear transformation that maps to (a tensor product space of) a linear space of dimension 2ℓ2ℓ. We prove a sharp basis collapse theorem, which shows that for domain size 3 and 4, all non-trivial holographic reductions can be expressed with a basis of size 1 or 2, respectively. The main proof techniques are Matchgate Identities and a Group Property of matchgate signatures.