Holographic Algorithms Part 3: Matchgate Identities

I still owe a proof of the identities invoked last post to characterize non-degenerate tensors. This relatively short post will be devoted to said proof. My primary reference for this section is Cai/Gorenstein’s paper “Matchgates Revisited.” The ideas it presents have roots in papers dating back to Valiant’s study of non-planar matchgate computation using characters in the context of simulating quantum computation by classical means. We haven’t mentioned this yet because this and the approach via signatures that we have described were shown to be equivalent by Cai, though this may form the subject of a future post. In any case, the exposition that follows will be limited to the signature theory of planar matchgates and will thus make no reference to characters.

We claimed last time that the following identities are necessary for a vector to be the standard signature of a planar matchgate {\Gamma}. In fact, we will show that they are also sufficient.

Theorem 1: The vector {u\in\mathbb{C}^n} is the standard signature of a matchgate {\Gamma} of arity {n} iff given any {\alpha,\beta\in\{0,1\}^n},

\displaystyle \sum^{\ell}_{i=1}(-1)^iu_{\alpha+e_{\gamma_i}}u_{\beta+e_{\gamma_i}} =0,\ \ \ \ \ (1)

where {e_j} denotes the bit vector with support at the {j}th bit, {\gamma_i} denotes the position of the {i}th nonzero bit of {\alpha+\beta}, and {\ell} is the Hamming weight of {\alpha+\beta}.

1. Necessity

We begin by showing necessity. The basic idea is that the matchgate identities are really just identities that sub-Pfaffians must satisfy, and if we impose upon our matchgate a Pfaffian orientation, the possible sign differences between the Pfaffian and {\text{PerfMatch}} in any of the subgraphs {\Gamma\backslash Z} will cancel each other out in those identities so that {\text{PerfMatch}} satisfies these same identities.

Let’s first prove the necessity of these identities for sub-Pfaffians:

Lemma 2: The identities of Theorem~1 hold if {u} is replaced by {\text{Pf}}, i.e.

\displaystyle \sum^{\ell}_{i=1}(-1)^i\text{Pf}^{\alpha+e_{\gamma_i}}\text{Pf}^{\beta+e_{\gamma_i}} =0.\ \ \ \ \ (2)

Here, {\text{Pf}^{\alpha}} for a string {\alpha\in\{0,1\}^n} denotes the Pfaffian of the weight matrix {A} of {\Gamma^{\alpha}:= \Gamma\backslash Z_{\alpha}}, where {Z_{\alpha}} denotes the input/output nodes indexed by the nonzero bits of {\alpha}. For convenience, if {\alpha_1,...,\alpha_k\in[n]}, denote the Pfaffian of the submatrix whose rows and columns are indexed by these {\alpha_i} by {\text{Pf}(\alpha_1,...,\alpha_k)}.

Proof: As we alluded to previously, the matchgate identities arise from the so-called Grassmann-Plucker identities. Specifically, if {i_1<\cdots<i_K} and {j_1<\cdots<j_{L}} are indices from {[k]}, then because {\text{Pf}(a,b) + \text{Pf}(b,a)} for any indices {a,b}, it is trivial to verify that

\displaystyle \sum^L_{\ell=1}(-1)^{\ell-1}\text{Pf}(j_{\ell},i_1,...,i_K)\text{Pf}(j_1,...,\hat{j_{\ell}},...,j_L) + \sum^K_{k=1}(-1)^{k-1}\text{Pf}(i_k,j_1,...,j_L)\text{Pf}(i_1,...,\hat{i_k},...,j_K) = 0.\ \ \ \ \ (3)

We can write this in a nicer way in terms of the symmetric difference {\{i_1,...,i_K\}\Delta\{j_1,...,j_L\}}, which we will denote by {\{k_1,...,k_M\}}:

\displaystyle \sum^{M}_{m=1}(-1)^m\text{Pf}(I\Delta\{k_m\})\text{Pf}(J\Delta\{k_m\}) = 0. \ \ \ \ \ (4)

Lemma~2 follows. \Box

2. Convenient Sign Cancellation

Now, it suffices to show that the extra signs mentioned above cancel in such a way that the Grassmann-Plucker identities still hold for {\text{PerfMatch}}. Fix some Pfaffian orientation of {\Gamma} and define {\delta(\alpha)\in\{-1,1\}} for {\alpha\in\{0,1\}^n} to be {\text{Pf}^{\alpha}/u_{\alpha}}.

Now compare equation (2), which we know, to equation (1), which we want. Because {\text{Pf}^{\alpha}} and {u^{\alpha}} differ only in sign for any string {\alpha}, the nonzero terms are in bijection. If the {\ell}th summands of (2) and (1) differ in sign by {\epsilon_{\ell}}, we want to show that for all {i,j}, {\epsilon_i\cdot\epsilon_j = 1}, i.e. {\delta(\alpha\oplus e_{\gamma_{i}})\delta(\alpha\oplus e_{\gamma_{j}}) = \delta(\beta\oplus e_{\gamma_{i}})\delta(\beta\oplus e_{\gamma_j})}. Cai/Gorenstein’s proof of this is a bit involved, so we will only sketch the key ideas in proving this.

