Again, the basic ingredient for HAs is the efficiently computable FKT-algorithm, which works because of the grateful fact that we are able to compute the determinant in polynomial time.
The literature of Holographic Algorithms (which are a generalization of CSP-Problems) is huge and is dominated by works of Valiant, Cai and Lu, see e.g. [1,2,3]. The central theorem is the Holant Theorem, which proofs the equality of the number of perfect matchings of a graph $\mathcal{G}$ and the value of the Holant Function. The Holant Function is applied to a matchgrid, that is a graph composed of certain subgraphs (called matchgates), such that the total graph (the matchgrid) is the graph $\mathcal{G}$ and its structure incorporates a combinatorial function.
The matchgrid $\Omega$ can be seen as a bipartite graph whereof the matchgates are the vertices. For the application to count satisfying assignments, we are always faced with bipartite graphs: on the left are the variable nodes and on the right the clause nodes.
The Holant Function can be understood as a function that measures or counts particles that flow along the lines of the bipartite graph from the left nodes to the right nodes, i.e., from the variables to the clauses.
For HA two types of mathgates are sufficient: Generators and Recognizer. The generator generates patterns of particles along its output lines and the recognizer recognizes these patterns. Matchgates, i.e., generators and recognizers, are little graphs with only output and input nodes respectively.
In Figure 1, you see a simple generator, which is the box on the left denoted as A. It is just a small graph that connects two nodes and has one edge of weight 1. The two nodes are also the output nodes (thats why they are drawn of the outerface of the matchgate). Normally, there are more inner nodes.
 |
| Figure 1 - A generator and its signature configurations |
