Holographic Algorithms Part 1: Matchgrids and the Holant

The last post armed us with a powerful piece of polynomial-time computation, the FKT algorithm. In this post we’ll begin to explore how to leverage this to solve other problems under Valiant’s holographic framework by developing the basic theory of matchgrids, including the original proof of Valiant’s flagship Holant theorem, a first glimpse at a holographic reduction using these tools, and a reformulation (due to Cai/Choudhary) of everything in terms of tensors.

At a high level, just as FKT solves a counting problem, {\text{PerfMatch}(G)}, related to a graph {G} by tweaking {G} until that counting problem becams something we know how to solve efficiently, namely the Pfaffian, the Holant theorem will allow us to solve counting problems related to {G} by building out of {G} a (planar) grid {\Omega} of “gadgets” called matchgates which capture the constraints related to the counting problem in question, so that the answer to the counting problem becomes something we know how to solve efficiently, namely {\text{PerfMatch}(\Omega)}. In particular, the counting problem is encoded by {\Omega} so that its answer is by construction equal to a particular function of the weighted edges of {\Omega}, an exponential sum of terms known as the Holant. We should think of the Holant as a global consolidation of all the local data needed to solve the counting problem at hand.

The whole point is that whereas we can rig the Holant to capture all this information because it’s defined as this huge exponential sum that we can’t hope to brute-force any more than we can our original problem, the FKT and Holant theorems imply that there are exponential cancellations among these terms, and solving the counting problem is as easy as computing the Holant is as easy as computing {\text{PerfMatch}}.

Of course, the tricky part is to define what the abovementioned “gadgets” are and how they can encode the local constraints we want. Before we introduce these key players, however, let’s play around with how we might encode the constraints of perfect matching locally.

1. Matchgates and Matchgrids

Our discussion at the beginning might come off as somewhat slow, but I’ll include it for those seeking motivation for all the definitions I’m throwing at the reader. For the time being, the following definitions will suffice.

Definition 1: A matchgate {\Gamma} is the data of a weighted, undirected planar graph {G = (V,E,W)}, a set of output nodes {Y\subset V}, and a set of input nodes {Z\subset V}. {\Gamma} is said to be of arity {|X|+|Y|}.

We will restrict our attention to matchgates exclusively containing output nodes, called generators, and exclusively containing input nodes, called recognizers. All other matchgates are called transducers.

Definition 2: A matchgrid {\Omega} is the planar graph defined as the union of a set of generators {G_1,...,G_g}, a set of recognizers {R_1,...,R_r}, and a set of edges {W_1,...,W_n} of weight 1, called wires, such that each input and output node in the matchgrid has exactly one incident wire.

Any perfect matching {M} assigns to each of the wires a bit depending on whether that wire belongs in the matching. Consider the set {X} of all {2^n} possible bit vectors {x} that can be assigned to the wires of {\Omega}. For a fixed {x\in X}, say that {x} decomposes as the concatenation {y_1\circ\cdots\circ y_g} and {z_1\circ\cdots z_r} for {y_i\in\{0,1\}^{|G_i|}} and {z_j\in\{0,1\}^{|R_j|}} denoting whether the input nodes in {G_i} and {R_i} respectively belong to wires assigned either 0 or 1.

Let {W = (v_o, v_i)} be one of these wires, with output node {v_o} belonging to generator {G} and input node {v_i} belonging to recognizer {R}. If {W} is assigned 0 (resp. 1) so that {W} does not (resp. does) belong to the matching, the matching restricts to a perfect matching of a subgraph of {G} including (resp. not including) {v_o} and a perfect matching of {R} including (resp. not including) {v_i}.

The point is the following. For fixed {x}, the contribution to {\text{PerfMatch}(\Omega)} of perfect matchings of {\Omega} coresponding to {x} is {\prod_{G_i}\text{PerfMatch}(G_i\backslash Y_i)\prod_{R_i}\text{PerfMatch}(R_i\backslash Z_i),} where {Y_i} denotes the subset of output nodes of {G_i} for which {y_i} is an indicator bit vector, and {Z_i} is defined likewise.

