A new class of undirected graphs with quantum relevance

 Cropped from source

Gustav Kirchhoff was a German physicist active in the mid-1800s. He is known for many things, especially for his “Laws” governing voltage and current in electrical circuits. Today we ask whether anything akin to Kirchhoff’s laws can be formulated for quantum circuits.

What may be less known about Kirchhoff is that he was a pioneer in graph theory. He proved Kirchhoff’s Theorem that the number of spanning trees equals the determinant of an associated matrix. This shows that the trees can be counted in polynomial time—a cool result. Here we present a class of graphs arising from quantum circuits and associated operations more complex than determinants.

Our search for new graph-based laws was driven by our work on simulations of stabilizer circuits. We have discussed this recently here and here. The bottom line is this:

A new class of graphs arises in a natural way and holds a key to improving certain quantum simulations.

We call these net-zero graphs. We like to imagine that Kirchhoff would have been interested. We will say more about why after we present the graphs.

Net-Zero Graphs

The new class of graphs comes from a natural counting problem. Consider black/white two colorings (not necessarily proper) of the ${n}$ vertices of a graph ${G}$, and count the number of edges whose two nodes are both colored black, being called B-B edges. Let ${c_0}$ be the count of colorings that make an even number of B-B edges and ${c_1 = 2^n - c_0}$ be the count of colorings that make an odd number of B-B edges. Then ${a(G) = c_0 - c_1}$ divided by ${2^n}$. Now we are good to define “Net-Zero” graphs as follows:

An undirected graph ${G}$ is net-zero if ${a(G) = 0}$.

Furthermore, we can call ${G}$ net-positive if ${a > 0}$ and net-negative if ${a < 0}$. By simple trial and error, the smallest net-zero graph is the triangle graph and the graph made by two triangles sharing an edge is net-zero as well. Here are some connected net-zero graphs of small size:

You might ask why study such labelings of graphs? Why is net-zero an interesting property? An equivalent formulation of ${a(G)}$ was given as “${Z_{H_2}(G)}$” (divided by ${2^n}$) in a 2009 paper by Leslie Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley, as part of a larger enumeration of polynomial-time cases. Their proof works by reduction to the problem of counting solutions to quadratic polynomials modulo 2, whose time we just improved from ${O(n^3)}$ to ${O(n^\omega)}$. Their paper does not mention quantum but does involve Hadamard-type matrices. Thus the short answer is that net-zero captures a type of balancing property that is related to understanding quantum circuits.

Some Examples and Facts

The following elementary facts show how the theory of our graphs takes shape.

Proposition 1 Every cycle graph ${C_n}$ with ${n}$ odd is net-zero.

This follows because every coloring of ${C_n}$ has an even number of B-W edges. Hence the number of monochrome edges is odd, and so complementing the coloring flips the parity between B-B and W-W edges. However, having an odd cycle as an induced graph does not make a graph net-zero. An example of this would be a 4-clique graph. Any subset of vertices of size 3 gives an triangle which is net-zero, but the 4-clique itself is net-negative.

Proposition 2 A graph is net-zero if and only if one of its connected components is net-zero.

