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:2407.00303 · Leibniz international proceedings in informatics

Krenn-Gu Conjecture for Sparse Graphs

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

Published Jan 1, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4230/lipics.mfcs.2024.41

Related papers

Connectivity Bounds for GHZ Graphs

L. Sunil Chandran, Rishikesh Gajjala

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.

quant-pharXiv:2610.22190•Oct 16, 2026•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

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

Quantum Information Experiments with Multiple Photons in One and High-Dimensions: Concepts and Experiments

Manuel Erhard, Mario Krenn, Xumei Gu +2 more

Starting with the first experimental generation of a Greenberger-Horne-Zeilinger entangled state in three dimensions we show how to describe photonic quantum experiments using graph theory. This novel link promises exciting new applications ranging from multi-photon high-dimensionally entangled states to special purpose quantum simulation.

Quantum Information and Measurement (QIM)•Jan 1, 2019•0 citations

Generating large-scale Greenberger-Horne-Zeilinger-like states in lattice spin systems

Xuanchen Zhang, Yaofeng Chen, Yong-Chun Liu

Greenberger-Horne-Zeilinger (GHZ) state is a typical maximally entangled state which is pursued in both fundamental research and emerging quantum technologies. Preparing large-scale GHZ states in lattice spin systems is particularly appealing for quantum advantages, but conventional schemes face great challenges in scalability. Here we propose a universal and scalable scheme to generate large-scale GHZ-like states, which share similar entanglement and metrological properties with standard GHZ states, in lattice spin systems through global Floquet engineering. Our scheme requires only global operations and shows great advantage for large particle number. It is applicable to systems with arbitrary interaction ranges, offering a practical pathway for large-scale implementation of many-body entangled states in various systems.

quant-pharXiv:2602.21839•Physical Review A•Feb 26, 2026•0 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
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.
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.
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.
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.
Greenberger-Horne-Zeilinger (GHZ) state is a typical maximally entangled state which is pursued in both fundamental research and emerging quantum technologies. Preparing large-scale GHZ states in lattice spin systems is particularly appealing for quantum advantages, but conventional schemes face great challenges in scalability. Here we propose a universal and scalable scheme to generate large-scale GHZ-like states, which share similar entanglement and metrological properties with standard GHZ states, in lattice spin systems through global Floquet engineering. Our scheme requires only global operations and shows great advantage for large particle number. It is applicable to systems with arbitrary interaction ranges, offering a practical pathway for large-scale implementation of many-body entangled states in various systems.
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.