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

Ukrains’kyi Matematychnyi Zhurnal

Про квантові симетрії графів

Ольга Островська, Vasyl Ostrovskyi, Людмила Туровська

Published May 29, 2026• 0 citations
Publisher

Abstract

UDC 519.17, 517.98, 519.8 Let $G$ be a simple finite graph and let $\mathcal U_G$ be the corresponding quantum graph. We study the game algebra $C(\mathrm{Qut}(\mathcal U_G))$ of the quantum automorphisms of $\mathcal U_G.$ It is shown that, for the complete graph $K_n,$ the algebra $C(\mathrm{Qut}(\mathcal U_{K_n}))$ is not commutative even for all $n\geq 3,$ unlike $C(\mathrm{Qut}(K_n))=C(S_n^+).$ Moreover, we prove that, for any graph $G$ with $|V(G)|\geq 3,$ the quantum graph $\mathcal U_G$ admits nonlocal symmetry, which means that there exists a perfect quantum no-signaling correlation for the quantum automorphism game for $\mathcal U_G,$ which is not local.

DOI
10.3842/umzh.v78i5-6.9774

Related papers

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•6 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 No-signalling Correlations and Non-local Games

Ivan G. Todorov, Lyudmila B. Turowska

Abstract We introduce and examine three subclasses of the family of quantum no-signalling (QNS) correlations introduced by Duan and Winter: quantum commuting, quantum and local. We formalise the notion of a universal TRO of a block operator isometry, define an operator system, universal for stochastic operator matrices, and realise it as a quotient of a matrix algebra. We describe the classes of QNS correlations in terms of states on the tensor products of two copies of the universal operator system and specialise the correlation classes and their representations to classical-to-quantum correlations. We study various quantum versions of synchronous no-signalling correlations and show that they possess invariance properties for suitable sets of states. We introduce quantum non-local games as a generalisation of non-local games. We define the operation of quantum game composition and show that the perfect strategies belonging to a certain class are closed under channel composition. We specialise to the case of graph colourings, where we exhibit quantum versions of the orthogonal rank of a graph as the optimal output dimension for which perfect classical-to-quantum strategies of the graph colouring game exist, as well as to non-commutative graph homomorphisms, where we identify quantum versions of non-commutative graph homomorphisms introduced by Stahlke.

arXiv:2009.07016•Communications in Mathematical Physics•May 28, 2024•15 citations

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•2 citations

The Morita Theory of Quantum Graph Isomorphisms

Benjamin Musto, David Reutter, Dominic Verdon

We classify instances of quantum pseudo-telepathy in the graph isomorphism game, exploiting the recently discovered connection between quantum information and the theory of quantum automorphism groups. Specifically, we show that graphs quantum isomorphic to a given graph are in bijective correspondence with Morita equivalence classes of certain Frobenius algebras in the category of finite-dimensional representations of the quantum automorphism algebra of that graph. We show that such a Frobenius algebra may be constructed from a central type subgroup of the classical automorphism group, whose action on the graph has coisotropic vertex stabilisers. In particular, if the original graph has no quantum symmetries, quantum isomorphic graphs are classified by such subgroups. We show that all quantum isomorphic graph pairs corresponding to a well-known family of binary constraint systems arise from this group-theoretical construction. We use our classification to show that, of the small order vertex-transitive graphs with no quantum symmetry, none is quantum isomorphic to a non-isomorphic graph. We show that this is in fact asymptotically almost surely true of all graphs.

arXiv:1801.09705•Communications in Mathematical Physics•Sep 7, 2018•36 citations

Communication Complexity of Graph Isomorphism, Coloring, and Distance Games

Pierre Botteron, Moritz Weber

In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. An example of differentiation is given by the principle of no-collapse of communication complexity, which is often interpreted as necessary for a feasible physical theory. It is satisfied by quantum correlations but violated by some non-signalling ones. In this work, we investigate this principle in the context of three nonlocal games related to graph theory, starting from the well-known graph isomorphism and graph coloring games, and introducing a new game, the vertex distance game, with a parameter $D\in\mathbb N$, that generalizes the former two to some extent. For these three games, we prove that perfect non-signalling strategies collapse communication complexity under favorable conditions. We also define a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms, and we show that this characterizes perfect non-signalling strategies for the vertex distance game. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies since the parameter D is visible only in the non-signalling setting.