More generally, for matchgate {\Gamma} with output nodes {Y} and input nodes {Z}, define the standard signature {u(\Gamma)} of {\Gamma} to be the {2^{|Y|}\times 2^{|Z|}} matrix whose {(y_i,z_i)}th entry is {\text{PerfMatch}(\Gamma\backslash (Y_i\cup Z_i))}. Note that the standard signature of a generator (resp. recognizer) is a column (resp. row) vector. It follows that {\text{PerfMatch}(\Omega) = \sum_x\prod_{G_i}u(G_i)_{y_i}\prod_{R_i}u(R_i)_{z_i}}.

Our informal discussion is almost done; we just need a bit of formality to help transition into our actual treatment of matchgates. Let {\beta} denote the standard basis {\{n,p\} = \{(1,0),(0,1)\}}. In the decomposition of {u(G)} for generator {G} as a linear combination of all {x_i\in\beta^{\otimes |Y|}}, the coefficient of {x_i} is obviously {u(G)_{x_i}}. Define this as {\text{valG}(G,x_i)}, and define the vector of all such values as {\text{valG}(G)}. In other words, the signature of {G} with respect to the standard basis is rigged to be the standard signature {u(G)}. The picture you should keep in mind is that generators emit from their {|Y|} output nodes all {2^{|Y|}} possible combinations of {n} and {p} particles, where each combination is weighted by the appropriate entry in {\text{valG}(G)}.

What’s another fancy way to express the standard signature of a matchgate “dual” to the one we’ve just given (more on this in the last section)? The inner product of {x_i\in\beta^{\otimes |Z|}} with {u(R)} for recognizer {R} is also obviously {u(R)_{x_i}}. Define this as {\text{valR}(R,x_i)}, and define {\text{valR}(R)} as the vector of all such values; call this vector the signature of {R} with respect to {\beta}. Again, the signature of {R} with respect to the standard basis is the standard signature {u(R)}. The picture here is that recognizers take in all combinations of {n} and {p} particles into their input nodes and spit out their values specified by the appropriate entries in {\text{valR}(R)}.

To complete the analogy, wires are the medium by which these particles are transferred. As such, we will occasionally regard the vector {x} as an element of {\{n,p\}^{|n|}}. In any case, the moral is that

\displaystyle \text{PerfMatch}(\Omega) = \sum_x\prod_{G_i}\text{valG}(G_i,y_i)\prod_{R_i}\text{valR}(R_i,z_i).\ \ \ \ \ (1)

 

2. Valiant’s Holant Theorem and Changes of Basis

Of course, this is pretty trivial given that we picked {\beta} to be the standard basis. We could likewise have defined {\text{valG}} and {\text{valR}} for arbitrary bases consisting of vectors of length 2 (in fact we can also consider vectors of dimension {2^k} for arbitrary {k}, but that’s a topic for another post). Define the Holant of {\Omega} to be the quantity on the right-hand side of (1). The content of Valiant’s Holant Theorem is the following miracle:

Theorem 3: Identity (1) holds regardless of the choice of basis. In other words, {\text{Holant}(\Omega) = \text{PerfMatch}(\Omega)}.

Why should we care? Recall that our ultimate goal is to take our input graph {G}, construct a matchgrid {\Omega} whose matchgates capture the local constraints of the counting problem at hand so that {\text{Holant}(\Omega)} equals the solution to our counting problem, and compute the solution by efficiently computing {\text{Holant}(\Omega) = \text{PerfMatch}(\Omega)}. Different signatures encode different kinds of constraints, and the issue with the standard basis is that it can’t realize all signatures. The Holant theorem tells us this isn’t an issue because we can just use other bases.

Whether some basis can realize a particular signature for a given matchgate boils down to whether the corresponding system of polynomial equations is solvable. We will give a nice formulation of such a system in a future post, but for now let’s illustrate with an extended example.

Example 1: Let’s just consider matchgates {\Gamma} with arity 2. What kinds of standard signatures exist? For starters, {G} has an odd or even number of vertices, so if we take out an even or odd number of vertices respectively, we’re left with zero perfect matchings. In other words, {u(\Gamma)} must be a vector such that either 1) {u(\Gamma)_{x_i} = 0} whenever {|x_i|} is even, 2) {u(\Gamma)_{x_i} = 0} whenever {|x_i|} is odd. For arity 2, not only is this a necessary condition for a standard signature to be realizable, but it’s sufficient.

