Our treatment of holographic algorithms thus far has only worked with bases of size 1 (a basis of size is a pair of -dimensional vectors). In the first section, we will describe the few simple steps needed to generalize our framework so far to bases of higher size. One naturally wonders whether higher-dimensional basis vectors add power to holographic algorithms. We will first briefly explore an example mentioned in our first post in this series that might seem to suggest this to be the case. Pl-Rtw-Mon-3CNF, the problem of determining the number of satisfying assignments in any planar, read-twice, monotone 3-CNF was shown by Valiant to be $\oplus P$-hard modulo 2 but admit a polynomal-time algorithm modulo 7 using holographic matchgates and a basis of size 2. At the time, people wondered whether bases of higher size indeed added power.
Cai/Lu later showed however that this problem can actually be solved only using matchgates over a basis of size 1. We sketch both algorithms in the second section. They subsequently showed that in fact all holographic algorithms using bases of size 2 can be “collapsed” to ones using bases of size 1 (The reason they stopped at 2 at the time was that for higher sizes, there exists an additional constraint for realizability of signatures, namely the so-called “Grassmann-Plucker identities”, which adds considerable complexity to the problem). They later extended their ideas for the original collapse theorem to prove a general basis collapse theorem by discovering that for so-called “non-degenerate bases” (degenerate bases give rise to trivial holographic algorithms and are uninteresting), it’s possible to break any such basis down into an “embedded basis” of 2-vectors capturing all the expressiveness of the higher-dimensional basis. Long story short, Cai/Lu showed that in fact higher-dimensional bases do not add power to holographic algorithms. The main goal of this post will be to present the proof of their final basis collapse theorem.
1. Bases of Size
In general, if a tensor of arity is realized over a basis of size , the corresponding matchgate has arity , and it’ll be convenient to think of its input/output nodes as split into “blocks” of size . Call the basis’ transformation matrix , and denote by the entry in row and column .
We can then extend the tensor-theoretic formulation covered last time as follows. As usual, the contravariant tensor G of a generator has signature over iff . Concretely, for ,
where denotes the standard signature of . Likewise, the covariant tensor R of a recognizer has signature over iff . Concretely,
where denotes the standard signature of .
2. Solutions Modulo 7
First note that the constraints of Pl-Rtw-Mon-3CNF can be simulated using generators with signature and recognizers with signature . The generators represent variables and the recognizers clauses. The symmetric signature captures the read-twice condition because the generator has arity 2 and captures the constraint that the truth values of the two instances of the variable are consistent because and are emitted with weight 0. The symmetric signature captures the 3CNF condition because the recognizer has arity 3 and captures the problem of satisfiability because it only recognizes instances where all three variables being transmitted are true.
Unfortunately, these signatures are not realizable in or , but Valiant showed that they are realizable in , specifically via the basis and .
Cai/Lu showed that these signatures are in fact realizable over the basis and . (For now we will defer the details of proving realizability in both cases; time permitting, I’ll write up a post some time on Cai/Lu’s successful characterization of realizability for all symmetric signatures.)
With this first instance of a dimension “collapse” result in mind, we will now begin to explore Cai/Lu’s remarkable result saying that such a collapse can always occur for nontrivial holographic algorithms.
3. Degenerate Generators
A new notion that Cai/Lu’s two papers on basis collapse introduced in moving beyond size-1 bases was the notion of degenerate and non-degenerate generators and bases. As it turns out recognizers over bases of size more than 1 are indeed more powerful. The saving grace is that such recognizers can only ever appear in conjunction with essentially “useless” generators that give rise to trivial holographic algorithms. Before introducing the actual definitions, let’s get a feel for what such generators would look like.
For starters, generators of arity 1 are pretty useless. Intuitively, without additional nodes to emit particles, there can be no holographic interference, defeating the purpose of using FKT to achieve exponential cancellations. More formally, assume that all the generators in a matchgrid were of arity 1; denote by the number of input nodes of recognizer , and denote by the generator connected to the th input node of . Then the Holant is merely ; in other words, the Holant of all of is the product of the Holants of the subgraphs of containing each recognizer and all generators attached to it. What this tells us is that the particular counting problem in question can be solved merely by looking at its local parts; for instance, if our problem is satisfiability and the recognizers represent the clauses in a CNF, generators of arity 1 would imply that this CNF is read-once so that the total number of satisfying assignments is merely the product of the number of satisfying assignments for each clause.
If arity 1 generators are uninteresting, anything that “decomposes” into such a generator is also uninteresting. In tensor language, we mean decomposition in the sense that the signature tensor of an arity- generator is equal to , where is the signature tensor of an arity-1 generator. In such a case, we could replace with arity-1 generators without changing the Holant, and we’re back in the situation of the previous paragraph.
Definition 1: A generator whose signature tensor has such a decomposition into signature tensors of arity-1 generators is said to be a degenerate generator.
To ignore degenerate generators, we will work only in bases for which at least one realizable tensor is non-degenerate. Cai/Lu’s first step is to give a necessary condition for such a basis. Let be the transformation matrix corresponding to a rank-2 basis of size . Denote by and the Hamming weight of and its parity, respectively.
Definition 2: is a degenerate basis if for all such that is of a particular parity.
We will need the following collection of identities regarding standard signatures, the above-mentioned Grassmann-Plucker identities (also called matchgate identities), which are central to the theory of matchgates. In a future post, we will prove the necessity and sufficiency of these identities and explore the observation by Landsberg, Morton, and Norine that in fact these identities are merely the defining equations for the spinor varieties obtained by Chevalley. For now, we state these identities without proof:
If is the standard signature of a matchgate of arity , then given any , where denotes the bit vector with support at the th bit, denotes the position of the th nonzero bit of , and is the Hamming weight of .
Example 1: If is the standard signature of a generator of arity 4, then one of the matchgate identities must satisfy is (we obtain this from setting and ).
Proof: Assume that for all odd (the proof for even is essentially identical).
Now pick any tensor realizable on ; also call the generator that realizes it . Denoting the standard signature of the generator as , we have by definition that . If the standard signature is already the zero vector, then we’d conclude that and be done. If not, assume for some . In particular, by multiplying our tensor by a scalar, we can assume , and by permuting indices, we can assume .
Denote the th “block” of as . More precisely, this is the matchgate whose output nodes are the output nodes of in the th block. Note that it suffices to show that the standard signature decomposes, in an appropriate sense, as a product of the standard signatures of these blocks. By definition, . We claim the following.
Claim 1: For all ,
Before we prove this, let’s make sure that this implies we’re done. Recall that we need to express as a tensor product of signature tensors of arity-1 generators. Pick a matrix for which is the identity matrix. Then simply define , and we’re done.
Proof: By our assumption that for all odd , we can assume that is even for all , or else the claim is trivially true.
We proceed by induction on . Weight 0 is obvious, and for weight 2, the two nonzero bits have to be in the same block or is odd for two values of and the claim is trivially true.
For weight , the inductive step is basically just some careful bookkeeping using the identities in Lemma~3. Let be the position of the first nonzero bit of (we’ve assumed implicitly that is not all zero, but we could very well done this analysis for any not all zero). We will take in that lemma to be and to be . By pulling out the first term in the matchgate identity and noting that , we get
But for such that lies outside of the first block, , so we’ll ignore those to get , where . The point now is that by restricting our attention to the first block, we can apply our inductive hypothesis to the tensors in each of the summands to conclude that it suffices to show , but one more application of Lemma~3, this time for and gives the desired result.
4. Embedded Basis Theorem
Now that we know what sorts of bases to ignore, we can establish the first crucial step towards the collapse theorem: any transformation matrix for non-degenerate basis has row rank 2! In our discussion below, we will refer to the row of indexed by by .
Proof: Pick any of even weight and of odd weight. Denote by the matrix with rows and , and the matrix with rows and . The claim is that for all possible and defined this way, .
Because is non-degenerate, Theorem~3 tells us that there exists some non-degenerate tensor realizable on . Also call the generator realizing it . Assume first that has an odd number of vertices (we’ll remark how to drop this assumption at the end), so that entries of whose indices are of even weight are zero.
If the arity of is even, then and are zero vectors because their entries are entries in the standard signature of whose indices are of even weight (the sum of an even number of integers of the same parity is even), but has an odd number of vertices. Because we’re assuming is non-degenerate and thus certainly not zero, this implies that and are not invertible, as desired.
If the arity of is odd, then still consists of entries in the standard signature of whose indices are of even weight (the sum of an odd number of even integers is even), so the reasoning above tells us and is not invertible. We can no longer say that , but instead we will “compress” into a nonzero tensor in for which .
Pick any for which and is even (the crucial assumption here is that is non-degenerate). Then let’s replace by so that . Let’s rewrite this; for each , define by so that .
The punch line is that one of these is the we’re looking for, i.e. nonzero, or else we get a contradiction of the fact that is non-degenerate. Indeed, if to the contrary for all , then if , the definition of tells us that , i.e. we can basically “walk” from to by switching off bits in the index at a cost of a factor of at each step. In other words, , so , a contradiction. Likewise, if , we could say that .
5. Collapse Theorem for Generators
Now the end is in sight; we’ve shown there exist 2-vectors and for which every row in is a scalar off from either or . Define the transformation matrix for this basis by where and ; Cai/Lu call this an embedded basis of size 1.
In other words, there is a ton of redundant information in signatures realizable over high-dimensional bases. Is it possible for such a signature to be realizable over the embedded basis? Specifically, we can basically fold into a particular -vector , and the question is whether we can collapse of arity defined above into a generator of arity whose standard signature is this .
Before we jump into proving this in the affirmative, let’s clarify what this is. For any , let denote the scalar for which . Then
First, some simplifying assumptions that will be useful for the collapse theorem for recognizers. Pick and of minimal Hamming distance such that , , and and are nonzero. By simple tweaks to , we can assume that and . Let . Note by minimality of the distance between and that for any between and , . As another piece of notation, denote the th external node in block of by .
Proof: Modify into a new generator as follows: for each block , attach to node a node via an edge of weight and attach to this a node via an edge of weight . Add edges of weight 1 between and for all . Take the output nodes to be all of these .
The point of connecting every other pair of adjacent nodes is as follows: for each , if is not present in the matching, then the edge connecting and must be. The only matchings of the original block which omit necessarily omit , again by minimality of distance between and . In other words, the only such matchings of the original block correspond to . The matching of the new block minus thus includes all the edges connecting adjacent pairs of nodes.
On the other hand, if is present in the matching, then the edge connecting and must be, as well as an edge from the original block that is incident to . The only matchings of the original block containing such an edge correspond to for the same reasons as above.
It thus follows that , and thus has standard signature as desired.
6. Collapse Theorem for Recognizers
We conclude this post by showing a similar collapsing result for recognizers. Let’s first find an analogue of from the previous section. For signature realized over basis by a recognizer that we also call , we know by definition that . But recall that is defined up to a multiplicative constant by , so group the by parity to get .
The analogue of is thus . Our claim is thus:
Proof: The following result essentially finishes the proof.
Theorem 7: The collection of all form the condensed signature of an even matchgate of arity .
Before we see how to prove this (the argument is very similar to that of Theorem 5), let’s see how this can be used to prove Theorem 6. The idea is to attach a copy of to each block of essentially to scale its contents and collapse each block to a single input node. Specifically, for each block, attach in a planar fashion the input nodes to the first input nodes of (you should check that this can be done in a planar fashion) by edges of weight 1, and denote the remaining node of as an input node. Call this new recognizer . Then . But note all the summands for which there exists one such that are zero: if so that the input node at block is included in the matching, then with this node omitted is odd so that an odd number of the remaining vertices must also be omitted for there to exist a perfect matching of , meaning must be even. Likewise, if , we conclude that must be odd, and we’re done.
Proof: We will build the desired matchgate out of . The following claim provides an anchor for our construction: if a standard signature has more than one nonzero entry, there exist entries whose indices are of Hamming distance 2 away from each other (perhaps more on this in another post, but for now, we’ll take this for granted).
Applying this claim to , assume wlog that we can pick entries and . Now for our construction, do nothing to block 1 but call the nodes . Modify block 2 as we did to construct above, but instead of weights and , assign weights and to be decided later. Call the node that we referred to as in the previous proof instead. For blocks , if , then (by the usual minimality argument) is already the only possible assignment of bits to the th block’s output nodes for which there is at least one perfect matching in that block, so don’t change those blocks. If , then we want to ensure that is the only possible assignment, so attach an edge of weight to the output node and pair up vertices to as before.
It’s straightforward to check that is even. By construction, we have for even and odd, respectively, that
Pick and , and we’re done.
In the next post, we will cover matchgate identities as they relate to spinors.