Sinkhorn Algorithm for Quantum Permutation Groups

Abstract

We introduce a Sinkhorn-type algorithm for producing quantum permutation matrices encoding symmetries of graphs. Our algorithm generates square matrices whose entries are orthogonal projections onto one-dimensional subspaces satisfying a set of linear relations. We use it for experiments on the representation theory of the quantum permutation group and quantum subgroups of it. We apply it to the question whether a given finite graph (without multiple edges) has quantum symmetries in the sense of Banica. In order to do so, we run our Sinkhorn algorithm and check whether or not the resulting projections commute. We discuss the produced data and some questions for future research arising from it.

Keywords:

• compact quantum groups
• quantum automorphism groups of graphs
• quantum symmetries of graphs
• quantum permutation matrix
• Sinkhorn algorithm

Declaration of Interest

No potential conflict of interest was reported by the author(s).

Acknowledgments

The authors thank to Piotr Sołtan and Laura Mančinska for very useful discussions around some of the topics of this work. They would also like to acknowledge the hospitality of the Mathematisches Forschungsinstitut Oberwolfach during the workshop 1819 “Interactions between Operator Space Theory and Quantum Probability with Applications to Quantum Information,” where some of this research has been done. Furthermore, they thank to the referee for useful comments and suggestions.

Notes

1 By $C_6(2)$ we mean the cycle graph C₆, where additionally vertices at distance two in C₆ are connected. The graph denoted $\text{Trun}(K_4)$ is the truncated tetrahedral graph, $\text{antip}(\text{Trun}(K_4))$ its distance-three graph. We provide the adjacency matrices of all graph appearing in Table 1 in the supplementary material of the arXiv submission.

Additional information

Funding

I.N.’s research has been supported by the ANR, projects StoQ (grant number ANR-14-CE25-0003-01) and NEXT (grant number ANR-10-LABX-0037-NEXT). S.Sch and M.W. have been supported by the DFG project Quantenautomorphismen von Graphen. M.W. has been supported by SFB-TRR 195.