Holographic Algorithms

This post shows an introduction to Holographic Algorithms (HA). From my point of view, Holographic Algorithms were motivated by analogies to quantum computing and to overcome some of the obstacles that occur when one follows Leslie Valiant's original approach using the permanent and cyclic covers to count satisfying solutions for boolean formulas.

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

A generator $\Gamma$ with $t$ output nodes can be can be assigned a signature $u$, which is a vector of length $2^{t}$. The vector contains the number of perfect matchings that remain when all possible combinations of output nodes are removed. So, the 4 boxes A,B,C and D in Figure 1, are the graphs that remain if all possible four combinations of the output nodes are removed.

• A: none removed $\rightarrow\;\text{PerfMatch}(\Gamma) = 1$
• B: 1 removed $\rightarrow\;\text{PerfMatch}(\Gamma-1) = 0$
• C: 2 removed $\rightarrow\;\text{PerfMatch}(\Gamma-2) = 0$
• D: both removed $\rightarrow\;\text{PerfMatch}(\Gamma-\{1,2\}) = 1$ (the number of perfect matching of the zero-graph is per definition 1)

So the standard signature $u$ of $\Gamma$, written as $u(\Gamma)$, is $(1,0,0,1)$. Figure 2 shows a recognizer matchgate. It has 3 input nodes and 1 internal node. Each edge has weight 1.

Figure 2 - A recognizer with 4 input nodes

In 8 combinations one could remove the input nodes which forms the signature  $(0,0,0,0,1,1,1,0)$. Note that after removing some input node combination the remaining number of nodes is odd, there can not be a perfect matching. And because of that you can not find a matchgate $\Gamma$ with three input nodes that has a standard signature $(0,1,1,1,1,1,1,1)$, which could e.g. represent a 3CNF clause. So one can not encode such constrains into the standard signature.
In order to make something similar possible, Holographic Algorithms use the definition of a basis and symbolic output symbols. The symbolic output symbols can be seen as particles that travel along the edges in certain combinations, generated by the generators and recognized by the recognizers.


The Basis and Symbolic Outputs. 

Consider matchgate $\Gamma$ with two output nodes and the standard signature $u(\Gamma) = (u_{00},u_{01},u_{10},u_{11})$. In Figure 3 you can see a generator that has 2 output nodes and generates the particle outputs $(n,p),(p,n)$ and $(p,p)$ but not $(n,n)$.

Figure 3 - A generator which sends particle combinations (n,p), (p,n) and (p,p) but not (n,n).

Hence the generator in Figure $3$ creates
$$ 0\cdot (n,n) + 1\cdot (n,p) + 1\cdot (p,n) + 1\cdot(p,p)$$ or in short $$(0,1,1,1) = (q_{00},q_{01},q_{10},q_{11})$$ In the context of holographic algorithms normally $n$ is denoted as $0$ and $p$ as $1$, so the ordering above is $00,01,10,11$.

Mathematically, the two particles $n$ and $p$ are vectors of length $2^k$ over $\mathbb{C}$. We first concentrate on the case $k=1$. Then we have the basis $$ \textbf{b} = [n,p] = \left[\binom{n_0}{n_1},\binom{p_0}{p_1} \right] = [(n_0,n_1)^T,(p_0,p_1)^T]$$

