The Quantum Homomorphism Orders are Universal
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914580251279360 |
|---|---|
| author | Long, Yangjing |
| author_facet | Long, Yangjing |
| contents | Manč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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19543 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Quantum Homomorphism Orders are Universal Long, Yangjing Combinatorics 05C76, 05C15, 81P45 (Graph theory, Graph colouring, Quantum theory applications) F.2.2; I.2.7; G.2.2 Manč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. |
| title | The Quantum Homomorphism Orders are Universal |
| topic | Combinatorics 05C76, 05C15, 81P45 (Graph theory, Graph colouring, Quantum theory applications) F.2.2; I.2.7; G.2.2 |
| url | https://arxiv.org/abs/2605.19543 |