Quantum Graph Theory

Composite crop of src1, src2, src3

Axel Dahlberg, Jonas Helsen, and Stephanie Wehner are researchers from QuTech associated to Delft Technological University. They have produced five wonderful and elegant recent papers that update the theory of quantum graph states.

Today we introduce some of what their papers are about.

We covered material related to graph states a few times before the pandemic, going in the direction of matroid theory. The work by Dahlberg, Helsen, and Wehner stays with ordinary simple undirected graphs.

Wehner was the advisor of Dahlberg and Helsen, and she was in turn a student of Harry Buhrman at CWI Amsterdam, where Helsen is now. Wehner’s CV lists one of her jobs prior to graduate study as “Hacker” for ITSX BV in Amsterdam, a fact used in the lead sentence in a 2018 news feature in Nature on work toward a quantum Internet. Both that and her Wikipedia page call her a theoretical physicist. We would claim her for theoretical computer science.

Amid the entanglement of fields, a key point is that simple problems about simple graphs govern blueprints for vast networking technology that we can now only conceive. Is all this simple enough to introduce in a short post? We’ll see.

Graph States

The quantum gates most commonly used to define and operate on graph states are the one-qubit Hadamard and Pauli gates

together with the controlled- and controlled-NOT gates, which are shown together with their usual quantum circuit notation:

Just because we like to be different, we will represent edges of undirected graphs by the following two-qubit gate instead:

We don’t know a common name, but the gate is provided by Craig Gidney’s popular Quirk quantum circuit simulator with the following logical notation and enjoys the identities shown here:

The third identity means that is the same as under the change of basis by the Hadamard transform. Graph states are usually defined by an initial -qubit Hadamard transform of all-zero input followed by placing a gate between qubits and for each edge in the graph; the order does not matter because gates commute no matter how placed. Instead, we have dispensed with the initial transform and simply place an for each edge. Here are our circuits for the star graph on nodes, the -cycle graph , and the complete graph , respectively:

Putting an gate anywhere on line is the same as flipping the input bit and adds a self-loop to node in the graph. A double edge between two nodes is the same as a non-edge; only the parity matters. The gates , , and all commute. Both and can be represented as for some Hermitian matrix of rank whose diagonal form is all-zero except for a single entry. The matrix eloquently speaks “one unit of interaction.”

Entanglement Examples

If we start with the graph with just one edge on nodes, then the quantum graph state is given by the first column of the matrix above: . If we follow with a single Hadamard gate on line , then the state becomes

This is the Bell pair. Named after John Bell, which is the simplest entangled state. If we say that the first qubit is held by “Alice” and the second by “Bob,” then Alice and Bob are entangled. For any , the state , which is called the GHZ state after Daniel Greenberger, Michael Horne, and Anton Zeilinger, has the maximum possible entanglement among qubits by several quantitative measures.

Now let us add interactions with two more qubits held by “Charlie” and “Donna” in the form of the cycle graph :

Questions that we can ask include:

1. Are Alice and Bob entangled? Or Alice and Charlie?

2. Do they have less entanglement than a Bell pair?

3. Do the four parties together have as much entanglement as the -qubit GHZ state?

The answers to the first two questions are, “it depends.” Absent any knowledge of what Charlie and Donna do with their qubits, the status of Alice and Bob is conveyed by the density matrix resulting from the partial trace-out of Charlie and Donna. Here is a direct shortlink to view it on Quirk under its native “little-endian” qubit order (Donna uppermost), or this to view with Alice uppermost. This gives the identity matrix, which represents the completely mixed state of two qubits, by which Alice and Bob have two independent classical coins with no entanglement. Regardless of what unitary operations Charlie and Donna do unto themselves, the trace-out remains the same.

However, if Charlie and Donna measure their qubits, different effects can occur to Alice and Bob depending primarily on how they measure, and secondarily on the measurement results they get. If they both immediately measure in the standard basis, then Alice and Bob “collapse” to one of the four two-qubit basis states, as can be viewed on Quirk using the post-selection widgets “” and “.”

Yet if Charlie and Donna each apply one Hadamard gate before their measurement, then Alice and Bob get , or something they can make equal to by applying one of the Pauli matrices on being told Charlie’s and Donna’s outcomes. A further Hadamard by Alice or Bob then creates the Bell pair, as viewable here (or here for a big-endian view).

To ask about Alice and Charlie, it is most convenient to re-order so that Donna and Bob are consecutive:

Tracing out Donna and Bob now leaves the density matrix . This means that Alice and Charlie have classical coins that are fully correlated, but not quantum entanglement. However, if just one of Bob or Donna applies one Hadamard gate before measuring, Alice and Charlie become a Bell pair (perhaps after a local tweak like the -gate here).

We can pose the same questions for other graphs. On the third, given the star with Alice at the center, let her apply one Hadamard gate to her qubit. The result is the GHZ state.

Given , we can do the same by involving two more gates:

These obey the identities , , and so

Thus is also written as by Quirk. Applications of these along with Hadamard and the Pauli matrices on any one qubit generate the local Clifford group. Now let three of the qubits do while the fourth does followed by . The result is again the GHZ state. The same tricks work with and for any .

Can we get the GHZ state from the cycle ? The answer is no. This leads into the basic quantum connection to graphs.

The Neighborhood Flip

The upshot is that because the graph states of and the star can each produce the GHZ state, they can produce each other. The graph operation that does this is to choose one node , and for every pair of neighbors of :

• if and are not connected, connect them by an edge;

• if and are connected, delete the edge between them.

