Connectivity limits dimension of multipartite GHZ quantum states
Connectivity Bounds for GHZ Graphs
Discrete Mathematics
Summary
Multipartite GHZ states are special quantum states important for quantum computing and communication. The authors explore a mathematical connection between these states and graph theory to understand limits on their complexity. They prove a new formula that sets upper limits on the dimension of these quantum states based on how connected the related graph is. This helps clarify what kinds of high-dimensional entangled states can be created in quantum optics experiments.
What this means in practice
- •For quantum optics engineers: Determine fundamental limits for high-dimensional entangled photonic states based on experimental graph structures.
- •For quantum communication developers: Guide design of multipartite quantum networks by bounding achievable entanglement dimensions from connectivity metrics.
A theory result. No direct application yet.
Authors
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.