Mathematically, the pair of particles, e.g., $(n,p)$, that is send out over the output nodes is combined using the tensor product: $$n\otimes p = (n_0p_0,n_0p_1,n_1p_0,n_1p_1)$$ Here, the standard signature $u(\Gamma)$ and the particle output comes together. There must be the equality (for 2 symbolic outputs):
\begin{align*}
u(\Gamma)  & = q_{00}n\otimes n + q_{01}n\otimes p + q_{10}n\otimes n +q_{11}p\otimes p\\
(u_{00},u_{01},u_{10},u_{11}) & = q_{00}(n_0n_0,n_0n_1,n_1n_0,n_1n_1) + \\
& = q_{01}(n_0p_0,n_0p_1,n_1p_0,n_1p_1) + \\
& = q_{10}(p_0n_0,p_0n_1,p_1n_0,p_1n_1) + \\
& = q_{11}(p_0p_0,p_0p_1,p_1p_0,p_1p_1)
\end{align*}
which is equal to
\begin{align*}
u_{00} & = q_{00}n_0n_0 + q_{01}n_0p_0 + q_{10}p_0n_0 + q_{11}p_0p_0\\
u_{01} & = q_{00}n_0n_1 + q_{01}n_0p_1 + q_{10}p_0n_1 + q_{11}p_0p_1\\
u_{10} & = q_{00}n_1n_0 + q_{01}n_1p_0 + q_{10}p_1n_0 + q_{11}p_1p_0\\
u_{11} & = q_{00}n_1n_1 + q_{01}n_1p_1 + q_{10}p_1n_1 + q_{11}p_1p_1
\end{align*}
For example, if we have $u(\Gamma) = (1,0,0,1)$ (from Figure 1) and $$(0,1,1,1) = (q_{00},q_{01},q_{10},q_{11})$$, then the basis $\textbf{b} = [(-i,0),(i,1)]$ solves the equation system above. Normally, the approach is the other way round: Given a basis and a constraint $(q_{00},q_{01},q_{10},q_{11})$, is their a standard signature that solves this? Or given a constraint and a standard signature, which constraint can be realised with this?

Then we have a function called $\mathsf{valG}()$ (valuation Generator), that takes as the input the generator matchgate $\Gamma$ and a tensor product $T$, e.g., $n \otimes p$ ($\hat{=}01$) or $p \otimes p \otimes n$ ($\hat{=}110$)  and returns $q_{01}$ or $q_{110}$.

The $q$ values are important, since they define the combinatorial function or the constraint that we want to satisfy.

For recognizer the equations look a little bit different. Suppose you have a recognizer $\Gamma$ with $3$ input nodes and standard signature $$u(\Gamma) = (u_{000},u_{001},u_{010},u_{011},u_{100},u_{101},u_{110},u_{111})$$

Figure 4 - An example recognizer with 3 input nodes that does not allow all/or nothing inputs

Then if an input combination arrives, e.g., $n\otimes p\otimes n$, then it is evaluated via the $\mathsf{valR}()$ function, which is the inner product of the standard signature and the obtained input, e.g.:
\begin{align*}
\mathsf{valR}(\Gamma,n\otimes p\otimes n) = &\left<u(\Gamma), n\otimes p\otimes n\right> \\
= &\hat{q}_{010} \\
= &u_{000}n_0p_0n_0 + u_{001}n_0p_0n_1 + u_{010}n_0p_1n_0 + u_{011}n_0p_1n_1 + \\
&u_{100}n_1p_0n_0 + u_{101}n_1p_0n_1 + u_{011}n_1p_1n_0 + u_{111}n_1p_1n_1
\end{align*}
whereof the $\hat{q}$ values are the constraint or combinatorial function that is evaluated.

Definition [Holant]. The Holant value of the matchgrid $\Omega$ with base $\textbf{b}$, with $g$ generators $B_j$ and $r$ recognizers $A_i$ and $f$ edges that connect generators with recognizers, is then sum of products \begin{align*} \mathsf{Holant}(\Omega) & = \sum_{x \in \textbf{b}^f} \left[\prod_{1\leq j \leq g}\mathsf{valG}(B_j,x) \right] \left[\prod_{1\leq i \leq r}\mathsf{valR}(A_i,x) \right]\\ & = \sum_{x \in \textbf{b}^f} \prod_{1\leq j \leq g} q_{s_1(B_j,x)}\prod_{1\leq i \leq r} \hat{q}_{s_2(A_i,x)} \end{align*}

So, the Holant function is a large sum of products and the products are only $> 0$ if for each generator and recognizer a valid input/output combination was used, which is determined by the combinatorial function that is used as the constraint.

