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 . In fact, we will show that they are also sufficient.
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 in any of the subgraphs will cancel each other out in those identities so that 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 is replaced by , i.e.
Here, for a string denotes the Pfaffian of the weight matrix of , where denotes the input/output nodes indexed by the nonzero bits of . For convenience, if , denote the Pfaffian of the submatrix whose rows and columns are indexed by these by .
Proof: As we alluded to previously, the matchgate identities arise from the so-called Grassmann-Plucker identities. Specifically, if and are indices from , then because for any indices , it is trivial to verify that
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 . Fix some Pfaffian orientation of and define for to be .
Now compare equation (2), which we know, to equation (1), which we want. Because and differ only in sign for any string , the nonzero terms are in bijection. If the th summands of (2) and (1) differ in sign by , we want to show that for all , , i.e. . Cai/Gorenstein’s proof of this is a bit involved, so we will only sketch the key ideas in proving this.
Because for all by definition, really the claim we are making is the following:
Proof: We will prove this for , though the proof for follows analogously. We will assume that the matchgate is connected. For convenience, for each attach a path of length 2 to the 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 . Note that this doesn’t affect the standard signature of the matchgate.
A Pfaffian orientation on induces one for each , which we’ll denote by . Denote by (resp. ) the sign of the summand in the Pfaffian (resp ) of (endowed with a particular Pfaffian orientation) corresponding to a matching of .
Fix values for , and denote and by and respectively. Define and to be matchings of and . 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 . Let be the edge connecting input/output nodes and , define to be , with the extra edge oriented to preserve the Pfaffian orientation.
Define to be the matching . We show that the relationships between the sign of and the signs of and are the same regardless of .
First of all because doesn’t contain , and by definition of a Pfaffian orientation: all summands of the Pfaffian must have the same sign. We conclude that the signs of and are always the same.
The analysis for is a bit trickier. and are off by a factor of , where is the permutation corresponding to the matching . The sign of the permutation is where is merely the number of edges from an output/input node between and to a point outside of this range, i.e. the number of zeros in between bits and . For , consider its value when is zero only at and . 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 . In other words, for a quantity not depending on , so we’re done.
Next, we want to show that the matchgate identities are in fact sufficient conditions, i.e. given a -vector 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 . If this isn’t the case, define for some for which , and we’ll construct a matchgate with as its standard signature. After this, we can simply add an extra edge of length disjoint from the rest of the matchgate, and attach extra edges to the appropriate input/output nodes, i.e. indexed by for which , and we’re done.
Let’s now set out constructing with signature under these assumptions. For now, let’s drop the condition of planarity. Consider the complete graph on vertices. For each edge , assign the weight so that as long as . On the other hand, defining to be the index of the th bit at which is zero, then applying the matchgate identities to the strings and tells us that
But 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 .
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 shown in the figure below. Among the non-gadget edges corresponding to an edge between vertices of the original , pick one edge to assign a weight of the original edge to. Call the resulting matchgate .
Lemma 4: .
Proof: First note that the standard signature of is given by , for all other . Next, denote by all edges in which do not belong to a copy of ; we’ll call these edges “passage edges.” Note that any perfect matching of corresponds to a subset of passage edges, call it .
We can restrict our attention to perfect matchings of for which for some perfect matching of . The reason is that if one cannot reconstruct from , there is one copy of for which there is an odd number of passage edges incident to or else exactly two passage edges incident to vertices on the same side of . But recall that the crossover gadget was designed to have standard signature equal to zero at these entries and thus not contribute to .
But observe that of all the four valid combinations (indexed by ) of corner vertices to remove from , 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 ) is , where the sum is taken over all perfect matchings of with these vertices removed. In particular, this sum is -1. Thus, the sum in (6) is , where 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 . Now just pick a Pfaffian orientation, and we’re done.
In the next post, we will look at the geometric meaning behind the matchgate identities.