Monochromatic quantum graphs (inherited vertex colorings)

The question

eqSystem6_no_solution_ge3. For $N=6$ and all $D\ge 3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem8_no_solution_d3. For $N=8$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem10_no_solution_d3. For $N=10$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem10_no_solution_d4. For $N=10$ and $D=4$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem10_no_solution_d5. For $N=10$ and $D=5$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem10_no_solution_d6. For $N=10$ and $D=6$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem10_no_solution_d7. For $N=10$ and $D=7$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem12_no_solution_d3. For $N=12$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem14_no_solution_d3. For $N=14$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem16_no_solution_d3. For $N=16$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem_no_solution_ge6_ge3. For all even $N\ge 6$ and $D\ge 3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{C}$?

eqSystem6_no_solution_d3_real. For $N=6$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{R}$?

eqSystem6_no_solution_ge3_real. For $N=6$ and all $D\ge 3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{R}$?

eqSystem8_no_solution_d3_real. For $N=8$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{R}$?

eqSystem10_no_solution_d3_real. For $N=10$ and $D=3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{R}$?

eqSystem_no_solution_ge6_ge3_real. For all even $N\ge 6$ and $D\ge 3$, does there exist no solution to the monochromatic quantum graph equation system over $\mathbb{R}$?

This file studies the existence of monochromatic quantum graphs: edge-coloured, edge-weighted complete graphs whose perfect matchings induce vertex colourings, with the property that

• every non-monochromatic inherited vertex colouring has total weight 0, while
• each of the D monochromatic colourings has total weight 1.

In the quantum-optics motivation, such a construction corresponds to generating high-dimensional multipartite GHZ-type states using probabilistic pair sources and linear optics (without additional resources), where interference patterns can be expressed as weighted sums over perfect matchings.

Main questions (informal)

• For N = 4 and D ≥ 4, does there exist such a graph/weighting?
• For even N ≥ 6 and D ≥ 3, does there exist such a graph/weighting?

Formalisation sketch

A quantum graph with N vertices and D colours can be encoded by a weight function W : EdgeN N D α → α (for a coefficient domain α).

For each assignment of vertex indices ι : V N → Fin D, we define a perfect-matching sum pmSumN N D W ι (a sum over perfect matchings, where each matching contributes the product of the corresponding edge weights determined by ι). The equation system EqSystemN N D W requires

pmSumN N D W ι = 1 iff ι is constant (all entries equal), and 0 otherwise.

The open conjectures in this file ask for non-existence/existence of such W over various coefficient domains (e.g. ℂ, ℝ, ℤ, and restricted integer weights).

References

• [Krenn2017] M. Krenn, X. Gu, A. Zeilinger, "Quantum Experiments and Graphs: Multiparty States as Coherent Superpositions of Perfect Matchings", Physical Review Letters 119(24), 240403 (2017).

• [MO2018] Vertex coloring inherited from perfect matchings (motivated by quantum physics), MathOverflow question 311325.

• [Gu2019] X. Gu, M. Erhard, A. Zeilinger, M. Krenn, "Quantum experiments and graphs II: Quantum interference, computation, and state generation", PNAS 116(10), 4147–4155 (2019).

• [Krenn2019] Questions on the Structure of Perfect Matchings inspired by Quantum Physics by M. Krenn, X. Gu, U. Soltész, Proc. 2nd Croatian Combinatorial Days, 57–70 (2019).

• [Chandran2022] Edge-coloured graphs with only monochromatic perfect matchings and their connection to quantum physics by N. Chandran, S. Gajjala (2022).

• [Chandran2024] Krenn–Gu conjecture for sparse graphs by N. Chandran, S. Gajjala, S. Illickan, M. Krenn, MFCS 2024.

• [Ki26] [A solver-free Lean 4 proof of the sharp bound $D\le N-2$ for monochromatic quantum graph equation systems over integral domains](https://github.com/KitaKen1/monochromatic-quantum-graph-sharp-bound-lean/tree/6c5340384479dbb36129b2e0084449be2458cce2), commit 6c534038.

• [Ki26b] [A solver-free Lean 4 proof that the monochromatic quantum graph equation system has no solution for $N=10$ and $D=8$ over integral domains](https://github.com/KitaKen1/monochromatic-quantum-graph-n10-d8-lean/tree/a9309005c7a27a2615f8e7eebef7a1db017809ab), commit a9309005.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.Paper.MonochromaticQuantumGraph (16 statements). answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem eqSystem6_no_solution_ge3 :
    answer(sorry) ↔
      ∀ D : Nat, D ≥ 3 →
        ¬ ∃ W : WeightsN 6 D ℂ, EqSystemN 6 D W

theorem eqSystem8_no_solution_d3 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 8 3 ℂ, EqSystemN 8 3 W

theorem eqSystem10_no_solution_d3 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 10 3 ℂ, EqSystemN 10 3 W

theorem eqSystem10_no_solution_d4 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 10 4 ℂ, EqSystemN 10 4 W

theorem eqSystem10_no_solution_d5 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 10 5 ℂ, EqSystemN 10 5 W

theorem eqSystem10_no_solution_d6 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 10 6 ℂ, EqSystemN 10 6 W

theorem eqSystem10_no_solution_d7 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 10 7 ℂ, EqSystemN 10 7 W

theorem eqSystem12_no_solution_d3 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 12 3 ℂ, EqSystemN 12 3 W

theorem eqSystem14_no_solution_d3 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 14 3 ℂ, EqSystemN 14 3 W

theorem eqSystem16_no_solution_d3 :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 16 3 ℂ, EqSystemN 16 3 W

theorem eqSystem_no_solution_ge6_ge3 :
    answer(sorry) ↔
      ∀ N D : Nat, N ≥ 6 → Even N → D ≥ 3 →
        ¬ ∃ W : WeightsN N D ℂ, EqSystemN N D W

theorem eqSystem6_no_solution_d3_real :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 6 3 ℝ, EqSystemN 6 3 W

theorem eqSystem6_no_solution_ge3_real :
    answer(sorry) ↔
      ∀ D : Nat, D ≥ 3 →
        ¬ ∃ W : WeightsN 6 D ℝ, EqSystemN 6 D W

theorem eqSystem8_no_solution_d3_real :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 8 3 ℝ, EqSystemN 8 3 W

theorem eqSystem10_no_solution_d3_real :
    answer(sorry) ↔
      ¬ ∃ W : WeightsN 10 3 ℝ, EqSystemN 10 3 W

theorem eqSystem_no_solution_ge6_ge3_real :
    answer(sorry) ↔
      ∀ N D : Nat, N ≥ 6 → Even N → D ≥ 3 →
        ¬ ∃ W : WeightsN N D ℝ, EqSystemN N D W

What counts as progress

• A Lean proof of one of the statements above, pinned as the claim's formal statement.
• Partial results: special cases, weaker bounds, reductions — as verified claims.
• Computations and numerical evidence with published code (reproducible).
• Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
• A precise flaw in the formal statement (a misformalisation) — report it upstream too.

Source and licence

Imported from Formal Conjectures (research papers), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.