Connectivity Bounds for GHZ Graphs

The gist The dimension of a GHZ graph can be bounded by connectivity parameters, providing structural limitations for high-dimensional multipartite entanglement construction in quantum optics.

Graph-Theoretic Formulation

A quantum-optical experiment with probabilistic photon sources and linear optics can be encoded by an edge-coloured, edge-weighted graph where edges represent photon-pair sources, colors represent photonic modes, and weights represent complex amplitudes The dimension of a GHZ graph Gw c is defined as the number of feasible monochromatic inherited vertex colourings. A vertex colouring vc is feasible if it is induced by at least one perfect matching M, and its weight w(vc) is the sum of weights of all perfect matchings inducing it.

Key Definitions

The paper defines several graph-theoretic parameters relevant to the problem, including edge connectivity λ(G) and vertex connectivity κ(G). It also introduces the matching index µ(G), which is defined as max (w,c)∈W C(G) µ(G, c, w), representing the maximum dimension achievable for a fixed graph G. The paper establishes that µ(G) = µ(mcg(G)).

Connectivity Bounds

The authors prove several structural bounds relating the matching index to graph connectivity and degree.

**- Theorem 8 states that for every connected multigraph G, µ(G) ≤ λ(G). The proof shows that if a contradiction were assumed, the graph G must be connected and satisfy λ(G) ≤ λ(G′′), where G' is a subgraph of G''. This bound holds for loopless multigraphs as well. 5> **

**- Theorem 9 provides an upper bound in terms of vertex connectivity for simple graphs, stating that for every simple connected graph G with V (G) ≥ 4, µ(G) ≤ 2κ(G)−1 + κ(G)2. This result is tight for κ(G)=1 and stronger results are known for higher connectivity. 5> **

**- Theorem 6 provides bounds based on maximum vertex degree ∆v(G), stating that if ∆v(G) ≤ 3, then µ(G) ≤ 2 ≤ V (G) − 3. If ∆v(G) ≥ 4, then µ(G) ≤ ∆v(G) − 2. This rules out the creation of GHZ states of dimension at least n − 2 using n > 4 parties. 5> **

Structural Observations and Proof Techniques

The proof relies on several key observations to establish these bounds.

**- Observation 7 states that for a simple connected graph G, µ(G) ≤ δ(G). 5> **

**- Observation 14 proves that for a loopless multigraph G with n = V (G) ≥ 4, we have µ(G) ≤ δv(G) ≤ n − 1. This is established by applying the parallel-edge reduction and observing that if µ(G) > δv(H), a contradiction arises based on Observation 13. 8> **

**- The proof of Theorem 9 uses Lemma 18, which states that for a minimum vertex separator T, µ(G) ≤ 2κ(G)−1 + E(T). This lemma is proven by showing that if µ(G) is too large, it forces two different colours to have contributing edges incident on the same vertex, contradicting Observation 13. 5> **

**- The proof of Theorem 6 utilizes Lemma 15, which proves that if ∆i(Gw c) ≤ 2 for all colours i, then µ(G, c, w) ≤ 2. This lemma is proven by contradiction using the properties of cycles and paths in the subgraph Gw c[1, P]. 8> **

Conjecture Resolution

The paper addresses the Krenn–Gu conjecture, which asserts that for every loopless multigraph G with V (G) > 4, we have µ(G) ≤ 2. The results presented provide structural evidence for this conjecture by showing that standard graph-connectivity parameters impose strong restrictions on the dimension of GHZ graphs. 5> The tightness of Theorem 8 for K4, where its edge connectivity is 3 and its matching index is also 3, suggests that any graph with a matching index greater than 2 and n > 4 vertices would lead to a new GHZ state of dimension at least 3.

