AI Lab logo
menu MENU

Theory Seminar

Holographic algorithms without matchgates

Jason MortonAssistant Professor of Mathematics and StatisticsDepartment of Mathematics, Pennsylvania State University

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.

Sponsored by

Yaoyun Shi