pith. sign in

arxiv: 2601.09685 · v3 · submitted 2026-01-14 · 🪐 quant-ph · math-ph· math.CT· math.MP· math.OA

Quantum graphs of homomorphisms

Andre Kornell , Bert Lindenhovius This is my paper

Pith reviewed 2026-05-16 14:25 UTC · model grok-4.3

classification 🪐 quant-ph math-phmath.CTmath.MPmath.OA
keywords quantum graphshomomorphism gamequantum strategiesnoncommutative geometryclosed monoidal categoryCP morphismsconfusability graphquantum channels
0
0 comments X

The pith

The quantum graph [G,H] of homomorphisms from G to H is nonempty exactly when a quantum strategy wins the (G,H)-homomorphism game for finite graphs.

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

The paper defines a category qGph of quantum graphs whose structure comes from noncommutative geometry. It builds an internal hom [G,H] inside this category that represents homomorphisms from one quantum graph to another, turning qGph into a closed symmetric monoidal category. For ordinary finite graphs G and H, the resulting object [G,H] is nonempty precisely when the classical homomorphism game between them admits a winning quantum strategy. This equivalence supplies a direct quantum lift of the classical fact that homomorphisms exist exactly when the hom-set is nonempty. Additional results establish that finite quantum graphs are tracial, real and self-adjoint, that two notions of completely positive morphism coincide in this setting, and that every finite reflexive quantum graph arises as the confusability graph of a quantum channel.

Core claim

We construct a quantum graph [G,H] of homomorphisms from G to H in the category qGph of quantum graphs, making qGph a closed symmetric monoidal category. For all finite graphs G and H, the quantum graph [G,H] is nonempty if and only if the (G,H)-homomorphism game has a winning quantum strategy.

What carries the argument

The internal hom-object [G,H] constructed in the closed symmetric monoidal category qGph, whose morphisms are completely positive maps adjoint to unital *-homomorphisms.

If this is right

  • qGph is a closed symmetric monoidal category under the constructed internal hom.
  • Weaver's two notions of CP morphism coincide for all finite quantum graphs.
  • Every finite reflexive quantum graph is the confusability quantum graph of some quantum channel.
  • All finite quantum graphs in qGph are tracial, real, and self-adjoint.

Where Pith is reading between the lines

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

  • The monoidal structure may allow classical results on graph homomorphisms to be lifted systematically to the quantum setting via categorical constructions.
  • Explicit computation of [G,H] for small finite graphs could provide concrete tests of the claimed equivalence between quantum graphs and quantum strategies.
  • The identification of reflexive quantum graphs with confusability graphs of channels may link homomorphism questions to concrete tasks in quantum information.

Load-bearing premise

The definitions of quantum graphs and CP morphisms in qGph, motivated from noncommutative geometry, correctly capture the existence of quantum winning strategies for homomorphism games.

What would settle it

A concrete pair of finite graphs G and H such that [G,H] is nonempty yet no quantum strategy wins the homomorphism game, or [G,H] is empty yet a quantum strategy does win.

read the original abstract

We introduce a category $\mathsf{qGph}$ of quantum graphs, whose definition is motivated entirely from noncommutative geometry. For all quantum graphs $G$ and $H$ in $\mathsf{qGph}$, we then construct a quantum graph $[G,H]$ of homomorphisms from $G$ to $H$, making $\mathsf{qGph}$ a closed symmetric monoidal category. We prove that for all finite graphs $G$ and $H$, the quantum graph $[G,H]$ is nonempty iff the $(G,H)$-homomorphism game has a winning quantum strategy, directly generalizing the classical case. The finite quantum graphs in $\mathsf{qGph}$ are tracial, real, and self-adjoint, and the morphisms between them are CP morphisms that are adjoint to a unital $*$-homomorphism. We prove that Weaver's two notions of a CP morphism coincide in this context. We also include a short proof that every finite reflexive quantum graph is the confusability quantum graph of a quantum channel.

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 / 2 minor

Summary. The manuscript introduces the category qGph of quantum graphs, defined as tracial real self-adjoint objects with CP morphisms adjoint to unital *-homomorphisms and motivated from noncommutative geometry. It constructs an internal hom [G,H] making qGph a closed symmetric monoidal category, and proves that for finite classical graphs G and H the quantum graph [G,H] is nonempty if and only if the (G,H)-homomorphism game admits a winning quantum strategy. Supporting results establish that Weaver's two notions of CP morphisms coincide in this setting and that every finite reflexive quantum graph arises as the confusability graph of a quantum channel.

