Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.13928

Compact graphs and quantum automorphisms

Pedro Baptista, Gabriel Coutinho, Chris Godsil, Simon Schmidt

quant-phmath.COSubmitted Jun 11, 2026• Announced Jun 15, 2026
arXivHTMLPDF

Abstract

Compact graphs are graphs for which the fractional automorphism polytope has no genuinely fractional vertices. This paper proposes a quantum analogue of this idea by evaluating the fundamental magic unitary of the quantum automorphism group on states, which we show to produce a closed convex set of doubly stochastic matrices sitting between the classical automorphism polytope and the full fractional automorphism polytope. Our main result is that the natural quantum analogue of compactness is classical, that is, a quantum compact graph is classically compact. We also relate this set to the quantum orbital algebra and obtain a hierarchy of classical and quantum compactness pseudo notions. The framework recovers familiar consequences of compactness through commutants and suggests quantum analogues of generous transitivity and distance-transitivity. We also isolate examples and open problems indicating where quantum symmetries may strictly refine the classical compactness theory.

Comments
22 pages

Related papers

Asymmetric graphs with quantum symmetry

Josse van Dobben de Bruyn, David E. Roberson, Simon Schmidt

Abstract We present an infinite sequence of finite graphs with trivial automorphism group and non‐trivial quantum automorphism group. These are the first known examples of graphs with this property. Moreover, to the best of our knowledge, these are the first examples of any asymmetric classical space that has non‐trivial quantum symmetries. Our construction is based on solution groups to (binary) linear systems, as defined by Cleve, Liu, and Slofstra in the context of non‐local games. We first show that the dual quantum group of every solution group occurs as the quantum automorphism group of some graph, and then construct an infinite sequence of systems whose solution groups are non‐trivial perfect groups. This leads to the desired sequence of graphs. In addition to our main result, we prove a number of related results that allow us to answer several open problems from the literature. We prove a weak quantum analog of Frucht's theorem, namely that every finite classical group occurs as the quantum automorphism group of a finite graph. Combined with our main result, this shows that, for every finite group , there are graphs and that both have classical automorphism group isomorphic to but one of them has quantum symmetry and the other does not. Therefore, the quantum automorphism group of a graph is never determined by its classical automorphism group, and there do not exist any “quantum excluding groups.”

arXiv:2311.04889•Proceedings of the London Mathematical Society•Nov 1, 2025•9 citations

A compositional approach to quantum functions

Benjamin Musto, David Reutter, Dominic Verdon

We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.

arXiv:1711.07945•Journal of Mathematical Physics•Aug 1, 2018•66 citations

An Adian-Rabin theorem for quantum automorphism groups of graphs

Josse van Dobben de Bruyn, William Slofstra

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.

arXiv:2610.40590•Oct 29, 2026•0 citations

Quantum symmetry vs nonlocal symmetry

David E. Roberson, Simon Schmidt

We introduce the notion of nonlocal symmetry of a graph $G$, defined as a winning quantum correlation for the $G$-automorphism game that cannot be produced classically. Recent connections between quantum group theory and quantum information show that quantum correlations for this game correspond to tracial states on $C(\text{Qut}(G))$ -- the algebra of functions on the quantum automorphism group of $G$. This allows us to also define nonlocal symmetry for any quantum permutation group. We investigate the differences and similarities between this and the notion of quantum symmetry, defined as non-commutativity of $C(\text{Qut}(G))$. Roughly speaking, quantum symmetry vs nonlocal symmetry can be viewed respectively as non-classicality of our model of reality vs non-classicality of our observation of reality. We show that quantum symmetry is necessary but not sufficient for nonlocal symmetry. In particular, we show that the complete graph on five vertices is the only connected graph on five or fewer vertices with nonlocal symmetry, despite a dozen others having quantum symmetry. In particular this shows that the quantum symmetric group on four points, $S_4^+$, does not exhibit nonlocal symmetry, answering a question from the literature. In contrast to quantum symmetry, we show that two disjoint classical automorphisms do not guarantee nonlocal symmetry. However, three disjoint automorphisms do suffice. We also give a construction of quantum permutation matrices built from a finite abelian group $Γ$ and a permutation $π$ on $|Γ|$ elements. Computational evidence suggests that for cyclic groups of increasing size almost all permutations $π$ result in nonlocal symmetry. Surprisingly, the construction never results in nonlocal symmetry when $\mathbb{Z}_2^3$ is used. We also investigate under what conditions nonlocal symmetry arises when taking unions or products of graphs.

arXiv:2012.13328•Dec 24, 2020•9 citations

Graph Quantum Magic Squares and Free Spectrahedra

La Piana, Francesca

Recently De les Coves, Drescher and Netzer showed that an analogue of the Birkhoff--von Neumann theorem fails in the quantum setting. Motivated by this and questions arising in the study of quantum automorphisms of graphs, we introduce a graph-based variant of quantum magic squares and show that the analogue already fails for the cycle \(C_4\), via an explicit counterexample. We also show that they admit monic linear matrix inequality descriptions, hence form compact free spectrahedra.

arXiv:2512.08797•Dec 9, 2025•0 citations

Vertex-transitive quantum graphs

Mac Hayes, Trevor Jess, Andre Kornell +1 more