For all {x,y\in\mathbb{C}}, {(x,0,0,y)} and {(0,x,y,0)} are realizable as standard signatures.

Proof: For the former signature, consider the path graph with three vertices whose endpoints are the output nodes and whose edge weights are {x} and {y}. For the latter signature, consider the path graph with four vertices, whose endpoints are the output nodes and whose edge weights are {x}, {y}, and 1. \Box

Now what kinds of signatures are realizable by these matchgates in other bases? Consider the basis {\beta = \{(a,b),(c,d)\}} and a signature {q = (q_{00},q_{01},q_{10},q_{11})}. For a generator {G} with standard signature {(u_{00},u_{01},u_{10},u_{11})}, the constraint that either {u_{00} = u_{11} = 0} or {u_{01} = u_{10} = 0}, combined with the definition of {\text{valG}}, implies that one of the following two polynomial systems must have a solution in {q}:

\displaystyle a^2q_{00} + acq_{01} + acq_{10}+c^2q_{11} = b^2q_{00} + bdq_{01}+bdq_{10}+d^2q_{11} = 0

\displaystyle abq_{00} + adq_{01} + bcq_{10} + cdq_{11} = abq_{00} + bcq_{01} + adq_{10}+cdq_{11} = 0.

So for example, for {(a,b,c,d) = (1,1,1,-1)}, the first equation is satisfied as long as the signature is of the form {(x,y,-y,-x)}, while the second equation is satisfied as long as the signature is of the form {(x,y,y,x)}.

3. A First Proof

The following is the original proof of Valiant’s Holant theorem. The idea is to blow the matchgrid {\Omega} up into an family of exponentially many matchgrids {\Omega(y_1,...,y_g)} consisting of generators and recognizers of arity 1, each representing a possible combination {x} of bits passed along the wires of {\Omega}, such that {\text{MatchSum}(\Omega(y_1,...,y_g))} equals the contribution of {x} to the Holant. We then build the matchgrid back up out of these components, arguing by linearity at each step that {\text{MatchSum}} of each component equals its respective contribution to the Holant. At the end, we obtain a graph for which {\text{MatchSum}} and {\text{PerfMatch}} agree, and we’re done.

Proof: Pick a fixed vector {x\in\{n,p\}^n} of particles assigned to the wires. We first claim that there exists a generator of arity 1 whose standard signature, if we allow “omittable nodes,” can be any 2-vector {w = (w_0,w_1)} that we want. Consider the path graph {G} on three vertices with edge weights {w_1} and {w_0} from left to right and output node {v} the rightmost vertex. Normally, we’d say that the standard signature of this generator is {(\text{PerfMatch}(G),\text{PerfMatch}(G\backslash v)) = (0,w_1)}. As a hackish fix, let’s also count matchings which potentially omit the leftmost vertex {u}. Specifically, if we assign weight {1} to vertex {u} and weight {0} to vertex {v}, then {(\text{MatchSum}(G),\text{MatchSum}(G\backslash v)) = (w_0,w_1)} as desired. For a given 2-vector {w}, denote the corresponding arity-one generator by {G_w}.

Say that {G_i} emits some string {s\in(n,p)^{\otimes|Y_i|}} of {n} and {p} particles from its output nodes. Then replace {G_i} by the disjoint union of {G_{\text{valG}(G_i,y_i)\cdot s_1},G_{s_2},...,G_{s_{|Y_i|}}}, and for each {j\in[Y_i]}, rehook the wire originally going into the {j}th output of {G_i} into the output node of {G_{s_j}}. We’ve purposely scaled up one of these arity-1 generators by {\text{valG}(G_i,y_i)} so that these {|Y_i|} generators will emit {s} with the same weighting as {G_i}. Call this new matchgrid {\Omega(y_1,...,y_g)}.

The point of all of this is that now,

