pith. sign in

arxiv: 2407.00303 · v1 · submitted 2024-06-29 · 🪐 quant-ph · cs.DM· math.CO

Krenn-Gu conjecture for sparse graphs

L. Sunil Chandran , Rishikesh Gajjala , Abraham M. Illickan This is my paper

Pith reviewed 2026-05-23 23:20 UTC · model grok-4.3

classification 🪐 quant-ph cs.DMmath.CO
keywords GHZ graphsKrenn-Gu conjecturevertex connectivitycubic graphsgraph dimensionquantum states
0
0 comments X

The pith

The Krenn-Gu conjecture holds for all GHZ graphs with vertex connectivity at most 2 and for all cubic GHZ graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the dimension of any GHZ graph on more than four vertices stays at most two whenever the graph has vertex connectivity two or less. The identical bound applies to every cubic GHZ graph. It further shows that any smallest counterexample to the full conjecture must be four-connected. These facts follow from combinatorial arguments that track how cuts and degree restrictions limit the possible interactions among edge colors and weights.

Core claim

The authors prove the Krenn-Gu conjecture for all GHZ graphs of vertex connectivity at most 2 and for all cubic GHZ graphs. They also prove that the minimal counterexample, if it exists, must be 4-connected.

What carries the argument

Vertex connectivity of the GHZ graph, which bounds the dimension by restricting how weighted color classes can combine across vertex cuts.

If this is right

  • No GHZ graph of connectivity at most two can produce a state of dimension higher than two.
  • Cubic GHZ graphs are restricted to dimension at most two for more than four vertices.
  • Any search for counterexamples can safely ignore graphs that are not 4-connected.
  • The conjecture is now reduced to the 4-connected case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • High-dimensional states in this correspondence, if they exist, must arise only from graphs whose minimum degree is at least four.
  • Connectivity arguments of this type could be applied to other parameters that link graph structure to entanglement dimension.
  • The results imply that sparse optical setups are provably limited in the entanglement they can generate under the GHZ correspondence.

Load-bearing premise

The combinatorial definition of GHZ graphs and their dimension parameter correctly captures the quantum optical experiments without additional constraints that would invalidate the connectivity-based arguments.

What would settle it

A GHZ graph on more than four vertices that has vertex connectivity three or less yet dimension greater than two.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper proves the Krenn-Gu conjecture on the dimension of GHZ graphs for all graphs with vertex connectivity at most 2 and for all cubic GHZ graphs; it further shows that any minimal counterexample must be 4-connected. The arguments are purely combinatorial and rely on reductions based on connectivity and degree.

Significance. If correct, the results narrow the search for counterexamples to the Krenn-Gu conjecture, directly aiding computational tools such as PyTheus. The combinatorial proofs are self-contained and require no quantum background, providing concrete structural constraints (connectivity and degree) that any potential high-dimension GHZ graph must satisfy.

minor comments (1)
  1. Abstract: the sentence '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' appears twice consecutively; remove the duplication.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation of minor revision. No major comments were listed in the report, so we have no specific points requiring rebuttal or revision at this stage.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes the Krenn-Gu conjecture for graphs of vertex connectivity at most 2 and for cubic graphs, plus that minimal counterexamples must be 4-connected, via purely combinatorial arguments on the dimension parameter of GHZ graphs. No self-citations are load-bearing, no parameters are fitted and then renamed as predictions, and no definitions or uniqueness claims reduce to the result itself by construction. The derivation chain is self-contained within external combinatorial definitions and case analysis on connectivity and degree.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on standard definitions of vertex connectivity, cubic graphs, and the GHZ-graph dimension parameter; no free parameters or new entities are introduced.

axioms (1)
  • standard math Standard definitions and basic properties of vertex connectivity and cubic graphs in graph theory
    Proofs for connectivity ≤2 and cubic cases rely on these background facts.

