Some results on matchcircuit computations and holographic algorithms

Recently Valiant has initiated a new theory of matchcircuit computations
and holographic algorithms.  This theory attempts to encode and
perform computations using perfect matchings and the Pfaffian.
In holographic algorithms, a new ingredient was added, namely
a choice of a set of linear basis vectors, in terms of which
the computation can be expressed and interpreted.
The matchcircuit theory is based on general matchgates, for which
one associates a character matrix. For holographic algorithms,
one only considers planar matchgates, each is assigned a signature
matrix, and computation is performed
through the Fisher-Kasteleyn-Temperley method.  With matchcircuit Valiant
has shown a non-trivial fragment of quantum computation can be simulated
in polynomial time.  With holographic algorithms, a number of
combinatorial problems were shown to be in P for the first time.

In this talk we report some new results, among which

(1) A new framework for the matchgate character theory based
  on contravariant and covariant tensors, leading to a natural proof of the
  Holant Theorem.

(2) A complete set of matchgate identities based on a set of
 "useful" Grassmann-Pl{\"u}cker identities.  Some group actions and
 symmetries.

(3) A unification of the theories of matchcircuit and
 planar matchgrid computation.

(4) Some further problems solved in P for the first time.

(5) Some impossibility results.