\displaystyle \text{MatchSum}(\Omega(y_1,...,y_g)) = \left(\prod_{G_i}\text{valG}(G_i,y_i)\right)\left(\prod_{R_i}\text{valR}(R_i,z_i)\right)

(note that implicitly we’re weighting each recognizer vertex by 0).

To be explicit, any matching corresponds to a bitstring {t\in\{0,1\}^n} depending on whether the omittable nodes in our arity-1 generators are present, and in particular corresponds to an entry {u} in {x_1\otimes x_2\otimes\cdots\otimes x_n}, namely {(x_1)_{t_1}\cdots(x_n)_{t_n}}. If {u_i} denotes {\prod_{t_j\in Z_i}(x_j)_{t_j}} so that {u = \prod u_i}, and {Z^u_i} denotes the input nodes of {R_i} already occupied in our matching by a wire, the matchings corresponding to a particular such entry {u} thus contribute to {\text{MatchSum}(\Omega(y_1,...,y_g))} a total of {\left(\prod_{G_i}\text{valG}(G_i,y_i)\right)\left(\prod_{R_i}u_i\cdot\text{PerfMatch}(G_i\backslash Z^u_i)\right)}. But by definition of {\text{valR}(R_i,z_i)} as the inner product of {u(R_i)} with {z_i}, {\sum_{u}\prod_{R_i}u_i\cdot\text{PerfMatch}(G_i\backslash Z^u_i)} is precisely {\prod_{R_i}\text{valR}(R_i,z_i)}.

The rest of the argument basically follows by linearity. Split {X} into groups of {2^{|Y_1|}} elements each, where in each group all elements assign the same particles to the output nodes of {G_2,...,G_g}. For any one group, say that the assignment to these output nodes is {y_2\circ\cdots\circ y_n}. For any {y_1}, let {x = y_1\circ\cdots\circ y_n}, and define {\Omega(y_2,...,y_n)} to be {\Omega(y_1,...,y_g)} with the arity-1 generators corresponding to {G_1} replaced once more by {G_1}. We can now split the matchings of this new matchgrid up based on which particles {G_1} outputs, concluding that {\text{MatchSum}(\Omega(y_2,...,y_n)) = \sum_{y_1}\left(\prod_{G_i}\text{valG}(G_i,y_i)\right)\left(\prod_{R_i}\text{valR}(R_i,z_i)\right)}.

Now we can keep playing this game; define {\Omega(y_3,...,y_n)} to be {\Omega(y_2,...,y_n)} for any {y_2}, with the arity-1 generators corresponding to {G_2} replaced once more by {G_2}, so that {\text{MatchSum}(\Omega(y_3,...,y_n)) = \sum_{y_1,y_2}\left(\prod_{G_i}\text{valG}(G_i,y_i)\right)\left(\prod_{R_i}\text{valR}(R_i,z_i)\right)}. Continuing thus, we conclude that {\text{MatchSum}(G())} is precisely the Holant. But {\text{MatchSum}(G())=\text{PerfMatch}(G())} because we’ve gotten rid of all the omittable nodes we initially introduced. \Box

4. {\#X-MATCHINGS}

Here’s our first example of a holographic algorithm. As a bit of background, recall the remark from the last post that while counting perfect matchings of planar graphs is easy, counting arbitrary matchings of planar graphs is {\#P}-complete. In fact, a theorem by Vadhan says that counting matchings even in bipartite graphs of degree at most six is just as hard!

Let’s consider a slightly less ambitious problem. Say I wanted to compute the number of matchings in any bipartite graph where the left vertices have degree 2 and the right vertices have degree {d}. Then I claim there exists a holographic algorithm solving this problem {\pmod{d+1}}.

In fact, there exists a holographic algorithm for the so-called {\#X-MATCHINGS} problem which subsumes the above as a special case: given a planar weighted bipartite graph whose left vertices have degree 2, compute the sum of the “masses” of all matchings. Here, the “mass” of a matching {M} is the product of {\prod_{(i,j)\in M}A_{ij}} with {\prod_{v\not\in M}\sum_{(i,v)}(-A_{i,v})}. (For the previous problem, weight all the edges by 1 and note that {(-d)^{k}\equiv 1\pmod{d+1}}).

Given such a bipartite graph {(V,E,W)}, we want to replace each left vertex by a generator of arity 2 which sends out at most 1 {p} particle, i.e. {u(\Gamma) = n\otimes n + n\otimes p + p\otimes n}; this translates to the local constraint that a matching will contain at most one edge incident to any given left vertex. We want to replace each right vertex {v} by a recognizer of arity {\deg(v)} which 1) outputs 0 when sent more than 2 {p} particles, 2) outputs {w} when sent exactly 1 {p} particle along a wire of weight {w}, 3) outputs {\sum_{(i,v)}(-A_{i,v})} when sent no {p} particles. 1) captures the local constraint that a matching will contain at most one edge incident to any given right vertex. 2) captures the constraint of the first multiplicand defining “mass.” 3) captures the constraint of the second multiplicand.

