Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.22190

Connectivity Bounds for GHZ Graphs

L. Sunil Chandran, Rishikesh Gajjala

quant-phcs.DMmath.COSubmitted Oct 15, 2026• Announced Oct 16, 2026• 0 citations
arXivHTMLPDF

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.

Comments
To appear in FSTTCS 2026

Related papers

Krenn-Gu Conjecture for Sparse Graphs

L. Sunil Chandran, Rishikesh R. Gajjala, Abraham M. Illickan

Greenberger-Horne-Zeilinger (GHZ) states are quantum states involving at least three entangled particles. They are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography. They are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography. Krenn, Gu and Zeilinger discovered a correspondence between a large class of quantum optical experiments which produce GHZ states and edge-weighted edge-coloured multi-graphs with some special properties called the \emph{GHZ graphs}. On such GHZ graphs, a graph parameter called \emph{dimension} can be defined, which is the same as the dimension of the GHZ state produced by the corresponding experiment. Krenn and Gu conjectured that the dimension of any GHZ graph with more than $4$ vertices is at most $2$. An affirmative resolution of the Krenn-Gu conjecture has implications for quantum resource theory. On the other hand, the construction of a GHZ graph on a large number of vertices with a high dimension would lead to breakthrough results. In this paper, we study the existence of GHZ graphs from the perspective of the Krenn-Gu conjecture and show that the conjecture is true for graphs of vertex connectivity at most 2 and for cubic graphs. We also show that the minimal counterexample to the conjecture should be $4$-connected. Such information could be of great help in the search for GHZ graphs using existing tools like PyTheus. While the impact of the work is in quantum physics, the techniques in this paper are purely combinatorial, and no background in quantum physics is required to understand them.

arXiv:2407.00303•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

Quantum experiments and graphs. III. High-dimensional and multiparticle entanglement

Xuemei Gu, Lijun Chen, Anton Zeilinger +1 more

Quantum entanglement plays an important role in quantum information processes, such as quantum computation and quantum communication. Experiments in laboratories are unquestionably crucial to increase our understanding of quantum systems and inspire new insights into future applications. However, there are no general recipes for the creation of arbitrary quantum states with many particles entangled in high dimensions. Here we exploit a recent connection between quantum experiments and graph theory and answer this question for a plethora of classes of entangled states. We find experimental setups for Greenberger-Horne-Zeilinger states, $W$ states, general Dicke states, and asymmetrically high-dimensional multipartite entangled states. This result sheds light on the producibility of arbitrary quantum states using photonic technology with probabilistic pair sources and allows us to understand the underlying technological and fundamental properties of entanglement.

arXiv:1812.09558•Physical Review A•Mar 25, 2019•50 citations

Characterizing high-dimensional multipartite entanglement beyond Greenberger-Horne-Zeilinger fidelities

Shuheng Liu, Qiongyi He, Marcus Huber +1 more

Characterizing entanglement of systems composed of multiple particles is a very complex problem that is attracting increasing attention across different disciplines related to quantum physics. The task becomes even more complex when the particles have many accessible levels, i.e., they are of high dimension, which leads to a potentially high-dimensional multipartite entangled state. These are important resources for an ever-increasing number of tasks, especially when a network of parties needs to share highly entangled states, e.g., for communicating more efficiently and securely. For these applications, as well as for purely theoretical arguments, it is important to be able to certify both the high-dimensional and the genuine multipartite nature of entangled states, possibly based on simple measurements. Here we derive a novel method that achieves this and improves over typical entanglement witnesses like the fidelity with respect to states of a Greenberger-Horne-Zeilinger (GHZ) form, without needing more complex measurements. We test our condition on paradigmatic classes of high-dimensional multipartite entangled states like imperfect GHZ states with random noise, as well as on purely randomly chosen ones and find that, in comparison with other available criteria our method provides a significant advantage and is often also simpler to evaluate.

arXiv:2405.03261•Quantum•Feb 3, 2026•1 citation

Experimental test of the Greenberger–Horne–Zeilinger-type paradoxes in and beyond graph states

Zhenghao Liu, Jie Zhou, Hui-Xian Meng +9 more

Abstract The Greenberger–Horne–Zeilinger (GHZ) paradox is an exquisite no-go theorem that shows the sharp contradiction between classical theory and quantum mechanics by ruling out any local realistic description of quantum theory. The investigation of GHZ-type paradoxes has been carried out in a variety of systems and led to fruitful discoveries. However, its range of applicability still remains unknown and a unified construction is yet to be discovered. In this work, we present a unified construction of GHZ-type paradoxes for graph states, and show that the existence of GHZ-type paradox is not limited to graph states. The results have important applications in quantum state verification for graph states, entanglement detection, and construction of GHZ-type steering paradox for mixed states. We perform a photonic experiment to test the GHZ-type paradoxes via measuring the success probability of their corresponding perfect Hardy-type paradoxes, and demonstrate the proposed applications. Our work deepens the comprehension of quantum paradoxes in quantum foundations, and may have applications in a broad spectrum of quantum information tasks.

npj Quantum Information•Apr 28, 2021•17 citations