Because {\alpha_{\gamma_i} = \bar{\beta_{\gamma_i}}} for all {i} by definition, really the claim we are making is the following:

Lemma 3: For any {1\le i<j\le k} and strings {u,\tilde{u}\in\{0,1\}^{i-1}}, {v,\tilde{v}\in\{0,1\}^{j-i-1}}, and {w,\tilde{w}\in\{0,1\}^{k-j}}, and bits {b,c\in\{0,1\}},

\displaystyle \delta(ubvcw)\delta(u\bar{b}v\bar{c}w) = \delta(\tilde{u}b\tilde{v}c\tilde{w})\delta(\tilde{u}\bar{b}\tilde{v}\bar{c}\tilde{w}).\ \ \ \ \ (5)

Proof: We will prove this for {b = c = 0}, though the proof for {b = 0, c = 1} follows analogously. We will assume that the matchgate is connected. For convenience, for each {i} attach a path of length 2 to the {i}th input/output node (with the two edges of weight 1) and define the new input/output node to be the other ends of these paths. Call it node {i}. Note that this doesn’t affect the standard signature of the matchgate.

A Pfaffian orientation on {\Gamma} induces one for each {\Gamma^{\alpha}}, which we’ll denote by {\vec{\Gamma^{\alpha}}}. Denote by {\text{Pf}_{\vec{\Gamma^{\alpha}}}(M^{\alpha})} (resp. {u^{\Gamma^{\alpha}}(M^{\alpha})}) the sign of the summand in the Pfaffian (resp {\text{PerfMatch}}) of {\Gamma^{\alpha}} (endowed with a particular Pfaffian orientation) corresponding to a matching {M^{\alpha}} of {\Gamma^{\alpha}}.

Fix values for {u,v,w}, and denote {\Gamma^{u0v0w}} and {\Gamma^{u1v1w}} by {\Gamma^{00}} and {\Gamma^{11}} respectively. Define {M^{00}} and {M^{11}} to be matchings of {\Gamma^{00}} and {\Gamma^{11}}. To get the desired result, we need to show that the value of the left-hand side of (5) is independent of the choice of {u,v,w}. Let {e} be the edge connecting input/output nodes {i} and {j}, define {\Gamma^*} to be {\Gamma^{00}\cup\{e\}}, with the extra edge oriented to preserve the Pfaffian orientation.

Define {M^*} to be the matching {M^{11}\cup\{e\}}. We show that the relationships between the sign of {M^*} and the signs of {M^{00}} and {M^{11}} are the same regardless of {u,v,w}.

First of all {\frac{\text{Pf}_{\vec{\Gamma^{00}}}(M^{00})}{u^{\Gamma^{00}}(M^{00})} = \frac{\text{Pf}_{\vec{\Gamma^*}}(M^{00})}{u^{\Gamma^*}(M^{00})}} because {M^{00}} doesn’t contain {e}, and {\frac{\text{Pf}_{\vec{\Gamma^*}}(M^{00})}{u^{\Gamma^*}(M^{00})} = \frac{\text{Pf}_{\vec{\Gamma^*}}(M^*)}{u^{\Gamma^*}(M^*)}} by definition of a Pfaffian orientation: all summands of the Pfaffian must have the same sign. We conclude that the signs of {M^*} and {M^{00}} are always the same.

The analysis for {M^{11}} is a bit trickier. {\text{Pf}_{\vec{\Gamma^{11}}}(M^{11})} and {\text{Pf}_{\Gamma^*}(M^*)} are off by a factor of {\text{sgn}(\pi^{11})\cdot A_{ij}}, where {\pi^{11}} is the permutation corresponding to the matching {M^{11}}. The sign of the permutation is {(-1)^z} where {z} is merely the number of edges from an output/input node between {i} and {j} to a point outside of this range, i.e. the number of zeros in {\alpha} between bits {i} and {j}. For {A_{ij}}, consider its value when {\alpha} is zero only at {i} and {j}. Now with every bit switched to zero, we’re including one more counterclockwise edge in the cycle formed by the new face created by the addition of {e}. In other words, {A_{ij} = (-1)^z\cdot F} for a quantity {F} not depending on {u,v,w}, so we’re done. \Box

3. Sufficiency