pith-pipeline@v0.9.0 · 5861 in / 1134 out tokens · 20233 ms · 2026-05-23T23:20:31.746911+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · 1 internal anchor

  1. [1]

    Accessed: 14-02-2023

    bit.ly/3RZmMYg. Accessed: 14-02-2023. 2 J. S. Bell. On the einstein podolsky rosen paradox. Physics Physique Fizika, 1:195–200, Nov

    work page 2023

  2. [2]

    3 Ilya Bogdanov

    URL: https://link.aps.org/doi/10.1103/PhysicsPhysiqueFizika.1.195, doi: 10.1103/PhysicsPhysiqueFizika.1.195. 3 Ilya Bogdanov. Solution to graphs with only disjoint perfect matchings.bit.ly/3x8hUGQ. Accessed: 09-02-2023. 4 Dik Bouwmeester, Jian-Wei Pan, Matthew Daniell, Harald Weinfurter, and Anton Zeilinger. Observation of three-photon greenberger-horne-z...

    work page doi:10.1103/physicsphysiquefizika.1.195 2023

  3. [3]

    5 Alba Cervera-Lierta, Mario Krenn, and Alán Aspuru-Guzik

    URL:https://link.aps.org/doi/10.1103/PhysRevLett.82.1345, doi:10.1103/PhysRevLett.82.1345. 5 Alba Cervera-Lierta, Mario Krenn, and Alán Aspuru-Guzik. Design of quantum optical experiments with logic artificial intelligence. CoRR, abs/2109.13273,

    work page doi:10.1103/physrevlett.82.1345

  4. [4]

    URL: https: //arxiv.org/abs/2109.13273, arXiv:2109.13273. 6 L. Sunil Chandran and Rishikesh Gajjala. Perfect matchings and quantum physics: Progress on krenn’s conjecture.CoRR, abs/2202.05562,

    work page arXiv

  5. [5]

    7 L.Sunil Chandran and Rishikesh Gajjala

    URL:https://arxiv.org/abs/2202.05562, arXiv:2202.05562. 7 L.Sunil Chandran and Rishikesh Gajjala. Graph-theoretic insights on the constructability of complex entangled states.CoRR, abs/2304.06407,

    work page arXiv

  6. [6]

    8 Daniel M

    URL:https://doi.org/10.48550/ arXiv.2304.06407, arXiv:2304.06407, doi:10.48550/ARXIV.2304.06407. 8 Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger.Going Beyond Bell’s Theorem, pages 69–72. Springer Netherlands, Dordrecht,

    work page doi:10.48550/arxiv.2304.06407

  7. [7]

    Questions on the Structure of Perfect Matchings inspired by Quantum Physics

    doi:10.1103/PhysRevA.99.032338. 10 Xuemei Gu, Manuel Erhard, Anton Zeilinger, and Mario Krenn. Quantum experiments and graphs ii: Quantum interference, computation, and state generation.Proceedings of the National Academy of Sciences, 116(10):4147–4155, 2019.doi:10.1073/pnas.1815884116. 11 Xuemei Gu and Mario Krenn. Compact greenberger-horne-zeilinger sta...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physreva.99.032338 2019

  8. [8]

    16 Jay Lawrence

    URL:https://link.aps.org/doi/10.1103/PhysRevX.11.031044, doi:10.1103/PhysRevX.11.031044. 16 Jay Lawrence. Rotational covariance and greenberger-horne-zeilinger theorems for three or more particles of any dimension. Phys. Rev. A, 89:012105, Jan

    work page doi:10.1103/physrevx.11.031044

  9. [9]

    Chandran, Gajjala and Illickan 1:21 17 Jay Lawrence

    URL: https: //link.aps.org/doi/10.1103/PhysRevA.89.012105, doi:10.1103/PhysRevA.89.012105. Chandran, Gajjala and Illickan 1:21 17 Jay Lawrence. Mermin inequalities for perfect correlations in many-qutrit systems.Phys. Rev. A, 95:042123, Apr

    work page doi:10.1103/physreva.89.012105

  10. [10]

    18 Kevin Mantey

    URL: https://link.aps.org/doi/10.1103/PhysRevA.95.042123, doi:10.1103/PhysRevA.95.042123. 18 Kevin Mantey. Krenn-gu conjecture is true for graphs with four vertices.http://tinyurl. com/4e5zjvpx. Accessed: 14-02-2024. 19 Dustin Mixon. A graph colouring problem from quantum physics with prizes!bit.ly/3Xk5KFm. Accessed: 09-02-2023. 20 Aaron Neugebauer. Rainb...

    work page doi:10.1103/physreva.95.042123 2024

  11. [11]

    URL:bit.ly/40CJCsV

    Accessed: 09-02-2023. URL:bit.ly/40CJCsV. 21 Jian-Wei Pan, Dik Bouwmeester, Matthew Daniell, Harald Weinfurter, and Anton Zeilinger. Experimental test of quantum nonlocality in three-photon greenberger–horne–zeilinger entan- glement. Nature, 403(6769):515–519, February 2000.doi:10.1038/35000514. 22 Matej Pivoluska, Marcus Huber, and Mehul Malik. Layered q...

    work page doi:10.1038/35000514 2023

  12. [12]

    Physical Review A33(5), 2913–2927 (1986)

    URL:https://link.aps.org/doi/10.1103/PhysRevA. 97.032312, doi:10.1103/PhysRevA.97.032312. 23 Carlos Ruiz-Gonzalez, Sören Arlt, Jan Petermann, Sharareh Sayyad, Tareq Jaouni, Ebrahim Karimi, Nora Tischler, Xuemei Gu, and Mario Krenn. Digital discovery of 100 diverse quantum experiments with pytheus. Quantum, 7:1204,

    work page doi:10.1103/physreva

  13. [13]

    22331/q-2023-12-12-1204, doi:10.22331/Q-2023-12-12-1204

    URL: https://doi.org/10. 22331/q-2023-12-12-1204, doi:10.22331/Q-2023-12-12-1204. 24 Junghee Ryu, Changhyoup Lee, Marek Żukowski, and Jinhyoung Lee. Greenberger-horne- zeilinger theorem forn qudits. Phys. Rev. A, 88:042101, Oct

    work page doi:10.22331/q-2023-12-12-1204 2023

  14. [14]

    org/doi/10.1103/PhysRevA.88.042101, doi:10.1103/PhysRevA.88.042101

    URL:https://link.aps. org/doi/10.1103/PhysRevA.88.042101, doi:10.1103/PhysRevA.88.042101. 25 Moshe Y. Vardi and Zhiwei Zhang. Quantum-inspired perfect matching under vertex-color constraints. CoRR, abs/2209.13063,

    work page doi:10.1103/physreva.88.042101

  15. [15]

    13063, arXiv:2209.13063, doi:10.48550/ARXIV.2209.13063

    URL: https://doi.org/10.48550/arXiv.2209. 13063, arXiv:2209.13063, doi:10.48550/ARXIV.2209.13063. 26 Moshe Y. Vardi and Zhiwei Zhang. Solving quantum-inspired perfect matching problems via tutte-theorem-based hybrid boolean constraints. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th Aug...

    work page doi:10.48550/arxiv.2209 2023

  16. [16]

    27 Xi-Lin Wang, Luo-Kan Chen, W

    URL:https://doi.org/10.24963/ ijcai.2023/227, doi:10.24963/IJCAI.2023/227. 27 Xi-Lin Wang, Luo-Kan Chen, W. Li, H.-L. Huang, C. Liu, C. Chen, Y.-H. Luo, Z.-E. Su, D. Wu, Z.-D. Li, H. Lu, Y. Hu, X. Jiang, C.-Z. Peng, L. Li, N.-L. Liu, Yu-Ao Chen, Chao-Yang Lu, and Jian-Wei Pan. Experimental ten-photon entanglement.Phys. Rev. Lett., 117:210502, Nov

    work page doi:10.24963/ijcai.2023/227 2023

  17. [17]

    URL:https://link.aps.org/doi/10.1103/PhysRevLett.117.210502, doi:10.1103/PhysRevLett.117.210502. 28 Han-Sen Zhong, Yuan Li, Wei Li, Li-Chao Peng, Zu-En Su, Yi Hu, Yu-Ming He, Xing Ding, Weijun Zhang, Hao Li, Lu Zhang, Zhen Wang, Lixing You, Xi-Lin Wang, Xiao Jiang, Li Li, Yu-Ao Chen, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. 12-photon entanglement and s...

    work page doi:10.1103/physrevlett.117.210502

  18. [18]

    URL:https://link.aps.org/doi/ 10.1103/PhysRevLett.121.250505, doi:10.1103/PhysRevLett.121.250505

    work page doi:10.1103/physrevlett.121.250505