A Matroid-Quantum Connection

With tighter links between notions of rank?

Composite of src1, src2 (our congrats)

James Oxley and Geoff Whittle are mathematicians at LSU and Victoria University (Wellington, New Zealand), respectively. They have written many joint papers on matroid theory, but none on quantum computing.

Today we observe that they really have indirectly written a paper on quantum computing.

Their paper, “A Characterization of Tutte Invariants of 2-Polymatroids,” has implications for quantum complexity theory. It introduced a polynomial where is a graph and are numbers. Like many polynomials defined on graphs this one is in general hard to compute—it is -hard, so if it is polynomial time computable, then surprising stuff happens.

The same paper observes that is easy to compute when

However, a 2006 paper by Steve Noble proves that all other rational cases are -hard. Our work finds easy cases in another family where and is a rational multiple of . This result goes through quantum complexity theory.

It is interesting to note that quantum computations welcome complex numbers such as . In mathematics insights to behavior of real functions are often found when we extend them to the complex functions. A beautiful example to compare is that the behavior of

is best understood by noting that can be zero at .

Matroids and Polymatroids

In order to best understand the above results it is helpful to look at matroids and generalizations. Matroids are a bit scary, since they seem quite abstract. But that is wrong. The matroid concept is a natural generalization of the notion of rank in an ordinary vector space.

Let’s take a look. A matroid is defined by a set and a function from finite subsets of to that obeys the following rules:

1. ;

2. for all , ;

3. if then ; and

4. if and then .

The notion of rank in an ordinary vector space obeys these axioms. The rules are:

1. The empty set has rank ;

2. Each vector has rank at most ;

3. The rank of a set of vectors can increase only by adding more vectors;

4. Suppose that adding to a set increases the rank. Then also increases the rank of any subset of . Or if is independent of a set of vectors , then it is independent of any subset of .

The definition of a polymatroid simply wipes out rule 2. OK, a -polymatroid replaces it by the rule that for all singleton sets have . An important kind of 2-polymatroid springs from the following idea:

The “-rank” of a subset of the edges in a graph is the number of vertices collectively touched by edges in .

In a simple undirected graph, every edge has -rank 2. In graphs with self-loops, however, the loops have rank . We can also allow the universe to include members of -rank . Those are visualized as loops without a vertex and called circles. We could also visualize edges of rank that stick out from a vertex into empty space, but those are formally the same as loops at . This defines a graphic(al) 2-polymatroid .

The theory of polymatroids ignores the notion of “vertex” apart from the definition of the rank function . Hence all graphs composed of isolated vertices define the empty 2-polymatroid. To preserve the distinction, we define an m-graph to be a graph with circles allowed. The empty m-graph is denoted by and called a “wisp.” Every m-graph specializes to a unique graphical polymatroid but we can include isolated nodes when thinking of it as a graph (plus circles).

Explosion and Contraction Again

We revisit the definition of “exploding” an edge in a graph from the previous post in this series:

• If there are an odd number of edges incident only to and/or , then and become a circle and a wisp, else they become two wisps.

• Any other edge incident to or from another vertex becomes a loop at .

If we ignore vertices, then the rank function of the resulting m-graph is such that for all subsets of its edge set ,

One can verify that the “explosion” description obeys (1). Glancing at our picture helps—we have varied the one in the previous post by showing how one exploded node becomes a wisp while the loop at the other leaves a circle:

The equation (1), however, is more fundamentally natural. The simple extension

defines the matroid contraction by any subset of . When , it supersedes the graph-theory notion of contraction in matroid contexts. Since we are talking about both, we will write for the matroid version. The notation conveys that the edge gets deleted emphatically.

The Polynomial

In a previous post we derived a recurrence for the amplitude in terms of explosion. The presence of circles and use of the function now allows us to write it as:

We can omit the “” from the previous version because the circles keep track of this. The rule is valid even when is a self-loop, using . The following is thus a complete basis:

• For a wisp or isolated node , .

• For a circle , .

• If is the disjoint union of and , then .

To get more mileage out of this, we want to emulate William Tutte’s idea and define a polynomial whose evaluation at gives , and whose other evaluations may give more information. Without further ado:

Definition 1 For an m-graph , define its amplitude polynomial inductively by:

• , if consists of isolated nodes, circles, and any number of wisps.

• For any edge ,

  

Recall if is a loop, else . When consists of a single node with a loop, the recursion gives . When it is a single edge between two nodes, we get

If we have a single node with two loops, something portentous happens. Exploding one of the loops leaves a circle. Removing still leaves one loop. So we get:

This agrees with the value on one isolated node. Similarly, if has just a double edge between two nodes and , then one edge becomes a circle upon exploding the other edge, so recursing on the other edge makes