Next, we want to show that the matchgate identities are in fact sufficient conditions, i.e. given a {2^n}-vector {u}satisfying these identities, we can construct a planar graph with that vector as its standard signature. The idea will be to construct a graph, not necessarily planar, whose standard signature agrees with the desired signature in enough places that the matchgate identities force a single possible value for each of the other entries of its standard signature. We then want to alter this graph by replacing all intersection points with so-called “crossover gadgets” in order to obtain a planar graph with the same signature.

First let’s simplify the problem by assuming that {u_{11\cdots 1} = 1}. If this isn’t the case, define {u'_{\alpha} = u_{\alpha + \bar{\beta}}/u_{\beta}} for some {\beta} for which {u_{\beta}\neq 0}, and we’ll construct a matchgate with {u'} as its standard signature. After this, we can simply add an extra edge of length {u_{\beta}} disjoint from the rest of the matchgate, and attach extra edges to the appropriate input/output nodes, i.e. indexed by {i} for which {\bar{\beta}_i = 1}, and we’re done.

Let’s now set out constructing {\Gamma} with signature {u} under these assumptions. For now, let’s drop the condition of planarity. Consider the complete graph {K_n} on {n} vertices. For each edge {(i,j)}, assign the weight {u_{e_i+e_j+11\cdots 1}} so that {\underline{\Gamma}^{\alpha} = u_{\alpha}} as long as {\text{wt}(\alpha) = n-2}. On the other hand, defining {p_i} to be the index of the {i}th bit at which {\alpha} is zero, then applying the matchgate identities to the strings {\alpha + e_{p_1}} and {1^n + e_{p_1}} tells us that

\displaystyle \underline{\Gamma}^{\alpha}\underline{\Gamma}^{1^n} = \sum^{\ell}_{i=2}(-1)^i\underline{\Gamma}^{\alpha + e_{p_1} + e_{p_i}}\underline{\Gamma}^{1^n + e_{p_1} + e_{p_i}}.

But {\underline{\Gamma}^{1^n}} of the complete graph is clearly 1, and the summands on the right hand are products of entries in the standard signature of higher weight, so we conclude that it indeed suffices to know the entries of weight {n-2}.

4. Planarity Assumption

Now we want to get rid of the planarity assumption by replacing all of the places where edges intersect by the crossover gadget {X} shown in the figure below. Among the non-gadget edges corresponding to an edge between vertices of the original {\Gamma}, pick one edge to assign a weight of the original edge to. Call the resulting matchgate {G}.

The crossover gadget (taken from Cai/Gorenstein)- all unlabeled edges are of weight 1

The crossover gadget (taken from Cai/Gorenstein)- all unlabeled edges are of weight 1

Lemma 4: {\underline{G} = \underline{\Gamma}}.

Proof: First note that the standard signature of {X} is given by {\underline{X}^{0000} = \underline{X}^{0101} = \underline{X}^{1010} = -\underline{X}^{1111} = 1}, {\underline{X}^{\alpha} = 0} for all other {\alpha}. Next, denote by {I} all edges in {G} which do not belong to a copy of {X}; we’ll call these edges “passage edges.” Note that any perfect matching {M} of {\Gamma} corresponds to a subset of passage edges, call it {S(M)}.

We can restrict our attention to perfect matchings {M'} of {G} for which {M'\cap I = S(M)} for some perfect matching {M} of {\Gamma}. The reason is that if one cannot reconstruct {M} from {M'\cap I}, there is one copy of {X} for which there is an odd number of passage edges incident to {X} or else exactly two passage edges incident to vertices on the same side of {X}. But recall that the crossover gadget was designed to have standard signature equal to zero at these entries and thus not contribute to {\text{PerfMatch}}.

Now we’re almost done.

\displaystyle \underline{G}^{\alpha} = \sum_{M'}\sum_{(i,j)\in M'}A_{ij} = \sum_{S\subseteq I}\sum_{M'\cap I = S}\prod_{(i,j)\in M}A_{ij} = \sum_{M}\sum_{M'\cap I = S(M)}\prod_{(i,j)\in M'}A_{ij}.\ \ \ \ \ (6)

But observe that of all the four valid combinations (indexed by {0000,0101,1010,1111}) of corner vertices to remove from {X}, only in the case that all are removed (i.e. the crossover gadget is the sight of an actual crossover in the original matching of {\Gamma}) is {\sum_{M''}\prod_{(i,j)\in M}A_{ij}\neq 1}, where the sum is taken over all perfect matchings of {X} with these vertices removed. In particular, this sum is -1. Thus, the sum {\sum_{M'\cap I}\prod_{(i,j)}A_{ij}} in (6) is {(-1)^{m}\prod_{e\in M}w(e)}, where {m} is the number of crossovers. But a matching with an odd number of crossovers corresponds to an odd permutation, so (6) is precisely equal to {\text{Pf}(\Gamma^{\alpha})}. Now just pick a Pfaffian orientation, and we’re done. \Box

In the next post, we will look at the geometric meaning behind the matchgate identities.


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