Metraipolis › archive › dc_d1ffc608dfa4

An Adian-Rabin theorem for quantum automorphism groups of graphs — arXiv:2610.40590

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.40590
License (as archived)
CC0-1.0
Archived
2026-11-01T02:38:24.104Z
SHA-256 of the archived text
d97276b95a924107ff938a84976bcab2bf62c9c401968c4427ccb44d58b646e4
Stable URL of this page
https://metraipolis.com/documento/dc_d1ffc608dfa4

How to cite

An Adian-Rabin theorem for quantum automorphism groups of graphs — arXiv:2610.40590 — arXiv (en), https://arxiv.org/abs/2610.40590 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d1ffc608dfa4 (Metraipolis archive dc_d1ffc608dfa4, sha256 d97276b95a924107ff938a84976bcab2bf62c9c401968c4427ccb44d58b646e4)
BibTeX
@misc{dcd1ffc608dfa4,
  title = {An Adian-Rabin theorem for quantum automorphism groups of graphs — arXiv:2610.40590},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40590},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d1ffc608dfa4; sha256 d97276b95a924107ff938a84976bcab2bf62c9c401968c4427ccb44d58b646e4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40590. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Given a graph $G$, does it have quantum symmetries, or in other words, is the algebra of the quantum automorphism group non-commutative? In the world of ordinary groups, determining whether a finitely presented group is commutative is undecidable. This is an immediate consequence of the Adian-Rabin theorem, which shows that many natural properties of finitely presented groups are undecidable. In this paper, we prove an Adian-Rabin theorem for quantum automorphism groups of graphs, showing that many natural properties of the quantum automorphism group of a graph (including having quantum symmetries) are undecidable. We also show that it's undecidable to determine if the discrete quantum automorphism group is non-trivial. Our methods are based on solution groups of linear system nonlocal games, and we also prove an Adian-Rabin theorem in this context.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Quantum Algebra (math.QA) ; Combinatorics (math.CO); Group Theory (math.GR); Operator Algebras (math.OA).
Pagina del lavoro: https://arxiv.org/abs/2610.40590 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:28.328Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).