By construction, the Holant will equal the product of the masses of all matchings: subsets of {E} which aren’t matchings contribute nothing, while those that are matchings contribute precisely their mass to the Holant.

It remains to check that we can construct matchgates with the abovementioned signatures under some basis. For the generators, consider the single edge with output nodes both vertices and weight -1. Its standard signature is {(-1,0,0,1)} ({\text{PerfMatch}} of the empty graph we will take to be 1), so we want 2-vectors {n} and {p} satisfying relevant polynomial constraints. I won’t bore you any further by writing these down, but suffice it to say that the basis with {n = (-1,1)} and {p = (1,0)} works.

For the recognizers, consider the star graph on {\deg(v)+1} vertices and edge weights {\{A_{i,v}\}}. Its standard signature is 0 at all entries corresponding to removing at most {\deg(v)-2} input nodes, and {A_{i,v}} at the entry corresponding to removal of all but the input node corresponding to {A_{i,v}}, and {\sum(-A_{i,v})} at the entry corresponding to removal of all nodes. The signature with respect to {n = (-1,1)} and {p = (1,0)} is the one we want.

By Valiant’s Holant theorem and the FKT algorithm, we conclude that there exists a polynomial time algorithm for {\#X-MATCHINGS}.

The key takeaway of this example is that the primary challenge of understanding the power of holographic algorithms is determining what collections of combinatorial constraints encoded by signatures are simultaneously realizable under a choice of bases for each wire? As you can tell from the above discussion about polynomial systems suggests, the question really boils down to determining whether the corresponding subvarieties of {\text{GL}(2)} have nonempty intersection. More on this in a future post.

5. A Tensor Formulation

We now give an alternative formulation of the theory of matchgrids in terms of tensors, due to Cai/Choudhary. The motivation is that the statement of the Holant theorem and the fact that it holds trivially for the standard basis seems to suggest that if we stare closely at the definitions, there should probably be a nice, coordinate-free proof. Indeed, if we think about {\text{valG}}, {\text{valR}}, and the Holant in the right way, we can get a very quick proof of the Holant theorem.

The exposition will follow Cai/Choudhary’s 2005 paper “Valiant’s Holant Theorem and Matchgate Tensors.”

As above, let {\beta = [n,p]} denote a basis of two column 2-vectors for {n = (n_0,n_1)^T} and {p = (p_0,p_1)^T}, and {b = [e_0,e_1]} the standard basis, and regard the standard signature {u(\Gamma)} of a matchgate {\Gamma} with outputs {Y} and inputs {Z} as a {2^{|Y|}\times 2^{|Z|}} matrix so that {u(\Gamma)} is a column (resp. row) vector if {\Gamma} is a generator (resp. recognizer). Also let {T} be the transformation matrix defined b {\beta = b\cdot T}. We’ll assume {T} is invertible for now.

If {G} is a generator with {n} inputs, then {\text{valG}(G)} is the column vector defined by the equation {b^{\otimes n}u(G) = \beta^{\otimes n}\text{valG}(G)}. Writing {\beta^{\otimes n}} as {b^{\otimes n}T^{\otimes n}}, we conclude that {\text{valG}(G) = (T^{-1})^{\otimes n}u(\Gamma)}. On the other hand, if {R} is a recognizer with {n} inputs, then the original definition of {\text{valR}(R)} tells us it’s merely {u(R)T^{\otimes m}}.

In what sense are these two constructions dual to each other? Let {b^*} denote the basis dual to {b} such that {(e^*_i)(e_j) = \delta_{ij}}; define {\beta^*} anlogously. Whereas {\text{valG}} is the vector of coefficients by which {u(\Gamma)} can be expressed in the basis {\beta^n}, we can show that {\text{valR}} is the vector of coefficients by which {u(\Gamma)} can be expressed in the basis {(\beta^*)^n}. Then {b^* = T\beta^*} implies that {u(\Gamma)(b^*)^{\otimes n} = u(\Gamma)T^{\otimes n}(\beta^*)^{\otimes n}} as desired.

Now consider a matchgrid {\Omega} with {g} generators {G_1,...,G_g}, {r} recognizers {R_1,...,R_r}, and {w} wires {W_1,...,W_w}. If {X = \{n,p\}^{\otimes w}} and {X^*} is its dual space, one observes that the Holant is merely the application of dual vector {\otimes_{j}\left(\text{valR}(R_j)(\beta^*)^{\otimes |Z_j|}\right)\in X^*} to {\otimes_i\left((\beta)^{\otimes |Y_i|}\text{valG}(G_i)\right)}. Alternatively, we could write the Holant as

\displaystyle \text{Holant}(\Omega) = \left\langle\bigotimes_j\text{valR}(R_j),\bigotimes_i\text{valG}(G_i)\right\rangle.

The proof of the Holant Theorem is now quite straightforward: by our alternative definitions of {\text{valR}} and {\text{valG}}, we can write the two arguments of the inner product defining {\text{Holant}(\Omega)} as {\left(\otimes_j u(R_j)\right)T^{\otimes w}} and {(T^{-1})^{\otimes w}\left(\otimes_i u(G_i)\right)}, from which we conclude that {\text{Holant}(\Omega)} in any basis is equal to {\left\langle\otimes_j u(R_j),\otimes_i u(G_i)\right\rangle}. Recall that this equals {\text{PerfMatch}(\Omega)} for combinatorial reasons, by our earlier discussion.

For the case where {T} is not invertible, we just need that the span of {\beta} contains {u(G)} for each generator {G}, because then we can still define {\text{valG}(G)} to be any one of the vectors for which {b^{\otimes n}u(G) = \beta^{\otimes n}\text{valG}(G)}. The Holant theorem follows in essentially the same way.

If {V^{i}_j} denotes the tensor product of {i} copies of {V} and {j} copies of {V^{*}}, where {V:= \mathbb{C}^2}, what the above discussion tells us is that {\text{valG}} should be thought of as living inside {V^{n}_0}, {\text{valR}} inside {V^0_{n}} should be thought of as living inside {V^0_n}, and the Holant is merely the contraction of {\bigotimes_j\text{valR}(R_j)} with {\bigotimes_j\text{valG}(G_i)}. Specifically,

\displaystyle \text{valG}(G) = \sum_{i_1,...,i_m\in Y}\text{PerfMatch}(G - \cup_jv_{i_j})b_{i_1}\otimes\cdots\otimes b_{i_m}

\displaystyle \sum_{i_1,...,i_m\in Z}\text{PerfMatch}(R - \cup_jv_{i_j})b^*_{i_1}\otimes\cdots\otimes b^*_{i_m},

where {b_i} and {b^*_i} denote copies of the standard basis and dual basis indexed by the input/output nodes of the matchgate in question. Valiant’s Holant theorem then immediately follows merely for the abovementioned combinatorial reasons.

6. Two Unrelated Remarks

The first is that this is my first post using Prof. Luca Trevisan’s nifty LaTeX2WP script for converting TeX into something suitable for pasting into WordPress’s editor; highly recommended for anyone fed up with typing “... ” and hand-numbering section and theorem numbers in the tiny WP editor window!

The second is that my statement about Gaussian elimination as it relates to FKT from the previous post was incorrect. The polynomial-time algorithm we should be using is Berkowitz’ algorithm, because for numerical reasons we don’t want to use division.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s