Source-linked AI summary
Connectivity Bounds for GHZ Graphs
L. Sunil Chandran, Rishikesh Gajjala
TL;DR
The paper addresses whether GHZ graphs with more than four vertices can have dimension above 2, a question tied to high-dimensional GHZ-state generation. It proves bounds using graph connectivity and degree, including a vertex-connectivity bound for simple connected graphs.
Problem
The Krenn–Gu conjecture asks whether every GHZ graph with more than four vertices has dimension at most 2, a question whose resolution would clarify limitations of the photonic model.
Source: §1.1 · p. 4Method
The paper proves graph-theoretic upper bounds on matching index using connectivity and degree parameters.
Source: §1.3 · p. 5Results
For simple connected graphs, the paper establishes a vertex-connectivity upper bound and shows that matching index is at most minimum degree.
Source: §1.3 · pp. 5–6Takeaways & Limitations
The bounds restrict which graph families in this model can serve as candidates for high-dimensional GHZ-state generation.
Source: §1.3 · p. 5For higher vertex connectivity, the optimal dependence remains open, and it is unknown whether a polynomial bound in κ(G) holds.
Source: §1.3 · p. 6
Abstract
from arXiv · showhide
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^{\kappa(G)-1}+\binom{\kappa(G)}{2}$, where $\kappa(G)$ is the vertex connectivity of $G$. We also prove new bounds in terms of edge connectivity and maximum degree.
1 Introduction
The paper frames high-dimensional GHZ-state generation as a graph problem about weighted perfect matchings and monochromatic inherited colourings. It studies the Krenn–Gu conjecture and proves connectivity- and degree-based restrictions, alongside new bounds for small simple graphs.
1 Introduction
- Photonic experiments can be encoded by edge-coloured, edge-weighted graphs: edges represent photon-pair sources, perfect matchings represent successful detections, and feasible monochromatic inherited colourings determine GHZ dimension.The edge colour represents a photonic mode, while edge weights represent complex amplitudes.Source: §1 · pp. 1–2, §1.1 · pp. 2–3
1.1 Problem definition
- The Krenn–Gu conjecture asserts that every loopless multigraph with more than four vertices has matching index at most 2, while a counterexample would yield a higher-dimensional GHZ construction.The matching index is defined for the fixed graph, without adding parallel edges.Source: §1 · p. 2, §1.1 · p. 4
1.3 Our Results
- The paper gives an upper bound in terms of vertex connectivity for simple connected graphs and shows that the matching index of a simple connected graph is at most its minimum degree.It also establishes bounds in terms of edge connectivity, including for loopless multigraphs.Source: §1.3 · pp. 5–6
- For simple graphs, the matching index is at most 2 on six vertices and at most 3 on eight; the optimal dependence on vertex connectivity above 2 remains open.The paper also states that disconnected graphs with a perfect matching have matching index 1, and those without one have matching index 0.Source: §1.3 · p. 6
2 Preliminaries
The preliminaries develop reductions and factorization properties that preserve the graph’s GHZ dimension, and use local edge constraints to bound the matching index by minimum degree.
2 Preliminaries
- Removing every edge in a redundant colour class preserves the GHZ graph and its dimension.A redundant class contains no monochromatic perfect matching; its removal leaves the number of monochromatic vertex colourings of weight 1 unchanged.Source: §2 · p. 7
- The weight of an inherited colouring factors across its colour classes and across connected components of a monochromatic induced subgraph.The factorization follows from taking disjoint unions of the corresponding monochromatic perfect matchings.Source: §2 · p. 7
- An edge is contributing when the total weight of same-colour perfect matchings containing it is nonzero.If that total is zero, the edge is non-contributing.Source: §2 · p. 7
- Replacing same-colour parallel edges by one edge weighted by their summed weights, or deleting a zero-sum bundle, preserves inherited-colouring weights without increasing degrees.The reduction leaves feasible monochromatic colouring weights unchanged and produces at most one edge of each colour between a vertex pair.Source: §2 · pp. 7–8
- After parallel-edge reduction, edges of different colours between the same vertex pair must both be non-contributing.Otherwise a non-monochromatic inherited colouring would have nonzero weight.Source: §2 · p. 8
- µ(G) ≤ δv(G) ≤ n −1 for loopless multigraphs with n ≥4.The bound follows because each feasible monochromatic colour needs a contributing edge at every vertex, while different contributing colours cannot share a neighbour.Source: §2 · p. 8
3 Maximum neighbour-degree: Proof of Theorem 6
The proof bounds matching index using maximum neighbour-degree, first establishing the bound of 2 when that degree is at most 3. For larger maximum degree D, it shows the matching index is at most D − 2.
3 Maximum neighbour-degree: Proof of Theorem 6
- For |V(G)| > 4 and maximum neighbour-degree at most 3, the matching index is at most 2.The proof assumes three feasible colours and uses the degree limit to force distinct-colour contributing edges onto already occupied neighbours, contradicting Observation 13.Source: §3 · p. 9
- The proof removes parallel edges and redundant colour classes while preserving dimension and not increasing neighbour-degrees.This reduction lets the argument assume all remaining colour classes are non-redundant.Source: §3 · p. 9
- For maximum neighbour-degree D ≥ 4, the matching index is at most D − 2.After fixing a non-redundant colour with at least three incident edges at a vertex, the other feasible colours require distinct additional neighbours, exceeding the degree bound if the index is at least D − 1.Source: §3 · p. 9
4 Edge connectivity: Proof of Theorem 8
The edge-connectivity argument uses a minimum edge cut to bound the number of feasible monochromatic colours. It rules out a connected multigraph whose matching index exceeds its edge connectivity.
4 Edge connectivity: Proof of Theorem 8
- Across a minimum edge cut, feasible colours whose matchings cross the cut each use at least two cut edges when both sides have even size.The proof separates colours into those with a matching crossing the cut and those without; every colour in the first group contributes at least two cut edges.Source: §4 · p. 10
- At most one feasible colour can have no monochromatic perfect matching crossing the cut.Two such colours would yield a non-monochromatic inherited colouring with nonzero weight, contradicting the GHZ condition.Source: §4 · p. 10
- A connected multigraph with matching index greater than its edge connectivity cannot exist.The proof assumes such a graph, removes redundant edges and colour classes without changing dimension, and shows the resulting graph remains connected.Source: §4 · pp. 9–10
5 Vertex connectivity for simple graphs: Proof of Theorem 9
For a minimum vertex separator, the proof counts colour classes against the possible subsets of the separator. A pigeonhole argument produces two colours with a shared split, contradicting the GHZ condition.
5 Vertex connectivity for simple graphs: Proof of Theorem 9
- The proof assumes too many feasible colours avoiding edges within a minimum separator, then assigns each colour a separator subset determining its matching split.For each such colour, every monochromatic perfect matching splits uniquely across the two sides augmented by a subset of the separator.Source: §5 · p. 11
- Two colours must share a separator subset, yielding a non-monochromatic inherited colouring with nonzero weight.There are more colours under consideration than available subsets; the shared subset supplies nonzero factors for both colours.Source: §5 · p. 11
- The proof bounds the edges inside the minimum separator and uses that count to conclude Theorem 9 for simple graphs.The separator has size κ(G), and simplicity limits the number of edges with both endpoints in it.Source: §5 · p. 11
6 Graphs with six or eight vertices: Proof of Theorem 10
The proof rules out the required multiple non-redundant colours on six- and eight-vertex graphs. It does so by showing that the resulting matchings force a non-monochromatic inherited colouring with nonzero weight, contrary to the GHZ condition.
6.1 Six-vertex case
- A third colour on six vertices forces a non-monochromatic colouring whose required zero weight contradicts the nonzero weights of its three matching edges.The first two matchings form an alternating 6-cycle, and any non-cyclic third-colour matching must contain an antipodal pair.Source: §6.1 · p. 12
6.2 Eight-vertex case for Theorem 10
- In Case 1 on eight vertices, the assumed two-4-cycle structure conflicts with the GHZ condition when a non-monochromatic inherited colouring has nonzero weight.The proof also frames the contradiction as a third colour forcing an alternating Hamiltonian cycle.Source: §6.2 · pp. 12, 14
- In Case 2, a non-crossing colour pairs vertices of equal parity along the fixed red-green Hamiltonian cycle, leaving three possible matching types up to symmetry.The proof distinguishes this from the case where every other non-redundant colour is crossing.Source: §6.2 · p. 14
- For a crossing matching, the proof derives one of two structures; either choice makes the fourth-colour extension impossible, whether brown is crossing or not.The non-crossing branch reduces to an already excluded Figure 5 configuration, while the crossing branch yields a non-monochromatic colouring of nonzero weight.Source: §6.2 · p. 15
- When both blue and brown are crossing, their edge-disjoint matchings have three possible combined configurations, and each leads to a contradiction.Figures 7a–b force an edge to be both red and green; Figure 7c yields a non-monochromatic colouring with nonzero weight.Source: §6.2 · p. 16