About the EventCombinatorial (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
"sumproduct 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 Pfaffianbased
approach has been used by Valiant and Cai to provide unexpected,
polynomialtime "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
geometricallymotivated simplification of this approach using only a
$E \times E$ matrix and give some generalizations.
