A Caltech Library Service

Nonlocal Games and Quantum Permutation Groups

Lupini, Martino and Mančinska, Laura and Roberson, David E. (2017) Nonlocal Games and Quantum Permutation Groups. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We present a strong connection between quantum information and quantum permutation groups. Specifically, we define a notion of quantum isomorphisms of graphs based on quantum automorphisms from the theory of quantum groups, and then show that this is equivalent to the previously defined notion of quantum isomorphism corresponding to perfect quantum strategies to the isomorphism game. Moreover, we show that two connected graphs X and Y are quantum isomorphic if and only if there exists x∈V(X) and y∈V(Y) that are in the same orbit of the quantum automorphism group of the disjoint union of X and Y. This connection links quantum groups to the more concrete notion of nonlocal games and physically observable quantum behaviours. We exploit this link by using ideas and results from quantum information in order to prove new results about quantum automorphism groups, and about quantum permutation groups more generally. In particular, we show that asymptotically almost surely all graphs have trivial quantum automorphism group. Furthermore, we use examples of quantum isomorphic graphs from previous work to construct an infinite family of graphs which are quantum vertex transitive but fail to be vertex transitive, answering a question from the quantum group literature. Our main tool for proving these results is the introduction of orbits and orbitals (orbits on ordered pairs) of quantum permutation groups. We show that the orbitals of a quantum permutation group form a coherent configuration/algebra, a notion from the field of algebraic graph theory. We then prove that the elements of this quantum orbital algebra are exactly the matrices that commute with the magic unitary defining the quantum group. We furthermore show that quantum isomorphic graphs admit an isomorphism of their quantum orbital algebras which maps the adjacency matrix of one graph to that of the other.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Lupini, Martino0000-0003-1588-7057
Additional Information:We would like to thank Alexandru Chirvasitu and Teodor Banica for pointing out to us that the Haar state of a quantum permutation group is tracial. Part of this work was completed during the Focused Research Meeting at Queen's University Belfast in October 2017, which was funded by the Heilbronn Institute for Mathematical Research. ML is partially supported by the National Science Foundation Grant DMS-1600186. DR was supported by European Research Council Advanced Grant GRACOL, project no. 320812.
Funding AgencyGrant Number
Heilbronn InstituteUNSPECIFIED
European Research Council (ERC)320812
Record Number:CaltechAUTHORS:20180410-085935600
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:85717
Deposited By: Tony Diaz
Deposited On:10 Apr 2018 16:07
Last Modified:10 Apr 2018 16:07

Repository Staff Only: item control page