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:2605.30730

Vertex-transitive quantum graphs

Mac Hayes, Trevor Jess, Andre Kornell, Remi Salinas Schmeis

math.OAmath.COmath.QAquant-phSubmitted May 29, 2026• Announced Jun 1, 2026• Revised Jun 1, 2026 (v2)
v1 · May 29, 2026v2 · Jun 1, 2026v3 · Sep 24, 2026
arXivHTMLPDF

Abstract

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.

Comments
29 pages, 4 figures; added a reference to [4]

Related papers

Compact graphs and quantum automorphisms

Pedro Baptista, Gabriel Coutinho, Chris Godsil +1 more

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.

quant-pharXiv:2606.13928•Jun 15, 2026

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

Solution group representations as quantum symmetries of graphs

David E. Roberson, Simon Schmidt

In 2019, Aterias et al. constructed pairs of quantum isomorphic, non-isomorphic graphs from linear constraint systems. This article deals with quantum automorphisms and quantum isomorphisms of colored versions of those graphs. We show that the quantum automorphism group of such a colored graph is the dual of the homogeneous solution group of the underlying linear constraint system. Given a vertex- and edge-colored graph with certain properties, we construct an uncolored graph that has the same quantum automorphism group as the colored graph we started with. Using those results, we obtain the first known example of a graph that has quantum symmetry and finite quantum automorphism group. Furthermore, we construct a pair of quantum isomorphic, non-isomorphic graphs that both have no quantum symmetry.

arXiv:2111.12362•Journal of the London Mathematical Society•Jul 11, 2022•8 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•9 citations

Unification of Quantum Graph Properties

Gian Luca Spitzer

Many properties of classical graphs are defined in terms of subsets of the vertex set. Examples include connected components, which are subsets $X \subseteq V(G)$ such that $X \times X^c$ and $E(G)$ are disjoint, or independent sets, for which $X \times X$ and $E(G)$ are disjoint. Direct generalisations of these definitions to quantum graphs are difficult to achieve, since the natural notion of subsets of a quantum set is much too rigid. As a consequence, approaches to generalising these classical properties to the quantum setting have been eclectic. In some cases, multiple inequivalent definitions of the same notion are in use. We introduce a natural and well-motivated alternative definition of subsets of a quantum set. Building on this, we propose unified definitions of quantum graph properties as straightforward generalisations of the classical definitions. We recover this way the established notions of colourings and connected components. For independent sets and cliques, our approach suggests variations that diverge from existing definitions, but address some of their counterintuitive properties. We nevertheless show how to recover an important existing definition of independent sets in our framework.

math.OACross-listedarXiv:2607.28024•Jul 31, 2026

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
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.
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.
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 2019, Aterias et al. constructed pairs of quantum isomorphic, non-isomorphic graphs from linear constraint systems. This article deals with quantum automorphisms and quantum isomorphisms of colored versions of those graphs. We show that the quantum automorphism group of such a colored graph is the dual of the homogeneous solution group of the underlying linear constraint system. Given a vertex- and edge-colored graph with certain properties, we construct an uncolored graph that has the same quantum automorphism group as the colored graph we started with. Using those results, we obtain the first known example of a graph that has quantum symmetry and finite quantum automorphism group. Furthermore, we construct a pair of quantum isomorphic, non-isomorphic graphs that both have no quantum symmetry.
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.”
Many properties of classical graphs are defined in terms of subsets of the vertex set. Examples include connected components, which are subsets X⊆V(G)X \subseteq V(G)X⊆V(G) such that X×XcX \times X^cX×Xc and E(G)E(G)E(G) are disjoint, or independent sets, for which X×XX \times XX×X and E(G)E(G)E(G) are disjoint. Direct generalisations of these definitions to quantum graphs are difficult to achieve, since the natural notion of subsets of a quantum set is much too rigid. As a consequence, approaches to generalising these classical properties to the quantum setting have been eclectic. In some cases, multiple inequivalent definitions of the same notion are in use. We introduce a natural and well-motivated alternative definition of subsets of a quantum set. Building on this, we propose unified definitions of quantum graph properties as straightforward generalisations of the classical definitions. We recover this way the established notions of colourings and connected components. For independent sets and cliques, our approach suggests variations that diverge from existing definitions, but address some of their counterintuitive properties. We nevertheless show how to recover an important existing definition of independent sets in our framework.
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.