This fact is intuitive when we look at the graph as a tensor product over the connected components, so the colorings to each component are independent. Every coloring ${R}$ on nodes outside the net-zero connected component can be easily extended to one coloring ${R'}$ for the entire graph by coloring nodes on the net-zero component, so the difference ${a}$ restricted by ${R}$ is zero.

Now let’s deviate from net-zero graphs. What are some typical net-positive graphs?

Proposition 3 Bipartite graphs are net-positive.

To prove this, let ${V_1, V_2}$ be the two disjoint vertex sets such that each edge connects one node from ${V_1}$ and one from ${V_2}$. If all nodes in ${V_1}$ are set to be white, then there will be zero B-B edges regardless of how ${V_2}$ is acolored, and ${a > 0}$ in this case. Now if any of the nodes, say ${u}$, in ${V_1}$ is colored black, then the number of B-B blacks equals the number of nodes connected to ${u}$ that are colored black, and ${a = 0}$ in this situation by straightforward combination calculation. Hence bipartite graphs are net-positive.

As a consequence, since all trees are bipartite, all trees are net-positive. So is ${C_n}$ for ${n}$ even. Net-negative graphs may seem to be rarer. We invite readers to work out from Pascal’s triangle when the ${k}$-clique is net-negative, net-zero, and net-positive. Congruence modulo ${8}$ is involved.

Other interesting examples come from allowing self-loops. The smallest net-zero graph of this kind is a single self-loop. But a 2-node graph with an edge connecting them and two self-loops is net-negative, and so is a graph of two triangles connected by one edge. Pictorially, these two graphs are:

There is a “local equivalence” between a single self-loop and a triangle: Any self-loop in a graph ${G}$ can be replaced by a triangle using two new vertices, and the resulting graph ${G'}$ will be net-zero if and only if ${G}$ is.

The Quantum Connection

There is a special class of quantum circuits that relate closely to graphs. They use just two kinds of quantum gates: Hadamard gate and the ${\mathsf{CZ}}$ gate. For more on quantum circuits see this elementary post and this more involved post.

Definition 4 Given a graph ${G = (V,E)}$, the corresponding graph state circuit ${C_G}$ involves ${n = |V|}$ qubits and consists of:
• An initial Hadamard gate on each qubit line ${i}$.
• For every edge ${(i,j) \in E}$, a ${\mathsf{CZ}}$ gate connecting lines ${i}$ and ${j}$. The order of placing the ${\mathsf{CZ}}$ gates does not matter.
• A closing Hadamard gate on each line ${i}$.

These circuits are a subset of stabilizer circuits, which we have been discussing. They become equivalent to stabilizer circuits if we also allow so-called phase gates ${\mathsf{S}}$ on single qubits, where they are analogous to a loop or “half-loop” at the corresponding vertex. We will stay with the simpler circuits here. The connection to graphs is expressed by:

Theorem 5 For any graph ${G}$, ${a(G) = \langle 0^n | C_G | 0^n\rangle}$, that is, the amplitude of measuring an all-zero output given an all-zero input. In particular, ${G}$ is net-zero if and only if ${\langle 0^n | C_G | 0^n\rangle = 0}$.

Recognizing Net-Zero Graphs

Theorem 5 implies that whether a graph is net-zero can be decided in ${O(n^\omega)}$ time. The question is, can we improve the time to ${O(n^2)}$, which for dense graphs means linear in the number of edges? The reason why we want to do so is the following further theorem:

Theorem 6 If net-zero graphs of ${n}$ nodes with self-loops allowed are recognizable in ${O(n^2)}$ time, then computing the strong simulation probability ${|\langle 0^n | C | 0^n\rangle|^2}$ for quantum stabilizer circuits ${C}$ is ${O(n^2)}$-time equivalent to computing ${n \times n}$ matrix rank over ${\mathbb{Z}_2}$.

This is proved in section 5 of our paper, which has a duality technique for eliminating the self-loops from phase gates that works for the probability but possibly not for the amplitude. Another way of stating our theorem is:

Theorem 7 Given any ${n}$-vertex graph ${G}$, we can compute ${p(G) = a(G)^2}$ in ${O(n^2)}$ time given only the rank of the adjacency matrix of ${G}$ and the yes/no answer about whether ${a(G) = 0}$.

This result extends to computing the probability of any output of a stabilizer circuit given a standard-basis input. This is why the decision problem for recognizing net-zero graphs is important.

In upcoming posts we will connect net-zero graphs further to ideas of circuit “laws” by defining recursions for ${a(G)}$. These recursions do not give efficient algorithms by themselves, but they connect to a wide theory involving graph polynomials and matroids. That theory includes Kirchhoff’s counting of spanning trees as a special case, and we will be interested in which other cases are polynomial-time feasible. This may position quantum computing as a meeting point for closer connections between work such as this 1997 paper by Andrei Broder and Ernst Mayr on counting minimum-weight spanning trees in ${O(n^\omega)}$ time and the paper by Goldberg et al. mentioned above.

Open Problems

What is the complexity of deciding whether a given ${n}$-vertex graph is net-zero? We know it is at worst order-${n^\omega}$. If it is ${O(n^2)}$, then we obtain a really tight connection between computing matrix rank and computing a quantum simulation probability.

Are there further applications of net-zero graphs?

[gave Kirchhoff his second “h”]

June 14, 2019 7:59 am

I don’t know if this has interesting consequences (and maybe you already know it), but a graph G (loops allowed) is net-zero iff the corresponding quadratic form Q on GF(2)^V (one monomial per edge) is non-identically zero on its radical (rad(Q)=the kernel of the associated bilinear form). This results from the classification of these quadratic forms (e.g. in W. Browder “Surgery on simply connected manifolds” 1972, p54-56, esp. thm III.1.14). More precisely, if Q is identically zero on rad(Q), it has an “Arf invariant”, which coincides with the value in GF(2) most taken by Q. Otherwise, both values are equally likely.
Hope this helps.