Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings

We show a surprising link between experimental setups to realize high-dimensional multipartite quantum states and graph theory. In these setups, the paths of photons are identified such that the photon-source information is never created. We find that each of these setups corresponds to an undirected graph, and every undirected graph corresponds to an experimental setup. Every term in the emerging quantum superposition corresponds to a perfect matching in the graph. Calculating the final quantum state is in the #P-complete complexity class, thus it cannot be done efficiently. To strengthen the link further, theorems from graph theory—such as Hall’s marriage problem—are rephrased in the language of pair creation in quantum experiments. We show explicitly how this link allows one to answer questions about quantum experiments (such as which classes of entangled states can be created) with graph theoretical methods, and how to potentially simulate properties of graphs and networks with quantum experiments (such as critical exponents and phase transitions).

Figure 1

(A) An optical setup which can create a 3-dimensional 4-photon GHZ-state with the method of entanglement by path identity [8]. It consists of three layers of crystals, and in between there are variable mode- and phase-shifters (depicted in grey). (B) The corresponding graph with four vertices (one for each path) and six edges (one for each crystal). Every layer of crystals leads to a four-fold coincidence count. (C) These correspond to three disjoint perfect matchings, or 1-factors, in the graph. (D) An optical setup for creating 3-dimensional entanglement with six photons. (E) The corresponding graph. (F) It has four perfect matchings, thus the corresponding quantum state has four terms. One terms comes from each of the three layers (the GHZ terms), and one additional term comes from different layers (the Maverick-term, with orange background). For that reason, the resulting quantum state has not the form of a GHZ state. In the Supplemental Material [17], we show how to construct the experimental setup from a given graph.

Figure 2

Application of the bridge between quantum experiments and graph theory: As a concrete example, we ask which $d$-dimensional $n$-photon GHZ states can be created experimentally with this method. The idea of the proof is to construct a graph starting with $n$ vertices without edges. We try to maximize the number of disjoint perfect matchings (PMs) by adding appropriate edges to the graph [24]. In disjoint PMs, every edge appears in only one perfect matching. The example in the figure is for $n=8$, but the proof works for any arbitrary even $n$. Step I: In $\mathbf{A}$, we add the first PM to a set of eight vertices (green). Step II: In $\mathbf{B}$, we add more edges to construct a second PM (red). Whenever the new PM, together with the first (green) PM, creates more than one cycle (here: edges 1-6,6-7,7-8,8-1; and 2-3,3-4,4-5,5-2), we immediately find an additional Maverick PM (indicated with white boundary, edges 1-6,2-3,4-5,7-8). Thus the graph cannot represent a GHZ state (as a GHZ state has only disjoint perfect matchings). The only choice for the second PM is to create together with the first PM one cycle that visits every vertex—a Hamilton cycle, shown in $\mathbf{C}$. Hamilton cycles consist of 2 PMs, and therefore correspond to 2-dimensional GHZ states. It can be arbitrarily large, and thus there can be arbitrarily large $n$-photon 2-dimensional GHZ states. Step III: Starting with the Hamilton cycle, we try to add a third PM with blue edges. In $\mathbf{D}$, we observe that if the new edge splits the graph into an even number of vertices (upper part: vertices 7,8; lower part: vertices 2,3,4,5), we always find a new Maverick PM. It consists of the new edge (here: 1–6) and edges from the Hamilton cycle (here edges 2-3,4-5,7-8). We learn—as we require only disjoint perfect matchings—no edge of a new PM should split the graph into even numbers of vertices (otherwise Maverick PMs appear). Finally, in $\mathbf{E}$ we try to add edges that split the graph into an odd number of vertices. We observe that in every additional PM there are at least two neighboring edges that intersect (neighboring edges start from consecutive vertices; here—shown in blue—they start at vertex 1 and vertex 2). This pair always forms a new Maverick PM with additional edges from the Hamilton cycle (here: 1-5,2-6,3-4,7-8). There is one exception for the case of $n=4$: There can be a 3rd disjoint PM, because a Maverick PM needs at least 3 edges (2 blue ones and one from the Hamilton cycle). Therefore, a 4-photon 3-dimensional GHZ state can be created, while for $n>4$, GHZ states can only be created with $d=2$.

Figure 3

Random graph or quantum random network—and its connection to quantum experiments. (A) A random graph with 8 vertices and 14 edges. (B) The perfect matchings corresponding to the random graph. (C) They can be calculated with the matrix function Hafnian, which is a generalization of the permanent. Both are very expensive to calculate. (D) The corresponding quantum experiment. Each of the terms in its quantum state corresponds to a perfect matching in the graph. It can also be seen as a quantum random network, to study network properties in the quantum regime.

Figure 4

A theorem from graph theory: Hall’s marriage theorem (A) For a bipartite graph with equal number of elements in $X$ and $Y$, Hall’s theorem gives a necessary and sufficient condition for the existence of a perfect matching. That happens when for every subset in $W\in X$, the number of neighbors in $Y$ is larger or equal than $|W|$. In the example graph, the subset of $X$ consisting of the vertices c, e, g (indicated in red) has only two neighbors in $Y$ (d, f—indicated in green), thus there cannot be a perfect matching. (B) For quantum experiments, the analog question is whether there can be $2n$-fold coincidences, given that $n$ crystals emit photon pairs. When the two photons are distinguishable (which corresponds to a bipartite graph), $2n$ folds can only happen when for every subset $W$ of signal photon paths the number of connected idler paths is larger or equal than $|W|$. In the example, the subset of signal photon paths (c, e, g—depicted in red) has only two corresponding idler paths (d, f—depicted in green), thus there cannot be a 10-fold coincidence count.