pith. sign in

arxiv: 2605.19543 · v1 · pith:RTJA5QI7new · submitted 2026-05-19 · 🧮 math.CO

The Quantum Homomorphism Orders are Universal

Yangjing Long This is my paper

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

classification 🧮 math.CO
keywords quantum graph homomorphismsquantum homomorphism ordersuniversal partial ordersdirected graphsundirected graphsgraph homomorphism gamesorder embeddings
0
0 comments X

The pith

The quantum homomorphism orders of finite directed and undirected graphs embed every countable partial order.

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 quantum homomorphism orders on finite directed graphs and on finite undirected graphs are both universal partial orders. Every countable partial order embeds into each of these orders. A sympathetic reader would care because this shows the relation induced by perfect quantum strategies for graph homomorphism games is rich enough to contain arbitrary countable order structures. For directed graphs the argument lifts a known classical universality result on disjoint unions of clockwise directed cycles by observing that quantum and classical homomorphisms agree exactly on those cycles. For undirected graphs the proof reduces the directed case to the undirected case by replacing each directed edge with a specially constructed gadget.

Core claim

We prove that the quantum homomorphism orders of both finite directed graphs and finite undirected graphs are universal: every countable partial order embeds into them. For directed graphs, the proof uses the classical universality of the homomorphism order on finite disjoint unions of clockwise directed cycles, together with the fact that quantum homomorphisms between such directed cycles coincide with classical homomorphisms. For undirected graphs we construct an explicit ordered undirected indicator whose terminal vertices are quantum endpoint-forcing. Replacing each directed edge by this indicator embeds the directed-cycle order into the quantum homomorphism order of finite undirected 그래

What carries the argument

The explicit ordered undirected indicator whose terminal vertices are quantum endpoint-forcing, which replaces directed edges to embed the directed-cycle order into the undirected quantum homomorphism order.

If this is right

  • Every countable partial order arises as a subposet of the quantum homomorphism order on finite directed graphs.
  • Every countable partial order arises as a subposet of the quantum homomorphism order on finite undirected graphs.
  • Quantum homomorphisms between finite disjoint unions of clockwise directed cycles are identical to classical homomorphisms.
  • The known classical universality result for the homomorphism order on cycle unions transfers directly to the quantum setting for directed graphs.

Where Pith is reading between the lines

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

  • The indicator gadget might be adaptable to establish universality results for other quantum relations defined on graphs.
  • These universal orders could supply order-theoretic tools for analyzing the computational complexity of deciding quantum homomorphism existence.

Load-bearing premise

The explicit ordered undirected indicator has terminal vertices that are quantum endpoint-forcing and thereby preserves the required order relations under edge replacement.

What would settle it

A concrete countable partial order that cannot be embedded into the quantum homomorphism order on finite undirected graphs would falsify the claim, for instance by exhibiting an order-theoretic property preserved by quantum homomorphisms that the candidate order violates.

Figures

Figures reproduced from arXiv: 2605.19543 by Yangjing Long.

