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:
-
;
-
for all
,
;
-
if
then
; and
-
if
and
then
.
The notion of rank in an ordinary vector space obeys these axioms. The rules are:
-
The empty set has rank
;
-
Each vector has rank at most
;
- The rank of a set of vectors can increase only by adding more vectors;
-
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:
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:
-
For the empty graph
, or any graph
with only isolated nodes, we have only the term
, so
.
-
For a circle
, we still have
even though
. The term
still gives
, but
now gives
. Thus
.
-
For the graph
consisting loop at a single node, we have
, so the term for
becomes
. And the term for
is
. So
.
-
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:
-
.
-
.
-
.
-
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
.
-
is the number of perfect matchings of
.
-
is the number of spanning subsets of
(not necessarily spanning trees).
-
is the number of (partial) matchings of
.
-
.
-
(for
).
-
The generating function
for the number
of matchings of size
equals
(valid for real
).
-
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]
I don’t understand the third and fourth paragraph. $S_G$ is a bivariate polynomial depending on a given graph $G$, on variables $x,y$; but then, the next paragraph discusses the ease of computing $S_G(x,y)$ upon conditions on $u,v$ (and their rationality). What are $u,v$?
Thanks. This is fixed now to be S_G(u,v) everywhere—it was a case of last-minute cut-and-paste between versions.