arXiv:2406.02199•Jun 4, 2024•0 citations
UDC 519.17, 517.98, 519.8 Let GGG be a simple finite graph and let UG\mathcal U_GUG​ be the corresponding quantum graph. We study the game algebra C(Qut(UG))C(\mathrm{Qut}(\mathcal U_G))C(Qut(UG​)) of the quantum automorphisms of UG.\mathcal U_G.UG​. It is shown that, for the complete graph Kn,K_n,Kn​, the algebra C(Qut(UKn))C(\mathrm{Qut}(\mathcal U_{K_n}))C(Qut(UKn​​)) is not commutative even for all n≥3,n\geq 3,n≥3, unlike C(Qut(Kn))=C(Sn+).C(\mathrm{Qut}(K_n))=C(S_n^+).C(Qut(Kn​))=C(Sn+​). Moreover, we prove that, for any graph GGG with ∣V(G)∣≥3,|V(G)|\geq 3,∣V(G)∣≥3, the quantum graph UG\mathcal U_GUG​ admits nonlocal symmetry, which means that there exists a perfect quantum no-signaling correlation for the quantum automorphism game for UG,\mathcal U_G,UG​, which is not local.
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.
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.
Abstract We introduce and examine three subclasses of the family of quantum no-signalling (QNS) correlations introduced by Duan and Winter: quantum commuting, quantum and local. We formalise the notion of a universal TRO of a block operator isometry, define an operator system, universal for stochastic operator matrices, and realise it as a quotient of a matrix algebra. We describe the classes of QNS correlations in terms of states on the tensor products of two copies of the universal operator system and specialise the correlation classes and their representations to classical-to-quantum correlations. We study various quantum versions of synchronous no-signalling correlations and show that they possess invariance properties for suitable sets of states. We introduce quantum non-local games as a generalisation of non-local games. We define the operation of quantum game composition and show that the perfect strategies belonging to a certain class are closed under channel composition. We specialise to the case of graph colourings, where we exhibit quantum versions of the orthogonal rank of a graph as the optimal output dimension for which perfect classical-to-quantum strategies of the graph colouring game exist, as well as to non-commutative graph homomorphisms, where we identify quantum versions of non-commutative graph homomorphisms introduced by Stahlke.
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 classify instances of quantum pseudo-telepathy in the graph isomorphism game, exploiting the recently discovered connection between quantum information and the theory of quantum automorphism groups. Specifically, we show that graphs quantum isomorphic to a given graph are in bijective correspondence with Morita equivalence classes of certain Frobenius algebras in the category of finite-dimensional representations of the quantum automorphism algebra of that graph. We show that such a Frobenius algebra may be constructed from a central type subgroup of the classical automorphism group, whose action on the graph has coisotropic vertex stabilisers. In particular, if the original graph has no quantum symmetries, quantum isomorphic graphs are classified by such subgroups. We show that all quantum isomorphic graph pairs corresponding to a well-known family of binary constraint systems arise from this group-theoretical construction. We use our classification to show that, of the small order vertex-transitive graphs with no quantum symmetry, none is quantum isomorphic to a non-isomorphic graph. We show that this is in fact asymptotically almost surely true of all graphs.
In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. An example of differentiation is given by the principle of no-collapse of communication complexity, which is often interpreted as necessary for a feasible physical theory. It is satisfied by quantum correlations but violated by some non-signalling ones. In this work, we investigate this principle in the context of three nonlocal games related to graph theory, starting from the well-known graph isomorphism and graph coloring games, and introducing a new game, the vertex distance game, with a parameter D∈ND\in\mathbb ND∈N, that generalizes the former two to some extent. For these three games, we prove that perfect non-signalling strategies collapse communication complexity under favorable conditions. We also define a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms, and we show that this characterizes perfect non-signalling strategies for the vertex distance game. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies since the parameter D is visible only in the non-signalling setting.