Figure 1
Figure 1. Figure 1: The three graph gadgets used to implement the colors A, B and E. An A-root is the apex of a cone over a private 5-cycle. A B-root has two adjacent private A-roots in its neighborhood. An E-root has two adjacent private B-roots in its neighborhood. The labels are only for exposition; the construction is an ordinary graph. Definition 4.3 (The indicator J). Let J = J(a, b) be the following graph. Start with a… view at source ↗
Figure 2
Figure 2. Figure 2: The ordered indicator J(a, b). Each labeled spine vertex carries the graph gadget of the indicated color from [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original abstract

Man\v{c}inska and Roberson introduced quantum graph homomorphisms as the existence of perfect quantum strategies for graph homomorphism games. The resulting relation is a quasi-order on finite graphs, and hence gives a partial order after quotienting by quantum homomorphic equivalence. We prove that the quantum homomorphism orders of both finite directed graphs and finite undirected graphs are universal: every countable partial order embeds into them. For directed graphs, the proof uses the classical universality of the homomorphism order on finite disjoint unions of clockwise directed cycles, together with the fact that quantum homomorphisms between such directed cycles coincide with classical homomorphisms. For undirected graphs we construct an explicit ordered undirected indicator whose terminal vertices are quantum endpoint-forcing. Replacing each directed edge by this indicator embeds the directed-cycle order into the quantum homomorphism order of finite undirected graphs.

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

1 major / 2 minor

Summary. The paper proves that the quantum homomorphism orders of both finite directed graphs and finite undirected graphs are universal: every countable partial order embeds into them. For directed graphs, the proof reduces the claim to the known classical universality of the homomorphism order on finite disjoint unions of clockwise directed cycles, together with the observation that quantum homomorphisms coincide with classical homomorphisms on these graphs. For undirected graphs, the proof constructs an explicit ordered undirected indicator gadget whose terminal vertices are quantum endpoint-forcing, and uses replacement of directed edges by this gadget to embed the directed-cycle order into the quantum homomorphism order of finite undirected graphs.

Significance. If the central claims hold, the result establishes that quantum homomorphism orders are universal in the order-theoretic sense, extending classical universality theorems for graph homomorphisms (such as those on directed cycles) to the quantum setting introduced by Mančinska and Roberson. The directed-graph case is a clean reduction that credits and reuses existing classical results without introducing new parameters or ad-hoc axioms. The undirected case supplies an explicit gadget construction, which, if verified, provides a concrete and potentially reusable tool for realizing embeddings via quantum strategies. This strengthens the understanding of the richness of quantum graph relations.

major comments (1)
  1. [§4 (gadget construction)] The load-bearing step for the undirected case is the claim that the constructed ordered undirected indicator has terminal vertices that are quantum endpoint-forcing, so that perfect quantum strategies for the homomorphism game between gadget-replaced graphs recover exactly the homomorphisms of the original directed cycles. The manuscript should supply a self-contained argument (or explicit verification via the homomorphism game definition) showing that no other quantum strategies can violate the intended terminal mapping; this is the point on which the embedding for undirected graphs stands or falls.
minor comments (2)
  1. [Abstract] The abstract is concise but could include a one-sentence pointer to the specific classical universality theorem being invoked for the directed-cycle case.
  2. [§2–3] Notation for quantum homomorphisms and the indicator gadget should be introduced once in a dedicated preliminaries subsection and then used consistently; currently the transition from directed to undirected replacement is slightly abrupt.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, their positive evaluation of the significance of the results, and for the constructive suggestion regarding the presentation of the undirected case. We address the major comment below and will revise the manuscript to incorporate a more explicit verification as requested.

read point-by-point responses

  1. Referee: [§4 (gadget construction)] The load-bearing step for the undirected case is the claim that the constructed ordered undirected indicator has terminal vertices that are quantum endpoint-forcing, so that perfect quantum strategies for the homomorphism game between gadget-replaced graphs recover exactly the homomorphisms of the original directed cycles. The manuscript should supply a self-contained argument (or explicit verification via the homomorphism game definition) showing that no other quantum strategies can violate the intended terminal mapping; this is the point on which the embedding for undirected graphs stands or falls.

    Authors: We agree that the verification that the terminal vertices of the ordered undirected indicator are quantum endpoint-forcing is the key step ensuring the embedding works, and that a more self-contained argument would improve clarity. In the revised version of the manuscript we will expand the discussion in §4 to include an explicit verification directly from the definition of the homomorphism game. We will show that any perfect quantum strategy on the gadget-replaced graphs must induce the intended mapping on the terminal vertices: specifically, by considering the projective measurements associated to the strategy and demonstrating that any outcome inconsistent with the endpoint-forcing property yields a winning probability strictly less than one. This argument will be presented without relying on external results beyond the standard definition of quantum homomorphisms, thereby confirming that the quantum homomorphisms between the modified undirected graphs recover precisely the classical homomorphisms of the original directed-cycle instances. We believe this addition will fully address the referee's concern while preserving the existing gadget construction. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit constructions and external classical results

full rationale

The derivation for directed graphs invokes the classical universality result on disjoint unions of directed cycles (an external fact) together with the stated equivalence of quantum and classical homomorphisms on those specific graphs. The undirected case proceeds by an explicit gadget construction whose terminal vertices are shown to be quantum endpoint-forcing via direct verification inside the proof. No equation or central claim reduces by definition to a fitted parameter, a self-referential definition, or a load-bearing self-citation chain; the result is obtained by concrete embedding rather than tautological renaming or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a pure mathematical proof in graph theory and quantum strategies. It relies on standard axioms of mathematics and graph theory with no free parameters, ad-hoc axioms, or invented entities introduced to support the central claim.

pith-pipeline@v0.9.0 · 5649 in / 1005 out tokens · 22607 ms · 2026-05-20T03:59:30.166498+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

32 extracted references · 32 canonical work pages

  1. [1]

    Atserias, L

    A. Atserias, L. Mančinska, D. E. Roberson, R. Šámal, S. Severini, and A. Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289–328, 2019. doi: 10.1016/j.jctb.2018.11.002

    work page doi:10.1016/j.jctb.2018.11.002 2019

  2. [2]

    Banakh, L

    D. Banakh, L. Ciardo, M. Kozik, and J. Tułowiecki. Classical simu- lation of quantum CSP strategies. InProceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 372–388, 2025

    work page 2025

  3. [3]

    Brannan, P

    M. Brannan, P. Ganesan, and S. J. Harris. The quantum-to-classical graph homomorphism game.Journal of Mathematical Physics, 63(11): 112204, 2022. doi: 10.1063/5.0072288

    work page doi:10.1063/5.0072288 2022

  4. [4]

    L. Ciardo. Quantum advantage and CSP complexity.Journal of Combi- natorial Theory, Series B, 176:404–439, 2026. doi: 10.1016/j.jctb.2025. 10.002

    work page doi:10.1016/j.jctb.2025 2026

  5. [5]

    L. Ciardo. On the quantum chromatic gap. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3364–3377. SIAM, 2026. doi: 10.1137/1.9781611978971.121

    work page doi:10.1137/1.9781611978971.121 2026

  6. [6]

    Ciardo, G

    L. Ciardo, G. Joubert, and A. Mottet. Quantum polymorphisms and commutativity gadgets, 2025

    work page 2025

  7. [7]

    Fiala, J

    J. Fiala, J. Hubička, and Y. Long. An universality argument for graph homomorphisms. InElectronic Notes in Discrete Mathematics, volume 49, pages 643–649, 2015. doi: 10.1016/j.endm.2015.06.087

    work page doi:10.1016/j.endm.2015.06.087 2015

  8. [8]

    Fiala, J

    J. Fiala, J. Hubička, Y. Long, and J. Nešetřil. Fractal property of the graph homomorphism order.European Journal of Combinatorics, 66: 101–109, 2017. doi: 10.1016/j.ejc.2017.06.001. 14 YANGJING LONG

    work page doi:10.1016/j.ejc.2017.06.001 2017

  9. [9]

    S. J. Harris. Universality of graph homomorphism games and the quan- tum coloring problem.Annales Henri Poincaré, 25:4321–4356, 2024. doi: 10.1007/s00023-024-01422-5

    work page doi:10.1007/s00023-024-01422-5 2024

  10. [10]

    Z. Hedrlín. On universal partly ordered sets and classes.Journal of Algebra, 11:503–509, 1969. doi: 10.1016/0021-8693(69)90060-0

    work page doi:10.1016/0021-8693(69)90060-0 1969

  11. [11]

    Hell and J

    P. Hell and J. Nešetřil.Graphs and Homomorphisms, volume 28 ofOxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2004

    work page 2004

  12. [12]

    J. W. Helton, K. P. Meyer, V. I. Paulsen, and M. Satriano. Algebras, synchronous games, and chromatic numbers of graphs.New York Journal of Mathematics, 25:328–361, 2019

    work page 2019

  13. [13]

    Hubička and J

    J. Hubička and J. Nešetřil. Finite paths are universal.Order, 22(1): 21–40, 2005. doi: 10.1007/s11083-005-9004-7

    work page doi:10.1007/s11083-005-9004-7 2005

  14. [14]

    Hubička and J

    J. Hubička and J. Nešetřil. Universal partial order represented by means of oriented trees and other simple graphs.European Journal of Combinatorics, 26(5):765–778, 2005. doi: 10.1016/j.ejc.2004.05.010

    work page doi:10.1016/j.ejc.2004.05.010 2005

  15. [15]

    P. N. Kar, D. E. Roberson, T. Seppelt, and P. Zeman. NPA hierarchy for quantumisomorphismandhomomorphismindistinguishability.Quantum, 10:1989, 2026. doi: 10.22331/q-2026-01-28-1989

    work page doi:10.22331/q-2026-01-28-1989 1989

  16. [16]

    Karamlou

    A. Karamlou. Quantum relaxations of CSP and structure isomor- phism. In50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), volume 345 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:18, Dagstuhl, Ger- many, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/LIPIcs.MFCS.2025.61

    work page doi:10.4230/lipics.mfcs.2025.61 2025

  17. [17]

    Kornell and B

    A. Kornell and B. Lindenhovius. Quantum graphs of homomorphisms, 2026

    work page 2026

  18. [18]

    Luchnikov, J

    A. Luchnikov, J. Wittebol, and J. Zuiddam. Universality of asymptotic graph homomorphism, 2025

    work page 2025

  19. [19]

    Lupini, L

    M. Lupini, L. Mančinska, and D. E. Roberson. Nonlocal games and quantum permutation groups.Journal of Functional Analysis, 279(5): 108592, 2020. doi: 10.1016/j.jfa.2020.108592

    work page doi:10.1016/j.jfa.2020.108592 2020

  20. [20]

    Consciousness and Cognition20(2011) https://doi.org/10.1016/j

    L. Mančinska and D. E. Roberson. Quantum homomorphisms.Journal of Combinatorial Theory, Series B, 118:228–267, 2016. doi: 10.1016/j. jctb.2015.12.009

    work page doi:10.1016/j 2016

  21. [21]

    Mančinska and D

    L. Mančinska and D. E. Roberson. Oddities of quantum colorings.Baltic Journal of Modern Computing, 4(4):846–859, 2016

    work page 2016

  22. [22]

    Stochastic Weighted Matching: (1-

    L. Mančinska and D. E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. InProceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020), pages 661–672. IEEE Computer Society, 2020. doi: 10. 1109/FOCS46700.2020.00067

    work page arXiv 2020

  23. [23]

    Mančinska, D

    L. Mančinska, D. E. Roberson, and A. Varvitsiotis. On deciding the existence of perfect entangled strategies for nonlocal games.Chicago Journal of Theoretical Computer Science, 2016(5):1–16, 2016. THE QUANTUM HOMOMORPHISM ORDERS ARE UNIVERSAL 15

    work page 2016

  24. [24]

    Naserasr, S

    R. Naserasr, S. Sen, and É. Sopena. The homomorphism order of signed graphs.Journal of Combinatorial Mathematics and Combinatorial Computing, 116:169–182, 2021

    work page 2021

  25. [25]

    Naserasr, É

    R. Naserasr, É. Sopena, and T. Zaslavsky. Homomorphisms of signed graphs: An update.European Journal of Combinatorics, 91:103222,

    work page

  26. [26]

    doi: 10.1016/j.ejc.2020.103222

    work page doi:10.1016/j.ejc.2020.103222 2020

  27. [27]

    C. M. Ortiz and V. I. Paulsen. Quantum graph homomorphisms via operator systems.Linear Algebra and its Applications, 497:23–43, 2016. doi: 10.1016/j.laa.2016.02.019

    work page doi:10.1016/j.laa.2016.02.019 2016

  28. [28]

    Pultr and V

    A. Pultr and V. Trnková.Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, volume 22 of North-Holland Mathematical Library. North-Holland, 1980

    work page 1980

  29. [29]

    D. E. Roberson.Variations on a Theme: Graph Homomorphisms. PhD thesis, University of Waterloo, 2013

    work page 2013

  30. [30]

    D. E. Roberson. Conic formulations of graph homomorphisms.Jour- nal of Algebraic Combinatorics, 43(4):877–913, 2016. doi: 10.1007/ s10801-016-0665-y

    work page 2016

  31. [31]

    D. E. Roberson and T. Seppelt. Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability.TheoretiCS, 3:Article 20, 1–42,

    work page

  32. [32]

    School of Mathematics and Statistics, Central China Normal University, 152 Luoyu Road, Hongshan District, Wuhan, Hubei 430079, China Email address:yangjing@ccnu.edu.cn

    doi: 10.46298/theoretics.24.20. School of Mathematics and Statistics, Central China Normal University, 152 Luoyu Road, Hongshan District, Wuhan, Hubei 430079, China Email address:yangjing@ccnu.edu.cn

    work page doi:10.46298/theoretics.24.20