Paperlane

no. 5 · Friday 30 October 2026

An Adian-Rabin theorem for quantum automorphism groups of graphs

Josse van Dobben de Bruyn and William Slofstra

math.QA · 21 pp

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.

comments
21 pages
fields
Quantum Algebra, Combinatorics, Group Theory, Operator Algebras
pdf ↗ page arXiv:2610.40590 ↗