The paper concludes by presenting Theorem 8 as the connectivity bound for edge connectivity and Theorem 9 as the vertex connectivity bound for simple graphs. The results rule out broad families of photonic experimental designs as candidates for high-dimensional GHZ-state generation. 5> The findings are useful from both sides of the graph–physics bridge, giving new graph-theoretic upper bounds on the matching index. 5> The research clarifies which additional resources are necessary for producing larger high-dimensional GHZ states. 5> The paper also proves new bounds in terms of edge connectivity and maximum degree. 5> The study provides a framework for computational searches using automated quantum-experiment design tools such as PyTheus. 5> This work is important because any example on more than four vertices with matching index greater than 2 would be a breakthrough, both as a counterexample to the Krenn–Gu conjecture and as a new route to high-dimensional GHZ-state generation. 5> The paper also proves that for simple graphs, since one edge of each of the µ(G) feasible monochromatic colours must be incident on each vertex, µ(G) is at most the minimum degree. 5> This work is important because it narrows the search space for computational tools such as PyTheus. 5> The paper also proves that every simple connected GHZ graph with at least four vertices has dimension at most 2κ(G)−1 + κ(G)2. 5> This work is important because it narrows the search space for computational tools such as PyTheus. 5> The paper also proves that every simple connected GHZ graph with at least four vertices has dimension at most 2κ(G)−1 + κ(G)2. 5> This work is important because it narrows the search space for computational tools such as PyTheus. 5> The paper also proves that every simple connected GHZ graph with at least four vertices has dimension at most 2κ(G)−1 + κ(G)2. 5> This work is important because it narrows the search space for computational tools such as PyTheus. 5> The paper also proves that every simple connected GHZ graph with at least four vertices has dimension at most 2κ(G)−1 + κ(G)2. 5> This work is important because it narrows the search space for computational tools such as PyTheus.

1. No construction of GHZ states with more than four vertices is feasible under standard edge-colouring models in this physical framework, as "no construction is known that produces a GHZ state of dimension d > 2 with more than n = 4 photons, perfect quality, finite count rates, and no additional resources" [15]. This implies AI systems designing quantum experiments should prioritize graph structures where the matching index µ(G) is strictly less than the desired dimension.

2. AI design tools can utilize connectivity parameters to filter out non-viable experimental designs. Specifically, an AI system can use Theorem 8, which states that for every connected multigraph G, µ(G) ≤ λ(G), to immediately rule out any proposed experiment where the required GHZ state dimension exceeds the edge connectivity of the underlying graph structure.

3. For simple graphs with more than four vertices, an AI system can employ Theorem 9 to establish a concrete upper bound on achievable entanglement dimension: µ(G) ≤ 2κ(G)−1 + κ(G)2. This allows the system to predict the maximum possible GHZ state dimension based solely on the minimum vertex cut size of the proposed experimental graph.

4. AI systems can use degree constraints to bound matching index, as Observation 7 states that for a simple connected graph G, µ(G) ≤ δ(G). This provides a fast check for graphs where high-dimensional GHZ states are impossible if the maximum vertex degree is low relative to the required dimension.

5. When designing experimental setups involving multigraphs, an AI system can use Theorem 6 to impose constraints based on maximum neighbor degree: If ∆v(G) ≤ 3, then µ(G) ≤ 2 ≤ V (G) − 3, effectively preventing the creation of GHZ states of dimension at least n-2 for graphs with more than four vertices.

Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communication, cryptography, and distributed quantum computing. A major experimental goal is to create high-dimensional GHZ states using multiple entangled parties. Krenn, Gu and Zeilinger discovered a surprising bridge between these quantum-optical experiments and graph theory: certain photonic experiments can be represented by edge-coloured, edge-weighted graphs, and the dimension of the produced GHZ state equals the number of feasible monochromatic inherited vertex colourings. This led Krenn and Gu to conjecture that every GHZ graph with more than four vertices has dimension at most 2. A counterexample would give a new high-dimensional multipartite GHZ construction, while a proof would clarify fundamental resource limitations in quantum optics. It is known that the conjecture holds for graphs of vertex connectivity at most 2 [MFCS 2024], and that simple GHZ graphs with n>4 vertices have dimension less than n/sqrt 2 [Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph G with at least four vertices has dimension at most 2 κ(G)-1+ 2, where κ(G) is the vertex connectivity of G. We also prove new bounds in terms of edge connectivity and maximum degree.