Connectivity Bounds for GHZ Graphs
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/√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.
Related
- Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- The Connectivity Threshold for Friends and Strangers graphs
- Independence number, essential connectivity and the distance spectral radius of graphs
- A linear bound for a connectivity partition in graphs
BibTeX
@misc{chandran2026connectivity,
title = {{Connectivity Bounds for GHZ Graphs}},
author = {L. Sunil Chandran and Rishikesh Gajjala},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22190},
eprint = {2610.22190},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22190},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Connectivity Bounds for GHZ Graphs
AU - L. Sunil Chandran
AU - Rishikesh Gajjala
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22190
UR - https://arxiv.org/abs/2610.22190
AB - 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/√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.
ER -