#### Theory Seminar

# Holographic algorithms without matchgates

Add to Google Calendar

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.