Thus the double edge gives the same result as having two isolated nodes. The upshot is that equation (2) naturally treats edges modulo two. We can recurse on a non-edge as if it were a double-edge, and the circle left by the explosion (i.e., by the matroid contraction) becomes a multiplier on the entire remainder of that branch of the recursion. The circle thus becomes a placeholder for calculating phase flips and cancellations, which is why we believe the matroid notions are useful in analyzing quantum processes.

It may not be obvious, however, that is well-defined when has more than one edge. That is, does it come out the same for any order of choosing edges for the recursion? We will prove this by connecting to the polynomial mentioned above.

Relation to the Rank-Generating Function

The original non-recursive definition of the rank-generating function of a graphical 2-polymatroid is:

We compute some basic cases:

1. For the empty graph , or any graph with only isolated nodes, we have only the term , so .

2. For a circle , we still have even though . The term still gives , but now gives . Thus .

3. For the graph consisting loop at a single node, we have , so the term for becomes . And the term for is . So .

4. For with a single edge between two nodes, .

Note the symmetry in and between cases 2 and 4 in particular, which could be brought out more by discussing how (graphical poly-)matroids foster higher notions of duality than graphs do. Our theorem breaks this symmetry, but perhaps there is a deeper underlying law that would restore it:

Theorem 2 For any m-graph with nodes, of which are isolated, and all , taking ,

Proof: Call the right-hand side of (4). Note first that if consists only of isolated nodes then so the right-hand side becomes

Now we verify the other base cases:

1. .

2. .

3. .

4. For with a single edge between two nodes, .

To verify the recursion, we note facts observed by Oxley and Whittle as consequences of (3):

• (a) If is a loop at a vertex with other incident edges, so and , then

  

• (b) If is a pendant edge, i.e., between a node of degree 1 and a node of larger degree, so and , then

  

• (c) If is an edge between nodes of degree at least , so and , then

  

Every connected graph other than those we put in our basis has an edge that falls into one of these three cases. So we can prove (4) by induction on them. The details convey why we need to use the particular value but are otherwise straightforward and tedious, so we’ve put them in a longer PDF version. Since the equation (3) for involves no recursion, this also proves that the recursive definition of is confluent.

Note how the sum in the case (c) echoes the sum defining the Tutte polynomial, but with “explosion” in place of ordinary graph contraction. A more salient difference is that whereas the Tutte polynomial is the same on all -vertex trees, differs on them.

What Does It All Mean?

As remarked in Noble’s paper, Oxley and Whittle noted the significance of a host of specializations of the polynomial. We suppose has nodes with isolated, so , and we put . The first two presume .

1. is the number of perfect matchings of .

2. is the number of spanning subsets of (not necessarily spanning trees).

3. is the number of (partial) matchings of .

4. .

5. (for ).

6. The generating function for the number of matchings of size equals (valid for real ).

7. The generating function for the number of subsets of spanning vertices equals (again valid for real ).

Also interesting is that if and we delete each of the edges independently with probability , then the probability that the deletions did not cause any isolated vertices is

Of course, this is classical probability. What interests us here is the import of for quantum amplitude and probability. We have already observed in previous posts that gives the amplitude for an outcome in a special kind of quantum circuit. This means that gives the same information, where .

We are curious about is the significance of for other values of besides . The complex value takes us outside the real-valued domain of Noble’s paper. His proof that most real cases are -hard to compute does not extend because , which causes a denominator in his proof to vanish. Thus and hence may be polynomial-time computable for various other real .

The specialization (times other easily-computed factors) does not seem to intersect with any of the above cases. Hence the field is wide open for finding new interpretations of it. Whatever we find, however, is bound to relate to the analysis of quantum circuits. It might help fulfill the aim in our post drawing analogy to Gustav Kirchhoff’s laws for electrical circuits.

Open Problems

How useful is the matroid-based framework for analyzing graph entities associated to quantum circuits? Can we say more about the significance of for other particular values of ?

We had thought to imitate how the Tutte polynomial has base monomials for graphs composed of “bridge” edges and loop edges at otherwise-isolated nodes. One can base a polynomial on monomials

for composed of isolated nodes, disjoint single-node loops, circles, and “wisps.” The recursion is the same:

The point is that in the explosion case, the inclusion of the factors for wisps and circles (namely, if the explosion leaves two wisps, if it leaves a wisp and a circle, or for two circles) keeps homogeneous of degree for an -vertex graph. The conditions for this recursion to be confluent, however, essentially leave something equivalent to with as a homogenizing variable. In particular, this idea appears not to yield a two-variable polynomial that gives more leverage.

[made S_G(u,v) not S_G(x,y) consistent at top]