We define a quantum graph to be vertex-transitive if the join of its automorphism group is the maximum quantum relation on its quantum vertex set, in direct analogy with the classical case. All simple quantum graphs in $M_2(\mathbb C)$ are vertex-transitive, but many simple quantum graphs in $M_3(\mathbb C)$ are not vertex-transitive. We provide a complete classification of vertex-transitive quantum graphs in $M_3(\mathbb C)$ up to isomorphism. To do this, we introduce a polynomial invariant for quantum graphs in $M_n(\mathbb C)$, which we call the panoramic polynomial.

math.OACross-listedarXiv:2605.30730•Jun 1, 2026
Compact graphs are graphs for which the fractional automorphism polytope has no genuinely fractional vertices. This paper proposes a quantum analogue of this idea by evaluating the fundamental magic unitary of the quantum automorphism group on states, which we show to produce a closed convex set of doubly stochastic matrices sitting between the classical automorphism polytope and the full fractional automorphism polytope. Our main result is that the natural quantum analogue of compactness is classical, that is, a quantum compact graph is classically compact.
We also relate this set to the quantum orbital algebra and obtain a hierarchy of classical and quantum compactness pseudo notions. The framework recovers familiar consequences of compactness through commutants and suggests quantum analogues of generous transitivity and distance-transitivity. We also isolate examples and open problems indicating where quantum symmetries may strictly refine the classical compactness theory.
Abstract We present an infinite sequence of finite graphs with trivial automorphism group and non‐trivial quantum automorphism group. These are the first known examples of graphs with this property. Moreover, to the best of our knowledge, these are the first examples of any asymmetric classical space that has non‐trivial quantum symmetries. Our construction is based on solution groups to (binary) linear systems, as defined by Cleve, Liu, and Slofstra in the context of non‐local games. We first show that the dual quantum group of every solution group occurs as the quantum automorphism group of some graph, and then construct an infinite sequence of systems whose solution groups are non‐trivial perfect groups. This leads to the desired sequence of graphs. In addition to our main result, we prove a number of related results that allow us to answer several open problems from the literature. We prove a weak quantum analog of Frucht's theorem, namely that every finite classical group occurs as the quantum automorphism group of a finite graph. Combined with our main result, this shows that, for every finite group , there are graphs and that both have classical automorphism group isomorphic to but one of them has quantum symmetry and the other does not. Therefore, the quantum automorphism group of a graph is never determined by its classical automorphism group, and there do not exist any “quantum excluding groups.”
We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.
Given a graph GGG, 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.
We introduce the notion of nonlocal symmetry of a graph GGG, defined as a winning quantum correlation for the GGG-automorphism game that cannot be produced classically. Recent connections between quantum group theory and quantum information show that quantum correlations for this game correspond to tracial states on C(Qut(G))C(\text{Qut}(G))C(Qut(G)) -- the algebra of functions on the quantum automorphism group of GGG. This allows us to also define nonlocal symmetry for any quantum permutation group. We investigate the differences and similarities between this and the notion of quantum symmetry, defined as non-commutativity of C(Qut(G))C(\text{Qut}(G))C(Qut(G)). Roughly speaking, quantum symmetry vs nonlocal symmetry can be viewed respectively as non-classicality of our model of reality vs non-classicality of our observation of reality. We show that quantum symmetry is necessary but not sufficient for nonlocal symmetry. In particular, we show that the complete graph on five vertices is the only connected graph on five or fewer vertices with nonlocal symmetry, despite a dozen others having quantum symmetry. In particular this shows that the quantum symmetric group on four points, S4+S_4^+S4+​, does not exhibit nonlocal symmetry, answering a question from the literature. In contrast to quantum symmetry, we show that two disjoint classical automorphisms do not guarantee nonlocal symmetry. However, three disjoint automorphisms do suffice. We also give a construction of quantum permutation matrices built from a finite abelian group ΓΓΓ and a permutation πππ on ∣Γ∣|Γ|∣Γ∣ elements. Computational evidence suggests that for cyclic groups of increasing size almost all permutations πππ result in nonlocal symmetry. Surprisingly, the construction never results in nonlocal symmetry when Z23\mathbb{Z}_2^3Z23​ is used. We also investigate under what conditions nonlocal symmetry arises when taking unions or products of graphs.
Recently De les Coves, Drescher and Netzer showed that an analogue of the Birkhoff--von Neumann theorem fails in the quantum setting. Motivated by this and questions arising in the study of quantum automorphisms of graphs, we introduce a graph-based variant of quantum magic squares and show that the analogue already fails for the cycle C4C_4C4​, via an explicit counterexample. We also show that they admit monic linear matrix inequality descriptions, hence form compact free spectrahedra.
We define a quantum graph to be vertex-transitive if the join of its automorphism group is the maximum quantum relation on its quantum vertex set, in direct analogy with the classical case. All simple quantum graphs in M2(C)M_2(\mathbb C)M2​(C) are vertex-transitive, but many simple quantum graphs in M3(C)M_3(\mathbb C)M3​(C) are not vertex-transitive. We provide a complete classification of vertex-transitive quantum graphs in M3(C)M_3(\mathbb C)M3​(C) up to isomorphism. To do this, we introduce a polynomial invariant for quantum graphs in Mn(C)M_n(\mathbb C)Mn​(C), which we call the panoramic polynomial.