Here are pictures for , the second showing how Donna could connect Alice and Charlie in the cycle graph. This neighborhood flip operation is self-inverse. It cannot disconnect a node, and so defines an equivalence relation on connected graphs.

If Alice is chosen in the graph at right after Donna’s flip, then Charlie is disconnected from Bob and Donna but Bob and Donna are connected. The edges to Alice do not change, so we get a triangle of Alice-Bob-Donna plus the edge Alice-Charlie.

The quantum circuit rule for is simple:

• add an inverse- gate on qubit line ;

• for each neighbor of , add a gate on line .

What gives this power is that every local quantum transformation of graph states arises this way. This was proved in a 2004 paper by Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor, among several related papers leading to a long 2006 synthesis.

Theorem 1 A graph state can be converted to a graph state by local Clifford operations if and only if .

The star and complete graphs go only to each other, though the center of the star can be moved to any vertex. This answers the last section’s question about :

Proposition 2 and are in different equivalence classes, and these are the only two classes among connected graphs on four nodes.

Hence the entanglement in is different from that of the four-qubit GHZ state from the standpoint of local Clifford conversions. It is further known that no local unitary operations can convert them.

Measurement and Vertex Deletion

With our version of graph states , applying one Hadamard to qubit , measuring in the standard basis, and post-selecting on yields for the graph obtained by deleting vertex . If the outcome is , then is obtained by further applying to every neighbor of . (Measuring in the basis and then applying on line has similar result. With the original version of graph states, use on neighbors of instead.)

The new papers, in particular this by Dahlberg and Wehner, complete the above-mentioned earlier work to prove the following extension of Theorem 1. Write and call a vertex minor of if can be obtained from by neighborhood flips and vertex deletions. The deletions can without loss of generality be done last.

Theorem 3 An -qubit graph state can be converted to a graph state by local Clifford operations, standard-basis measurements, and classical communication of measurement results, if and only if .

In our example of entangling Alice and Charlie in , Donna’s applying and then measuring left Alice and Charlie connected only to Bob. Bob’s not applying before measuring was the same as applying it twice, first to flip Alice and Charlie into being connected, and then to drop himself out. Donna and Bob still needed to communicate their measurement results in order for Alice and Charlie to choose exactly the operations that produce the state .

This opens the possibility of creating new entanglements by adding a node, flipping some neighborhoods, then deleting it. For example, neither nor can work itself into two entangled pairs by local means, because cannot disconnect a graph. Suppose we invite Eve not to eavesdrop but to slot between Bob and Charlie in the path graph shown at left below.

Bob and Charlie do neighborhood flips that connect Eve to Alice and Donna as well. This yields the bowtie graph in the middle. Then Eve can measure and step away, leaving Alice-Bob and Charlie-Donna as separate couples.

The New Hardness Results

In 1991, before the quantum connection was visible, André Bouchet showed that whether two -vertex graphs are equivalent under is polynomial-time decidable. The corresponding quantum problem about graph states is part-and-parcel with simulation questions for the larger class of stabilizer states, which we have also covered here and here.

But once deletion is allowed, Dahlberg, Helsen, and Wehner show that the feasible picture changes—at least when the target graph is on a fixed set of vertices.

Theorem 4 Given and with (but not necessarily ), the problem of whether is -complete. It remains complete when is a star or consists of multiple disjoint edges.

The disjoint edges are on prescribed pairs of vertices. They also show hardness when both graphs are circle graphs, a subclass on which many other -complete problems become polynomial-time decidable. In consequence:

Theorem 5 It is -hard to decide whether an -qubit graph state can be converted into a GHZ state on a given subset of the qubits, or into Bell pairs on designated pairs of qubits, by local unitary operations, measurements, and classical communication.

The fifth paper contains a further surprise. Even though the decision problem of belongs to (indeed, to a subclass defined by parity and linear algebra), the associated counting problem is hard.

Theorem 6 Given a graph , counting the number of labeled graphs equivalent to under is -complete.

Again the completeness holds under restriction to circle graphs, which furnish machinery for the proof that connects to other linear- and group-algebraic constructs important to quantum mechanics.

What does the hardness mean? One takeaway is that shortcuts with multi-variable polynomials that suffice to simulate quantum graph-state and stabilizer circuits may not extend nicely to describe entanglement and how it is affected by measurement. Another is that various other problems about quantifying and channeling quantum entanglement are likely to be hard as well. To pick up one theme we took from Lance Fortnow in our previous post, the decision hardness channels questions about approximate optimization and heuristic most-case solving. Can entanglement be moved around a network and delivered to clients on demand, at what practical cost and loss of quantum coherence? I’ve tried to hint at such wider quantitative problems in the third section.

Open Problems

What other areas of graph theory may be enriched by the quantum connection? The role of vertex deletion makes us think of the graph reconstruction conjecture in particular. Can results on minors in this 2019 dissertation extend to show that the relation is reconstructible? There are other uses of graphs in quantum mechanics, even a novel about them.

For a footnote, the double- construction can be added to the Qcircuit.tex macro package by including the two lines

\newcommand{\controlplus}{{\xy ="i","i"-;"i"+ **\dir{-}, "i"-;"i"+ **\dir{-},"i"*\xycircle{} \endxy}}
\newcommand{\ctrlp}[1]{\controlplus \qwx[#1] \qw}


and using \ctrlp the same way as \ctrl with \targ and a numerical argument.

[a couple of minor word changes; clarified the scope of proposition 2 and added a note afterwards in view of comment by GK below]