\documentclass[ALCO, Unicode]{cedram}
\usepackage{subcaption}
\usepackage{enumitem}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}
\mathtoolsset{centercolon}
\usepackage{tabu}
\usepackage{blkarray}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\DeclareMathOperator{\aut}{Aut}
\title{Quantum isomorphic strongly regular graphs from the \texorpdfstring{$E_8$}{E8} root system}
\author[\initial{S.} Schmidt]{\firstname{Simon} \lastname{Schmidt}}
\address{QMATH\\ Department of Mathematical Sciences\\ University of Copenhagen\\ Universitetsparken 5\\ 2100 Copenhagen \O\\ Denmark}
\curraddr{Faculty of Computer Science\\ Ruhr University Bochum\\ Universitätsstraße 150\\ 44801 Bochum\\ Germany}
\email{s.schmidt@rub.de}
\thanks{The author has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 101030346. He thanks David Roberson for helpful discussions on quantum isomorphisms and graph switching. He furthermore thanks the reviewer for valuable comments.}
% Key words and phrases:
\keywords{strongly regular graphs, quantum isomorphism, root systems, Godsil--McKay switching}
%% Mathematical classification (2000)
%% This will not be printed but can be useful for database search
\subjclass{05E30, 20B25, 05C25, 17B22, 20G42}
\begin{document}
\begin{abstract}
In this article, we give a first example of a pair of quantum isomorphic, non-isomorphic strongly regular graphs, that is, non-isomorphic strongly regular graphs having the same homomorphism counts from all planar graphs. The pair consists of the orthogonality graph of the $120$ lines spanned by the $E_8$ root system and a rank $4$ graph whose complement was first discovered by Brouwer, Ivanov and Klin. Both graphs are strongly regular with parameters $(120, 63, 30, 36)$. Using Godsil-McKay switching, we obtain more quantum isomorphic, non-isomorphic strongly regular graphs with the same parameters.
\end{abstract}
\maketitle
\section{Introduction}
The notion of quantum isomorphism of graphs was first introduced by Aterias et al in \cite{AMRSSV}. Two graphs are quantum isomorphic if there exists a perfect quantum strategy for the so called isomorphism game, a nonlocal game in which Alice and Bob want to convince a referee that they know an isomorphism between two graphs $G_1$ and $G_2$. Interestingly, Aterias et al constructed pairs of graphs for which there are perfect quantum strategies for the isomorphism game, but no perfect classical strategies. This shows that there are graphs that are quantum isomorphic, but not isomorphic.
It is well-known that two graphs are isomorphic if there exists a permutation matrix interchanging the adjacency matrices of the graphs. It was shown in \cite{AMRSSV} that two graphs are quantum isomorphic if and only if there exists a quantum permutation matrix $u$ interchanging the adjacency matrices of the two graphs. Here a quantum permutation matrix is a matrix $u\in M_n(\mathcal{A})$ with entries in some unital $C^*$-algebra $\mathcal{A}$ fulfilling $u_{ij}=u_{ij}^*=u_{ij}^2$ and $\sum_k u_{ik}=1_{\mathcal{A}}=\sum_k u_{ki}$, which was first studied in terms of quantum permutation groups by Wang \cite{WanSn}.
A completely combinatorial description of quantum isomorphism was given by Man\v{c}inska and Roberson in \cite{MRplanar}. They showed that quantum isomorphism is equivalent to having the same homomorphism counts from all planar graphs.
Despite having many equivalent formulations, only a few constructions of quantum isomorphic, non-isomorphic graphs are known. In \cite{AMRSSV}, the graphs where constructed from quantum solutions of binary constraint systems. Roberson and the author (\cite{RS}) used colored versions of the graphs constructed in \cite{AMRSSV} and a decoloring procedure to obtain new quantum isomorphic, non-isomorphic graphs, but those still come from quantum solutions of binary constraint systems.
A more general approach was presented by Musto, Reutter and Verdon in \cite{MRV}. In the article, they obtain quantum isomorphic graphs from a central type subgroup of the automorphism group of one of the graphs, having coisotropic stabilizers. They could find the graphs of \cite{AMRSSV} in this way, but they did not construct new examples. Recently, Chan and Martin \cite{CM} and Gromada \cite{G} have shown that Hadamard graphs of the same order are quantum isomorphic.
In this article, we will construct a new pair of quantum isomorphic, non-isomorphic graphs from a subgroup of the automorphism group of a graph. This subgroup is associated to $3$-tensor Pauli matrices and is a central type subgroup with coisotropic stabilizers. We will explicitly construct the quantum permutation matrix interchanging the adjacency matrices from the automorphisms in the subgroup. The quantum isomorphic graphs are both strongly regular with parameters $(120, 63, 30, 36)$ and known from the graph theory literature. The first graph is the orthogonality graph of the lines in the $E_8$ root system, see also \cite[Section 10.39]{BVM}. The second graph can be obtained from independent sets of the folded halved $8$-cube graph. Its complement was first discovered by Brouwer, Ivanov and Klin in \cite{BIK} as a graph from a quadric with a hole.
One can obtain one graph from the other by switching the underlying partial geometry, as shown by Mathon and Street \cite{MS}. Note that our first graph is isomorphic to $G_1$ and the second graph is isomorphic to $G_2$ -- $G_5$ in \cite[Table 2.2]{MS}.
%rank 3, rank 4 aut, but both rank 3 q aut group
We will also show that using Godsil-McKay switching on both graphs with the same, appropriate vertex partition preserves quantum isomorphism. We get more examples of quantum isomorphic, but non-isomorphic strongly regular graphs in this way.
The article is structured as follows. In Section \ref{secprelim}, we recall basic notions of graph theory and give the definition of quantum isomorphism of graphs. In Section \ref{secpairqiso}, we will first define the orthogonality graph of the lines in the $E_8$ root system and study a specific subgroup of the automorphism group. Then, we look at a graph coming from independent sets of the folded halved $8$-cube graph and give an alternative description of this graph. Using this description, we show that the two mentioned graphs are quantum isomorphic. Finally, we obtain more quantum isomorphic, non-isomorphic strongly regular graphs using Godsil-McKay switching in Section \ref{secswitching}.
\section{Preliminaries}\label{secprelim}
We start by recalling basic notions of graph theory. In this article, a graph $G$ is always finite and simple, that is, it has a finite vertex set $V(G)$ and has no multiple edges or loops. Thus, the edge set $E(G)$ is a subset of $V(G)\times V(G)$, where $(i,j)\in E(G)$ implies $(j,i)\in E(G)$. The \emph{adjacency matrix} $A_G$ of a graph $G$ is the matrix with entries $(A_G)_{ij}=1$ if $(i,j)\in E(G)$ and $(A_G)_{ij}=0$ otherwise. The complement of a graph $G$, which we denote by $\overline{G}$, is the graph with the same vertex set as $G$ and $(i,j)\in E(\overline{G})$ if and only if $(i,j)\notin E(G)$.
A \emph{clique} is a subset $C\subseteq V(G)$ of vertices such that all vertices in $C$ are adjacent. The \emph{clique number} of $G$ is the size of a largest clique in $G$. An \emph{independent set} is a subset $I\subseteq V(G)$ of vertices such that all vertices in $I$ are non-adjacent. The $\emph{independence number}$ of $G$ is the size of a largest independent set in $G$.
The vertex $j$ is called \emph{neighbor} of $i$ if $(i,j)\in E(G)$. A graph is \emph{$k$-regular} if every vertex has $k$ neighbors. A \emph{path} of length $m$ joining two vertices $i,k \in V(G)$ is a sequence of vertices $a_0, a_1, \dots, a_m$ with $i=a_0$, $k=a_m$ such that $(a_n,a_{n+1})\in E(G)$ for $n\in \{0, \dots m-1\}$. The \emph{distance} $d(i,k)$ between vertices $i,k\in V(G)$ denotes the length of a shortest path joining $i$ and $k$.
\begin{defi}
Let $G$ be a $k$-regular graph with $n$ vertices that is not $K_n$ or its complement. We say that the graph $G$ is \emph{strongly regular} if there exist $\lambda, \mu\in \N_0$ such that
\begin{itemize}
\item[(i)] adjacent vertices have $\lambda$ common neighbors,
\item[(ii)] non-adjacent vertices have $\mu$ common neighbors.
\end{itemize}
We then say that $G$ is strongly regular with parameters $(n, k, \lambda, \mu)$.
\end{defi}
A \emph{graph automorphism} is a bijection $\sigma:V(G)\to V(G)$ such that $(i,j)\in E(G)$ if and only if $(\sigma(i), \sigma(j))\in E(G)$. The set of graph automorphisms form a group, the \emph{automorphism group} $\aut(G)$. For a subgroup $K\subseteq \aut(G)$ and a vertex $v\in V(G)$, the \emph{stabilizer subgroup} of $K$ with respect to $v$ is $\mathrm{Stab}_K(v)=\{\sigma \in K \mid \sigma(v)=v\}$.
An \emph{isomorphism} between graphs $G_1$ and $G_2$ is a bijection $\varphi:V(G_1) \to V(G_2)$ such that $(i,j)\in E(G_1)$ if and only if $(\varphi(i), \varphi(j))\in E(G_2)$. It is easy to see that there exists an isomorphism between the graphs $G_1$ and $G_2$ if and only if there exists a permutation matrix $P_{\varphi}$ such that $A_{G_1}P_{\varphi}=P_{\varphi}A_{G_2}$.
\begin{defi}[\cite{WanSn}]
Let $\mathcal{A}$ be a unital $C^*$-algebra. A matrix $u\in M_n(\mathcal{A})$ is called \emph{quantum permutation matrix} or \emph{magic unitary} if the entries $u_{ij}\in \mathcal{A}$ are projections, i.e. $u_{ij}=u_{ij}^*=u_{ij}^2$ for all $i,j$ and for all $i$,
\begin{align*}
\sum_k u_{ik}=1_{\mathcal{A}}=\sum_k u_{ki}.
\end{align*}
\end{defi}
If $\mathcal{A}=\C$, then $u$ is a quantum permutation matrix if and only if it is a permutation matrix. For the quantum permutation matrices appearing in this article, we will have $\mathcal{A}=M_8(\C)$.
The concept of quantum isomorphism was first introduced in \cite{AMRSSV} as perfect quantum strategies of the isomorphism game. We will use an equivalent definition, established in \cite{LMR}.
\begin{defi}
Let $G_1$ and $G_2$ be graphs. We say that $G_1$ and $G_2$ are \emph{quantum isomorphic} if there exists a unital $C^*$-algebra $\mathcal{A}$ and a quantum permutation matrix $u\in M_n(\mathcal{A})$ such that $A_{G_1}u=uA_{G_2}$, which means $\sum_k(A_{G_1})_{ik}u_{kj}=\sum_k u_{ik}(A_{G_2})_{kj}$ for all $i\in V(G_1), j \in V(G_2)$.
\end{defi}
The following lemma gives an equivalent relation to $A_{G_1}u=uA_{G_2}$, see also \cite[Theorem 2.2 and Theorem 2.5]{LMR}. We give a proof similar to \cite[Proposition 2.1.3]{Sthesis} which gives the same equivalence for quantum automorphism groups.
\begin{lemm}\label{lemprod0}
Let $G_1$ and $G_2$ be graphs, $\mathcal{A}$ be a unital $C^*$-algebra and $u\in M_n(\mathcal{A})$ be a quantum permutation matrix. Then $A_{G_1}u=uA_{G_2}$ is equivalent to $u_{ij}u_{kl}=0$ if $(i,k)\notin E(G_1)$ and $(j,l)\in E(G_2)$ or vice versa.
\end{lemm}
\begin{proof}
Assume $A_{G_1}u=uA_{G_2}$ and let $(i,k)\notin E(G_1)$, $(j,l)\in E(G_2)$. From $A_{G_1}u=uA_{G_2}$, we get $\sum_{s;(i,s)\in E(G_1)}u_{sl}=\sum_{t:(t,l)\in E(G_2)} u_{it}$. Using this, we calculate
\begin{align*}
u_{ij}u_{kl}= u_{ij}\bigg(\sum_{t:(t,l)\in E(G_2)} u_{it}\bigg)u_{kl}=u_{ij}\bigg(\sum_{s;(i,s)\in E(G_1)}u_{sl}\bigg)u_{kl}=0.
\end{align*}
The first equality holds because we have $u_{ij}u_{it}=\delta_{jt}u_{ij}$ and $j$ is part of the sum since $(j,l)\in E(G_2)$. The last equality holds because $u_{sl}u_{kl}=\delta_{ks}u_{kl}$ and $k$ is not part of the sum since $(i,k)\notin E(G_1)$. One similarly gets $u_{ij}u_{kl}=0$ for $(i,k)\in E(G_1), (j,l)\notin E(G_2)$.
Now assume that we have $u_{ij}u_{kl}=0$ if $(i,k)\notin E(G_1)$ and $(j,l)\in E(G_2)$ or vice versa. Using this and $\sum_s u_{sl}=1_{\mathcal{A}}=\sum_t u_{it}$, we get
\begin{align*}
\sum_{t;(t,l)\in E(G_2)}u_{it}&=\bigg(\sum_{t;(t,l)\in E(G_2)}u_{it}\bigg)\bigg(\sum_{s;(i,s)\in E(G_1)}u_{sl}\bigg)\\
&=\sum_{s;(i,s)\in E(G_1)}\left(\sum_{t=1}^nu_{it}\right)u_{sl}\\
&=\sum_{s;(i,s)\in E(G_1)}u_{sl}
\end{align*}
for all $i,l$.
\end{proof}
Interestingly, quantum isomorphism of graphs is connected to homomorphism counts of planar graphs in the following way.
\begin{theo}\cite{MRplanar}
Let $G_1$ and $G_2$ be graphs. Then $G_1$ and $G_2$ are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph.
\end{theo}
As mentioned in the introduction, only few constructions of quantum isomorphic, non-isomorphic graphs are known. In the next section, we obtain a new pair of quantum isomorphic, non-isomorphic graphs.
\section{A pair of quantum isomorphic strongly regular graphs}\label{secpairqiso}
In this section, we construct a new pair of quantum isomorphic, non-isomorphic graphs. Those graphs are moreover strongly regular with parameters $(120, 63, 30, 36)$, giving us a first pair of quantum isomorphic strongly regular graphs. Both graphs are known from the graph theory literature. We will first define the graphs, give some properties and alternative descriptions and then prove that they are quantum isomorphic.
\subsection[Orthogonality graph]{The orthogonality graph of the lines in the \texorpdfstring{$E_8$}{E8} root system}
\begin{defi}\label{defGE8}
The $E_8$ root system $\Psi_{E_8}$ consists of the following $240$ vectors in $\mathbb{R}^8$:
\begin{align}\label{rootsystemE8}
&\pm e_i \pm e_j \text{ for } 1 \leq i