Holographic algorithms without matchgates

Combinatorial (weighted) counting problems, such as counting the
number of satisfying assignments of a Boolean satisfiability problem
or computing the partition function of a graphical model, can be
expressed as tensor contractions diagrammed by a bipartite graph
$\Gamma=(V,U,E)$. Many algorithms for solving these problems
efficiently use tree structure and factorization over a semiring (the
"sum-product algorithm" ). Over a proper ring, cancellation can be
exploited as well. This requires a change of basis so that certain
algebraic conditions are locally satisfied, and the addition of
orientation or ordering information. Recently, this Pfaffian-based
approach has been used by Valiant and Cai to provide unexpected,
polynomial-time "accidental" algorithms for certain counting problems
including simulating quantum computation. Their method expands the
vertices of $\Gamma$ into graph fragments called matchgates and
applies the FKT algorithm to find a Pfaffian orientation and compute
the perfect matching polynomial. We demonstrate a
geometrically-motivated simplification of this approach using only a
$|E| \times |E|$ matrix and give some generalizations.