Figure 5 - A matchgrid

 In Figure 5 you can see what actually the proof explains. The two recognizers $A_1$ and $A_2$ have the edges $(1,3,4)$ and $(2,6,5)$ respectively. The three generators $B_1$, $B_2$ and $B_3$ have the edges $(1,2)$, $(3,5)$ and $(4,6)$. The $f=6$ connecting edges between the generators and recognizers can have the values $n$ and $p$ so in total there are $2^f$ possible flows.
Take for example the flow $x = (n,p,n,p,p,n) \hat{=} 010110$.  Then e.g. $s_1(B_1,x) = 01$ and $s_2(A_1,x) = 001$. And if each matchgate gets assigned correct input/output values (according to the defined constrained) $\mathsf{valG}$ and $\mathsf{valR}$ evaluate to some positive value and $0$ otherwise.

In particular, the Holant function is exponential. However, the following main theorem shows the main property of the HA.

Theorem [Holant]. Given the matchgrid $\Omega$ and let $\mathcal{G}$ be the total underlying graph, then we have the following equality: \begin{align*} \mathsf{Holant}(\Omega) = \mathsf{PerfMatch}(G) \end{align*} And if $\mathcal{G}$ is planar, the Holant-function can be computed in polynomial time due to the FKT-algorithm.

In general, if there are $x$ output nodes, a $k$-basis and $m$ symbolic out/inputs then it must hold $$ 2^x = 2^{k\cdot m} $$ So for $k=1$, you have $x = m$, which is the most intuitive way and actually already enough as written in [4].

The limitations come from the need to find a basis and a valid standard signature for a given combinatorial function.

If you want to count solutions of a boolean formula using the HA approach, you need:

1. A formula which has a planar incidence graph
2. A basis that solves the constraint for this formula over the integers or some field $\mathcal{F}$.

For example #Pl-3-NAE-SAT can be solved and also #$_7$Pl-Rtw-Mon-3CNF.

For the later you can e.g. chose $n = (1,6)$ and $p = (2,4)$ can create the generator that has the constraint $$(q_{00},q_{01},q_{10},q_{11}) = (1,0,0,1)$$ and the recognizer that has the constraint $$(q_{000},q_{001},q_{010},q_{011},q_{100},q_{001},q_{110},q_{111}) = (0,1,1,1,1,1,1,1)$$ The generator generates that variables. Since each variable occurs exactly twice and only non-negated, the constraint says: Either none output is used (variable = false) or both are used (variable = true). The recognizer evaluates to 1, if at least one input node is touched. So the representing clause is satisfied.

A solution of the associated equations exists for $\mathcal{F} = \mathbb{F}_7$. E.g. for the generator it holds
\begin{align*}
&1\cdot n\otimes n + 0\cdot n\otimes p + 0\cdot p\otimes n + 1\cdot p\otimes p \\
& = (1,6)\otimes (1,6) + (2,4)\otimes (2,4) \\
& = (1,6,6,36) + (4,8,8,16) = (5,14,14,52) \equiv (5,0,0,3) \pmod{7}
\end{align*}
which is realisable by e.g. the following generator matchgate:

Figure 6

[1] L. G. Valiant. Holographic Algorithms (Extended Abstract). In Proc. 45th IEEE Symposium
on Foundations of Computer Science, 2004, 306–315.
[2] L. G. Valiant. Accidental Algorithms. In Proc. 47th Annual IEEE Symposium on Foundations
of Computer Science 2006, 509–517.
[3] J-Y. Cai and Pinyan Lu. Holographic Algorithms: From Art to Science. To appear in STOC
2007. Also available at Electronic Colloquium on Computational Complexity Report TR06-
145.
[4] Cai, Jin-Yi; Lu, Pinyan (2011). "Holographic algorithms: From art to science". J. Comput. Syst. Sci. 77 (1): 41–61