Generation and Distribution of GHZ States in Quantum Networks

Mohammad Ghaderibaneh, Himanshu Gupta, C. R. Ramakrishnan

In quantum networks, multipartite entangled states distributed over the network are useful in implementing and supporting many quantum network applications for communications, sensing, and computing. The focus of our work is to de-velop techniques to efficiently generate distributed Greenberger-Horne-Zeilinger (GHZ) states, a special class of multipartite entanglement states. Prior works on generating GHZ states have focused on the objective of minimizing the number of maximally entangled (bipartite) pairs (EPs), while ignoring the stochastic nature of quantum processes and assuming uniform network links for generating EPs. In contrast, in our work, we take into consideration the stochastic nature of quantum networks, and focus on maximizing the expected generated rate of the GHZ states under given fidelity constraints. In this context, we develop two efficient generation schemes, viz., Fusion - Retain - only and General Fusion, comprised of optimal or near-optimal sub-steps. Both schemes, at a high-level, first determine a way to “connect” the nodes over which the GHZ state is to distributed, and then, determine a sequence of fusion operations on the EPs created over the connections. Using extensive simulations over a quantum network simulator (NetSquid), we demonstrate the effectiveness of our developed techniques and show that our schemes outperform prior work as well as a simple centralized approach by up to orders of magnitude while generating GHZ states of tolerable fidelity.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•14 citations

Nonsymmetric Greenberger-Horne-Zeilinger states: Weighted hypergraph and controlled-unitary graph representations

Hrachya Zakaryan, Konstantinos-Rafail Revis, Zahra Raissi

Nonsymmetric GHZ states ($n\text{\ensuremath{-}}{\mathrm{GHZ}}_{\ensuremath{\alpha}}$), defined by unequal superpositions of $|00...0\ensuremath{\rangle}$ and $|11...1\ensuremath{\rangle}$, naturally emerge in experiments due to decoherence, control errors, and state preparation imperfections. Despite their relevance in quantum communication, relativistic quantum information, and quantum teleportation, these states lack a stabilizer formalism and a graph representation, hindering their theoretical and experimental analysis. We establish a graph-theoretic framework for nonsymmetric GHZ states, proving their local unitary (LU) equivalence to two structures: fully connected weighted hypergraphs with controlled-phase interactions and star-shaped controlled-unitary (CU) graphs. While weighted hypergraphs generally lack stabilizer descriptions, we demonstrate that nonsymmetric GHZ states can be efficiently stabilized using local operations and a single ancilla, independent of system size, thereby enabling entanglement witness construction and offering a pathway toward qudit quantum error correction. We extend this framework to qudit systems, constructing LU-equivalent weighted qudit hypergraphs and showing that general nonsymmetric qudit GHZ states can be described as star-shaped CU graphs. Our results provide a systematic approach to characterizing and stabilizing nonsymmetric multipartite entanglement in both qubit and qudit systems, with implications for quantum error correction and networked quantum protocols.

