arXiv:2610.22190
Connectivity Bounds for GHZ Graphs
L. Sunil Chandran, Rishikesh Gajjala
Abstract
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}+\binom{κ(G)}{2}$, where $κ(G)$ is the vertex connectivity of $G$. We also prove new bounds in terms of edge connectivity and maximum degree.
AI Summary
The paper studies connectivity constraints on GHZ-state generation in a graph model of photonic experiments. Perfect matchings encode detection events, and complex edge weights must cancel all non-monochromatic inherited vertex colourings while retaining $d$ monochromatic ones. The motivating Krenn–Gu conjecture asserts $d\leq2$ for more than four vertices. The setting here uses ordinary edge colours, not the more general model with independently coloured edge endpoints. Writing $\mu(G)$ for the maximum achievable dimension on a fixed graph, the main result is $\mu(G)\leq2^{\kappa(G)-1}+\binom{\kappa(G)}{2}$ for simple connected graphs with at least four vertices. A sharper separator-dependent form replaces the binomial term by the number of edges inside a minimum vertex separator. For connected loopless multigraphs, the paper proves $\mu(G)\leq\lambda(G)$. It also establishes, for $n>4$, $\mu(G)\leq2$ when the maximum neighbour-degree is at most three, and $\mu(G)\leq\Delta_v(G)-2$ otherwise, implying $\mu(G)\leq n-3$. Purely combinatorial proofs recover bounds of two and three for simple graphs on six and eight vertices, respectively. The proofs factor matching-weight sums over colour classes and components, combine cut-parity arguments with counting, and use a pigeonhole argument over separator allocations. The small-order proofs analyze alternating cycles and matching configurations. The conjecture remains unresolved: the vertex-connectivity bound is exponential, stronger results were already known for connectivity at most two, and whether polynomial dependence is possible remains open. The small-order bounds were previously established computationally in a broader setting.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- To appear in FSTTCS 2026