Significance. If the central equivalence holds, the work supplies a categorical framework that directly generalizes classical graph homomorphisms to the quantum setting while linking nonemptiness of the internal hom to the existence of quantum winning strategies in homomorphism games. The definitional constructions resting on standard category axioms and domain definitions, together with the explicit proofs for the finite case and the auxiliary results on CP morphisms and confusability graphs, constitute a coherent contribution to quantum information theory and noncommutative geometry.

minor comments (2)
  1. [§2] §2 (definitions of qGph and CP morphisms): the statement that the two Weaver notions coincide is central to the morphism class; a short inline reminder of the precise statements of both notions before the proof would improve readability.
  2. [Abstract, §1] Abstract and §1: the restriction to finite graphs G and H for the main equivalence is stated clearly in the abstract but could be flagged again at the start of the introduction to set reader expectations.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the summary of our constructions and the recommendation for minor revision. We will incorporate appropriate minor changes in the revised version.

Circularity Check

0 steps flagged

No significant circularity; constructions and theorem are independent of inputs

full rationale

The paper defines qGph via tracial real self-adjoint objects and CP morphisms from noncommutative geometry, then uses standard monoidal closed category constructions to define the internal hom [G,H]. The central theorem—that [G,H] is nonempty precisely when the homomorphism game has a quantum winning strategy—is proved directly from these definitions for finite classical graphs G and H, with auxiliary results (Weaver's CP notions coincide; reflexive quantum graphs as confusability graphs) also derived independently. No equation reduces to a prior fit, no self-citation is load-bearing for the main claim, and the equivalence is not smuggled in by definition but established as a theorem. The derivation chain is self-contained against external category theory and game definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

Relies on standard category axioms and domain-specific definitions of quantum graphs; no free parameters or independently evidenced invented entities beyond the new category objects.

axioms (2)
  • standard math Axioms of symmetric monoidal closed categories
    Invoked to establish that qGph is closed symmetric monoidal.
  • domain assumption Quantum graphs and CP morphisms defined via noncommutative geometry
    Source of the objects and morphisms in qGph.
invented entities (2)
  • quantum graph no independent evidence
    purpose: Object in qGph generalizing classical graphs
    New objects introduced by the category definition.
  • homomorphism quantum graph [G,H] no independent evidence
    purpose: Internal hom object
    Constructed to close the monoidal structure.

pith-pipeline@v0.9.0 · 8043 in / 1213 out tokens · 53907 ms · 2026-05-16T14:25:06.896843+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Morita equivalence for quantum graphs

    math.OA 2026-04 unverdicted novelty 7.0

    Irreducibly acting quantum graphs are Morita equivalent if and only if they are full pullbacks of a common quantum graph, with connectivity, independence number, Shannon capacity, and Lovász number invariant under thi...

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    Abramsky and B

    S. Abramsky and B. Coecke. A categorical semantics of quantum protocols. In Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004, pages 415–425, 2004

    work page 2004

  2. [2]

    The quantum monad on relational structures

    Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Za- pata. The quantum monad on relational structures. In42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark, page19.Wadern: SchlossDagstuhl – Leibniz Zentrum für Informatik, 2017. Id/No 35

    work page 2017

  3. [3]

    Quantum groups and Fuss-Catalan algebras

    Teodor Banica. Quantum groups and Fuss-Catalan algebras. Commun. Math. Phys., 226(1):221–232, 2002

    work page 2002

  4. [4]

    J. S. Bell. On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1:195–200, Nov 1964

    work page 1964

  5. [5]

    2: Categories and struc- tures, volume 51 ofEncycl

    Francis Borceux.Handbook of categorical algebra. 2: Categories and struc- tures, volume 51 ofEncycl. Math. Appl.Cambridge: Univ. Press, 1994

    work page 1994

  6. [6]

    Bigalois extensions and the graph isomorphism game.Commun

    Michael Brannan, Alexandru Chirvasitu, Kari Eifler, Samuel Harris, Vern Paulsen, Xiaoyu Su, and Mateusz Wasilewski. Bigalois extensions and the graph isomorphism game.Commun. Math. Phys., 375(3):1777–1809, 2020

    work page 2020

  7. [7]

    Michael Brannan, Priyanga Ganesan, and Samuel J. Harris. The quantum- to-classical graph homomorphism game.J. Math. Phys., 63(11):112204, 34, 2022

    work page 2022

  8. [8]

    Cameron, Ashley Montanaro, Michael W

    Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Sev- erini, and Andreas Winter. On the quantum chromatic number of a graph. Electron. J. Comb., 14(1):research paper r81, 15, 2007

    work page 2007

  9. [9]

    Categorical aspects of quantum groups: multipliers and intrinsic groups.Can

    Matthew Daws. Categorical aspects of quantum groups: multipliers and intrinsic groups.Can. J. Math., 68(2):309–333, 2016

    work page 2016

  10. [10]

    Quantum graphs: different perspectives, homomorphisms and quantum automorphisms.Commun

    Matthew Daws. Quantum graphs: different perspectives, homomorphisms and quantum automorphisms.Commun. Am. Math. Soc., 4:117–181, 2024

    work page 2024

  11. [11]

    Meenakshi McNamara

    Rolando de Santiago and A. Meenakshi McNamara. Quantum chromatic numbers of products of quantum graphs. Preprint, arXiv:2408.11911 [math.OA] (2024), 2024

    work page arXiv 2024

  12. [12]

    Super-Activation of Zero-Error Capacity of Noisy Quantum Channels

    Runyao Duan. Super-activation of zero-error capacity of noisy quantum channels. Preprint, arXiv:0906.2527 [quant-ph] (2009), 2009

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  13. [13]

    Zero-error commu- nication via quantum channels, noncommutative graphs, and a quantum Lovász number.IEEE Trans

    Runyao Duan, Simone Severini, and Andreas Winter. Zero-error commu- nication via quantum channels, noncommutative graphs, and a quantum Lovász number.IEEE Trans. Inf. Theory, 59(2):1164–1174, 2013. 29

    work page 2013

  14. [14]

    Freyd and André Scedrov

    Peter J. Freyd and André Scedrov. Categories, allegories, volume 39 of North-Holland Math. Libr.Amsterdam etc.: North-Holland, 1990

    work page 1990

  15. [15]

    Quantum Games and Synchronicity

    Adina Goldberg. Quantum Games and Synchronicity. Preprint, arXiv:2408.15444 [quant-ph] (2024), 2024

    work page arXiv 2024

  16. [16]

    Gracia-Bondía, Joseph C

    José M. Gracia-Bondía, Joseph C. Várilly, and Héctor Figueroa.Elements of noncommutative geometry. Boston, MA: Birkhäuser, 2001

    work page 2001

  17. [17]

    Thestandardform of von Neumann algebras.Math

    Uffe Haagerup. Thestandardform of von Neumann algebras.Math. Scand., 37:271–283, 1976

    work page 1976

  18. [18]

    Samuel J. Harris. Universality of graph homomorphism games and the quantum coloring problem.Ann. Henri Poincaré, 25(10):4321–4356, 2024

    work page 2024

  19. [19]

    Monoidal Quantaloids

    Gejza Jenča and Bert Lindenhovius. Monoidal Quantaloids. Preprint, arXiv:2504.18266 [math.CT] (2025), 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  20. [20]

    Closed symmetric monoidal structures on the category of graphs

    Krzysztof Kapulkin and Nathan Kershaw. Closed symmetric monoidal structures on the category of graphs. Theory Appl. Categ., 41:760–784, 2024

    work page 2024

  21. [21]

    Quantum Functions

    Andre Kornell. Quantum Functions. Preprint, arXiv:1101.1694 [math.OA] (2011), 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  22. [22]

    Quantum collections

    Andre Kornell. Quantum collections. Int. J. Math., 28(12):1750085, 28, 2017

    work page 2017

  23. [23]

    Quantum sets.J

    Andre Kornell. Quantum sets.J. Math. Phys., 61(10):102202, 33, 2020

    work page 2020

  24. [24]

    Discrete quantum structures

    Andre Kornell. Discrete quantum structures. I: Quantum predicate logic. J. Noncommut. Geom., 18(1):337–382, 2024

    work page 2024

  25. [25]

    Characterizations of homomorphisms among unital com- pletely positive maps.Linear Algebra Appl., 709:314–330, 2025

    Andre Kornell. Characterizations of homomorphisms among unital com- pletely positive maps.Linear Algebra Appl., 709:314–330, 2025

    work page 2025

  26. [26]

    A category of quantum posets

    Andre Kornell, Bert Lindenhovius, and Michael Mislove. A category of quantum posets. Indag. Math., New Ser., 33(6):1137–1171, 2022

    work page 2022

  27. [27]

    K. Kraus. General state changes in quantum theory.Ann. Phys., 64:311– 335, 1971

    work page 1971

  28. [28]

    Texts Math.New York, NY: Springer, 2nd ed edition, 1998

    Saunders Mac Lane.Categories for the working mathematician., volume 5 of Grad. Texts Math.New York, NY: Springer, 2nd ed edition, 1998

    work page 1998

  29. [29]

    Graph homomorphisms for quan- tum players

    Laura Mančinska and David Roberson. Graph homomorphisms for quan- tum players. In9th conference on the theory of quantum computation, com- munication and cryptography, TQC 2014, Singapore, May 21–23, 2014, pages 212–216. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Infor- matik, 2014. 30

    work page 2014

  30. [30]

    Roberson

    Laura Mančinska and David E. Roberson. Quantum homomorphisms.J. Comb. Theory, Ser. B, 118:228–267, 2016

    work page 2016

  31. [31]

    Roberson

    Laura Mančinska and David E. Roberson. Oddities of quantum colorings. Baltic J. Modern Computing, 4(4):846–859, 2016

    work page 2016

  32. [32]

    Classification of quantum graphs on M2 and their quantum automorphism groups.J

    Junichiro Matsuda. Classification of quantum graphs on M2 and their quantum automorphism groups.J. Math. Phys., 63(9):092201, 34, 2022

    work page 2022

  33. [33]

    A compositional approach to quantum functions.J

    Benjamin Musto, David Reutter, and Dominic Verdon. A compositional approach to quantum functions.J. Math. Phys., 59(8):081706, 42, 2018

    work page 2018

  34. [34]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang.Quantum computation and quan- tum information. 10th anniversary edition. Cambridge: Cambridge Uni- versity Press, 2010

    work page 2010

  35. [35]

    Ortiz and Vern I

    Carlos M. Ortiz and Vern I. Paulsen. Quantum graph homomorphisms via operator systems. Linear Algebra Appl., 497:23–43, 2016

    work page 2016

  36. [36]

    Aclassof C ∗-algebrasgeneralizingbothCuntz-Krieger algebras and crossed products by Z

    MichaelV.Pimsner. Aclassof C ∗-algebrasgeneralizingbothCuntz-Krieger algebras and crossed products by Z. In Free probability theory. Papers from a workshop on random matrices and operator algebra free products, Toronto, Canada, Mars 1995, pages 189–212. Providence, RI: American Mathematical Society, 1997

    work page 1995

  37. [37]

    Podleś and S

    P. Podleś and S. L. Woronowicz. Quantum deformation of Lorentz group. Commun. Math. Phys., 130(2):381–431, 1990

    work page 1990

  38. [38]

    Piotr M. Sołtan. Quantum families of maps and quantum semigroups on finite quantum spaces.J. Geom. Phys., 59(3):354–368, 2009

    work page 2009

  39. [39]

    Quantum zero-error source-channel coding and non- commutative graph theory.IEEE Trans

    Dan Stahlke. Quantum zero-error source-channel coding and non- commutative graph theory.IEEE Trans. Inf. Theory, 62(1):554–577, 2016

    work page 2016

  40. [40]

    Covariant quantum combinatorics with applications to zero-error communication.Commun

    Dominic Verdon. Covariant quantum combinatorics with applications to zero-error communication.Commun. Math. Phys., 405(2):51, 57, 2024

    work page 2024

  41. [41]

    Categorical formulation of finite-dimensional quantum alge- bras

    Jamie Vicary. Categorical formulation of finite-dimensional quantum alge- bras. Commun. Math. Phys., 304(3):765–796, 2011

    work page 2011

  42. [42]

    Quantum relations

    Nik Weaver. Quantum relations. In A von Neumann algebra approach to quantum metrics / Quantum relations, pages 81–140. Providence, RI: American Mathematical Society (AMS), 2012

    work page 2012

  43. [43]

    Quantum graphs as quantum relations

    Nik Weaver. Quantum graphs as quantum relations. J. Geom. Anal., 31(9):9090–9112, 2021

    work page 2021

  44. [44]

    S. L. Woronowicz. Pseudospaces, pseudogroups and Pontrjagin duality. Mathematical problems in theoretical physics, Proc. Int. Conf., Lausanne 1979, Lect. Notes Phys. 116, 407-412 (1980), 1980. 31 Department of Mathematical Sciences, New Mexico State University Las Cruces, New Mexico, United States of America E-mail address : kornell@nmsu.edu Institute for...

    work page 1979