arXiv:2408.02740•Physical Review A•Sep 3, 2025•2 citations
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 222. 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 222 [MFCS 2024], and that simple GHZ graphs with n>4n>4n>4 vertices have dimension less than n/2n/\sqrt{2}n/2​ [Quantum 2024]. However, no general upper bound depending only on vertex connectivity was known. We prove that every simple connected GHZ graph GGG with at least four vertices has dimension at most 2κ(G)−1+(κ(G)2)2^{κ(G)-1}+\binom{κ(G)}{2}2κ(G)−1+(2κ(G)​), where κ(G)κ(G)κ(G) is the vertex connectivity of GGG. We also prove new bounds in terms of edge connectivity and maximum degree.
Greenberger-Horne-Zeilinger (GHZ) states are quantum states involving at least three entangled particles. They are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography. They are of fundamental interest in quantum information theory, and the construction of such states of high dimension has various applications in quantum communication and cryptography. Krenn, Gu and Zeilinger discovered a correspondence between a large class of quantum optical experiments which produce GHZ states and edge-weighted edge-coloured multi-graphs with some special properties called the \emph{GHZ graphs}. On such GHZ graphs, a graph parameter called \emph{dimension} can be defined, which is the same as the dimension of the GHZ state produced by the corresponding experiment. Krenn and Gu conjectured that the dimension of any GHZ graph with more than 444 vertices is at most 222. An affirmative resolution of the Krenn-Gu conjecture has implications for quantum resource theory. On the other hand, the construction of a GHZ graph on a large number of vertices with a high dimension would lead to breakthrough results. In this paper, we study the existence of GHZ graphs from the perspective of the Krenn-Gu conjecture and show that the conjecture is true for graphs of vertex connectivity at most 2 and for cubic graphs. We also show that the minimal counterexample to the conjecture should be 444-connected. Such information could be of great help in the search for GHZ graphs using existing tools like PyTheus. While the impact of the work is in quantum physics, the techniques in this paper are purely combinatorial, and no background in quantum physics is required to understand them.
Quantum entanglement plays an important role in quantum information processes, such as quantum computation and quantum communication. Experiments in laboratories are unquestionably crucial to increase our understanding of quantum systems and inspire new insights into future applications. However, there are no general recipes for the creation of arbitrary quantum states with many particles entangled in high dimensions. Here we exploit a recent connection between quantum experiments and graph theory and answer this question for a plethora of classes of entangled states. We find experimental setups for Greenberger-Horne-Zeilinger states, WWW states, general Dicke states, and asymmetrically high-dimensional multipartite entangled states. This result sheds light on the producibility of arbitrary quantum states using photonic technology with probabilistic pair sources and allows us to understand the underlying technological and fundamental properties of entanglement.
Characterizing entanglement of systems composed of multiple particles is a very complex problem that is attracting increasing attention across different disciplines related to quantum physics. The task becomes even more complex when the particles have many accessible levels, i.e., they are of high dimension, which leads to a potentially high-dimensional multipartite entangled state. These are important resources for an ever-increasing number of tasks, especially when a network of parties needs to share highly entangled states, e.g., for communicating more efficiently and securely. For these applications, as well as for purely theoretical arguments, it is important to be able to certify both the high-dimensional and the genuine multipartite nature of entangled states, possibly based on simple measurements. Here we derive a novel method that achieves this and improves over typical entanglement witnesses like the fidelity with respect to states of a Greenberger-Horne-Zeilinger (GHZ) form, without needing more complex measurements. We test our condition on paradigmatic classes of high-dimensional multipartite entangled states like imperfect GHZ states with random noise, as well as on purely randomly chosen ones and find that, in comparison with other available criteria our method provides a significant advantage and is often also simpler to evaluate.
Abstract The Greenberger–Horne–Zeilinger (GHZ) paradox is an exquisite no-go theorem that shows the sharp contradiction between classical theory and quantum mechanics by ruling out any local realistic description of quantum theory. The investigation of GHZ-type paradoxes has been carried out in a variety of systems and led to fruitful discoveries. However, its range of applicability still remains unknown and a unified construction is yet to be discovered. In this work, we present a unified construction of GHZ-type paradoxes for graph states, and show that the existence of GHZ-type paradox is not limited to graph states. The results have important applications in quantum state verification for graph states, entanglement detection, and construction of GHZ-type steering paradox for mixed states. We perform a photonic experiment to test the GHZ-type paradoxes via measuring the success probability of their corresponding perfect Hardy-type paradoxes, and demonstrate the proposed applications. Our work deepens the comprehension of quantum paradoxes in quantum foundations, and may have applications in a broad spectrum of quantum information tasks.
In quantum networks, multipartite entangled states distributed over the network are useful in implementing and supporting many quantum network applications for communications, sensing, and computing. The focus of our work is to de-velop techniques to efficiently generate distributed Greenberger-Horne-Zeilinger (GHZ) states, a special class of multipartite entanglement states. Prior works on generating GHZ states have focused on the objective of minimizing the number of maximally entangled (bipartite) pairs (EPs), while ignoring the stochastic nature of quantum processes and assuming uniform network links for generating EPs. In contrast, in our work, we take into consideration the stochastic nature of quantum networks, and focus on maximizing the expected generated rate of the GHZ states under given fidelity constraints. In this context, we develop two efficient generation schemes, viz., Fusion - Retain - only and General Fusion, comprised of optimal or near-optimal sub-steps. Both schemes, at a high-level, first determine a way to “connect” the nodes over which the GHZ state is to distributed, and then, determine a sequence of fusion operations on the EPs created over the connections. Using extensive simulations over a quantum network simulator (NetSquid), we demonstrate the effectiveness of our developed techniques and show that our schemes outperform prior work as well as a simple centralized approach by up to orders of magnitude while generating GHZ states of tolerable fidelity.
Nonsymmetric GHZ states ($n\text{\ensuremath{-}}{\mathrm{GHZ}}_{\ensuremath{\alpha}}$), defined by unequal superpositions of $|00...0\ensuremath{\rangle}$ and $|11...1\ensuremath{\rangle}$, naturally emerge in experiments due to decoherence, control errors, and state preparation imperfections. Despite their relevance in quantum communication, relativistic quantum information, and quantum teleportation, these states lack a stabilizer formalism and a graph representation, hindering their theoretical and experimental analysis. We establish a graph-theoretic framework for nonsymmetric GHZ states, proving their local unitary (LU) equivalence to two structures: fully connected weighted hypergraphs with controlled-phase interactions and star-shaped controlled-unitary (CU) graphs. While weighted hypergraphs generally lack stabilizer descriptions, we demonstrate that nonsymmetric GHZ states can be efficiently stabilized using local operations and a single ancilla, independent of system size, thereby enabling entanglement witness construction and offering a pathway toward qudit quantum error correction. We extend this framework to qudit systems, constructing LU-equivalent weighted qudit hypergraphs and showing that general nonsymmetric qudit GHZ states can be described as star-shaped CU graphs. Our results provide a systematic approach to characterizing and stabilizing nonsymmetric multipartite entanglement in both qubit and qudit systems, with implications for quantum error correction and networked quantum protocols.