Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 29 min ago
PreprintarXiv licencearXiv

An Adian-Rabin theorem for quantum automorphism groups of graphs

  • Josse van Dobben de Bruyn
  • William Slofstra
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Automorphism groups of Cayley graphs on almost simple groups with normal connection sets
    Mengyu Cao, Benjian Lv, Binzhou Xia
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  2. Asymptotical results on the automorphism groups of canonical double cover of graphs
    Bartłomiej Bychawski, Ademir Hujdurović, Đorđe Mitrović +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Mathieu groups as flag-transitive automorphism groups of block designs
    Fatemeh Bakhtiari, Ashraf Daneshkhah
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Algebraic entropy of birational automorphism groups in families of hyper-Kähler manifolds
    Francesco Antonio Denisi, Keiji Oguiso, Claudio Onorati +2
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv
  5. Automorphism groups of semi-rigid T-varieties of complexity one
    Kirill Rassolov
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{bruyn2026adianrabin,
  title = {{An Adian-Rabin theorem for quantum automorphism groups of graphs}},
  author = {Josse van Dobben de Bruyn and William Slofstra},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.40590},
  eprint = {2610.40590},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40590},
}
RIS
TY  - UNPB
TI  - An Adian-Rabin theorem for quantum automorphism groups of graphs
AU  - Josse van Dobben de Bruyn
AU  - William Slofstra
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.40590
UR  - https://arxiv.org/abs/2610.40590
AB  - 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.
ER  -