# Sheaves over complexes of groups and developability

Joshua L. Faber
<EMAIL_ADDRESS>
###### Abstract

We define the notion of a sheaf over a complex of groups. As an application,
we give a criterion for the developability of a complex of groups. When the
developability is witnessed by a morphism to $\mathrm{GL}(V)$ for some $V$,
our criterion is a characterization of developability.

##  1 Introduction

Motivated by Joel Friedman’s construction of sheaves over digraphs [Fri15] we
construct sheaves over categories. Our definition is deceptively simple to
state.

######  Definition 1.1.

Let $\mathcal{C}$ be a category, $\mathbb{K}$ a field, and $\mathbb{K}$-Vect
the category of $\mathbb{K}$-vector spaces. A sheaf over $\mathcal{C}$ is a
functor $\mathcal{F}:\mathcal{C}\rightarrow\mathbb{K}$-Vect.

In [BH99, III.$\mathcal{C}$ 2.1 p.535] Bridson and Haefliger define a complex
of groups $\Lambda$ and in [BH99, III.$\mathcal{C}$ 2.8 p.538] define what we
call the B.H. category $\mathcal{C}\Lambda$. The B.H. category
$\mathcal{C}\Lambda$ is constructed from $\Lambda$ and encodes the data of
$\Lambda$ into the structure of the space $\mathcal{C}\Lambda$ so that
$\pi_{1}(\Lambda)\cong\pi_{1}(\mathcal{C}\Lambda)$. By placing a sheaf
$\mathcal{F}$ over $\mathcal{C}\Lambda$ we provide a functor from
$\mathcal{C}\Lambda$ to the category $\mathbb{K}$-Vect. Functors from the B.H.
category $\mathcal{C}\Lambda$ of a complex of groups $\Lambda$ are not a new
area of research as the next two examples show. Let $\Lambda$ be a complex of
groups, $\mathcal{C}\Lambda$ the B.H. category and $\mathrm{Ab}$ the category
of abelian groups. In [Hae92, 4.1.5 p.298] Haefliger defines a
$\Lambda$-module $\mathcal{M}$ as a functor
$\mathcal{M}:\Lambda\rightarrow\mathrm{Ab}$. Let $\Lambda$, $\Lambda^{\prime}$
be complexes of groups, $\mathcal{C}\Lambda$, $\mathcal{C}\Lambda^{\prime}$
their B.H categories and $\phi:\Lambda\rightarrow\Lambda^{\prime}$ a morphism
of complexes of groups. In [BH99, III.$\mathcal{C}$. 2.4 p.536] Bridson and
Haefliger show how $\phi$ induces a functor
$\widehat{\phi}:\mathcal{C}\Lambda\rightarrow\mathcal{C}\Lambda^{\prime}$
between B.H categories which carries the same data as $\phi$ but translated
into category theory.

Unlike graphs of groups from Bass–Serre theory, complexes of groups cannot
always be realized as the result of a global quotient. When $\Lambda$ can be
realized as the result of a global quotient we say that $\Lambda$ is
_developable_. In Bass–Serre Theory a graph of groups is developable when one
can construct a Bass–Serre tree. The _fundamental theorem of Bass–Serre
theory_ states that all graphs of groups are developable [BH99,
III.$\mathcal{C}$ 2.17 p.544]. When $\Lambda$ is developable the usual
covering space theory of spaces works when we translate to the side of the
B.H. category $\mathcal{C}\Lambda$. In [BH99, III.$\mathcal{C}$ 2.15 p.544]
Bridson and Haefliger characterize the development of a complex of groups
$\Lambda$ in terms of a group $G$ which is a _witness_ to the development of
$\Lambda$, see Theorem 2.24.

In this paper we show that when the group $\mathrm{GL}(V)$ is a witness to the
developability of $\Lambda$ we can characterize the developability of
$\Lambda$ in terms of a sheaf $\mathcal{F}$ that satisfies the following
properties. Let $\Lambda$ be a complex of groups, $\mathcal{C}\Lambda$ the
B.H. category and $\mathcal{F}$ a sheaf. If there exists an $n\in\mathbb{N}$
so that for each $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ we have
$\dim(\mathcal{F}(\sigma))=n$ then $\mathcal{F}$ has constant rank. For
$\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ let
$S_{\sigma}\subseteq\mathcal{C}\Lambda$ be the full subcategory over $\sigma$.
If for each $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ the restriction
$\mathcal{F}|_{S_{\sigma}}:S_{\sigma}\rightarrow\mathbb{K}\mathrm{-Vect}$ is
injective then $\mathcal{F}$ is injective on local groups. We say that
$\mathcal{F}$ satisfies the _dev properties_ if _i_) $\mathcal{F}$ has
constant rank, _ii_) for each morphism
$\lambda\in\mathrm{Mor}(\mathcal{C}\Lambda)$ the linear map
$\mathcal{F}(\lambda)$ is invertible, and _iii_) $\mathcal{F}$ is injective on
local groups. We can now state our main theorem.

######  Theorem A.

Let $\Lambda$ be a complex of groups and $\mathcal{C}\Lambda$ the B.H.
category. The group $\mathrm{GL}(V)$ is a witness to the developability of
$\Lambda$ if and only if there exists a sheaf $\mathcal{F}$ over
$\mathcal{C}\Lambda$ satisfying the dev-properties.

###  1.1 Acknowledgements

We would like to thank Michelle Chu whose suggestions helped inspire Lemma 3.7
and to Daniel Groves whose continuous support helped guide this paper.

##  2 Background

Scwols were first introduced by Bridson and Haefliger in [BH99,
III.$\mathcal{C}$ 1 p.520] to define a complex of groups construction.
Complexes of groups are abstract objects which are natural generlizations of
graphs of groups. Given a polyhedral complex $\mathcal{M}$ there is a process
that constructs a scwol $\mathcal{X}$ from $\mathcal{M}$ and if given a group
$G$ which acts on $\mathcal{M}$ we can construct a complex of groups $\Lambda$
from the quotient space $G\setminus\mathcal{X}$. There is no loss in data when
constructing $\Lambda$ over a scwol $\mathfrak{C}$ in place of a polyhedral
complex $\mathcal{M}$. We start with the definition of a scwol $\mathfrak{C}$
and the construction of a scwol from a complex $\mathcal{M}$. We then define
complexes of groups $\Lambda$ as well as their associated B.H. categories
$\mathcal{C}\Lambda$ and give results concerning these gadgets. The following
can be found in [BH99, III.$\mathcal{C}$ 1 p 520],

######  Definition 2.1.

A scwol $\mathcal{X}$, is a small category such that,

  * •

for all composable arrows $a,b\in\mathrm{Arr}(\mathcal{X})$ if $i(a)\neq t(a)$
and $i(b)\neq t(b)$ then $i(ab)\neq t(ab)$; and

  * •

for all arrows $a\in\mathrm{Arr}(\mathcal{X})$ if $i(a)=t(a)$ then $a$ is the
identity morphism.

######  Definition 2.2.

Let $\mathcal{X}$ be a scwol, $k\in\mathbb{N}$ a natural number then
$E^{(k)}(\mathfrak{C})$ is the set of sequences $(a_{1},\cdots,a_{n})$ of
composable arrows in $\mathcal{X}$ where $i(a_{l})=t(a_{l+1})$ for $1\leq
l<k$.

Given a polyhedral complex $\mathcal{M}$ we construct a scwol through the
following construction,

######  Construction 2.3.

Let $\mathcal{M}$ be a polyhedral complex. The complex to scwol construction
$\mathfrak{M}$ takes $\mathcal{M}$ and constructs the scwol
$\mathfrak{M}(\mathcal{M})$ by taking the first barycentric subdivision of
$\mathcal{M}$ and,

  * •

associating the barycenter of each cell $\sigma\in\mathcal{M}$ to an object
$\sigma\in\mathrm{Obj}(\mathfrak{M}(\mathcal{M}))$; and

  * •

associating each $1$-simplex of the barycentric subdivision of $\mathcal{M}$
to an arrow $a\in\mathrm{Arr}(\mathfrak{M}(\mathcal{M}))$.

A directed graph $\Gamma$ is a $1$-dimensional polyhedral complex. In [Fri15,
1 p.6] Joel Friedman defines a sheaf over $\Gamma$ by placing a
$\mathbb{F}$-vector space over each vertex, a $\mathbb{F}$-vector space over
each edge, and a linear morphism over each attaching map. We give Friedman’s
definition below,

######  Definition 2.4 (Joel Friedman, [Fri15, 1 p.6]).

A sheaf $\mathcal{F}$ of finite dimensional $\mathbb{F}$-vector spaces over a
digraph $\Gamma$ is,

  * (1)

a finite dimensional $\mathbb{F}$-vector space $\mathcal{F}(v)$ for each $v\in
V\Gamma$;

  * (2)

a finite dimensional $\mathbb{F}$-vector space $\mathcal{F}(e)$ for each $e\in
E\Gamma$;

  * (3)

a linear morphism
$\mathcal{F}(t,e):\mathcal{F}(e)\rightarrow\mathcal{F}(t(e))$ for each edge
$e\in E\Gamma$; and

  * (4)

a linear morphism
$\mathcal{F}(h,e):\mathcal{F}(e)\rightarrow\mathcal{F}(h(e))$ for each edge
$e\in E\Gamma$.

Let $\mathfrak{C}$ be the scwol constructed from $\Gamma$ as in 2.3. In this
situation, it is easy to see that our definition of a sheaf from Definition
1.1 is equivalent to Friedman’s.

We now give the definition of complexes of groups. Complexes of groups are
natural generalizations of graphs of groups from Bass–Serre theory. Our
definition is derived from [BH99, III.$\mathcal{C}$ 2.1 p.535].

######  Definition 2.5.

A complex of groups $\Lambda=\big{(}\mathfrak{C}$, $G_{\sigma}$, $\psi_{a}$,
$g_{a,b}\big{)}$ is,

  * •

A scwol $\mathfrak{C}$;

  * •

For each $\sigma\in\mathrm{Obj}(\mathfrak{C})$ a group $G_{\sigma}$ called the
local group at  $\sigma$;

  * •

For each $a\in\mathrm{Arr}(\mathfrak{C})$ an injective homomorphism
$\psi_{a}:G_{t(a)}\rightarrow G_{i(a)}$; and

  * •

For each pair of composable edges $(a,b)\in E^{(2)}(\mathfrak{C})$, a twisting
element $g_{a,b}\in G_{t(a)}$ which satisfies,

    * –

$\mathrm{Ad}(g_{a,b})\psi_{ab}=\psi_{a}\psi_{b}$

where $\mathrm{Ad}(g_{a,b})$ is the conjugation by $g_{a,b}$ in $G_{t(a)}$,

    * –

For each triple $(a,b,c)\in E^{(3)}(\mathfrak{C})$ of composable elements we
have the cocycle condition:

$\psi_{a}\big{(}g_{b,c}\big{)}g_{a,bc}=g_{a,b}g_{ab,c}$

One way to construct a complex of groups is via a group action on a swol, see
[BH99, III.$\mathcal{C}$ 1.11 p.528].

In [BH99, III.$\mathcal{C}$ 2.8 p.538] Bridson and Haefliger construct a
category $\mathcal{C}\Lambda$ from a complex of groups $\Lambda$. We give the
definition of $\mathcal{C}\Lambda$, the B.H category, below.

######  Definition 2.6.

Let $\Lambda=\big{(}\mathfrak{C},G_{\sigma},\psi_{a},g_{a,b}\big{)}$ be a
complex of groups over a scwol $\mathfrak{C}$. The B.H. category of $\Lambda$
is the category $C\Lambda$ given by,

  * •

$\mathrm{Obj}\big{(}C\Lambda\big{)}=\mathrm{Obj}(\mathfrak{C})$;

  * •

$\mathrm{Arr}\big{(}C\Lambda\big{)}=\big{\\{}(g,\alpha):\alpha\in\mathrm{Mor}\big{(}\mathfrak{C}\big{)}$,
$g\in G_{t(\alpha)}\big{\\}}$ with the adjacency relations;

    * –

$i(g,\alpha)=i(\alpha)$

    * –

$t(g,\alpha)=t(\alpha)$

For arrows $(\alpha,g)$, $(\beta,h)\in\mathrm{Arr}(C\Lambda)$,
$i(\alpha)=t(\beta)$ we define their composition,

$(g,\alpha)(h,\beta)=(g\psi_{\alpha}(h)g_{a,b},\alpha\beta),\hskip
7.22743ptg_{a,b}\in G_{t(a)}$

Let $\pi_{1}(\Lambda)$ be the fundamental group of a complex of groups as in
[BH99, II.$\mathcal{C}$ 3.7 p.549] and $\pi_{1}(\mathcal{C}\Lambda)$ the
fundamental group of the category as defined in [BH99, III.$\mathcal{C}$ A.13
587]. We get,

######  Theorem 2.7.

[BH99, III.$\mathcal{C}$ A.12 p.578] Let $\Lambda$ be a complex of groups and
$\mathcal{C}\Lambda$ the B.H. category. Then,

$\pi_{1}(\Lambda)\cong\pi_{1}(\mathcal{C}\Lambda)$

######  Definition 2.8.

Let $\mathfrak{C}$ and $\mathfrak{C}^{\prime}$ be scwols.

  * •

A morphism of scwols $f:\mathfrak{C}\rightarrow\mathfrak{C}^{\prime}$ is a
functor.

  * •

A non-degenerate morphism of scwols is a functor such that for each
$v\in\mathrm{Obj}(\mathfrak{C})$ there is a bijection of sets,

$\big{\\{}a\in\mathrm{Arr}(\mathfrak{C}):i(a)=v\big{\\}}\leftrightarrow\big{\\{}a^{\prime}\in\mathrm{Arr}(\mathfrak{C}^{\prime}):i(a)=f(v)\big{\\}}.$

We define a morphism of complexes of groups over a morphism of scwols.

######  Definition 2.9.

[BH99, III.$\mathcal{C}$.2.4, p. 536] Let
$\Lambda=(\mathfrak{C},G_{\sigma},\psi_{a},g_{a,b})$ and
$\Lambda^{\prime}=(\mathfrak{C}^{\prime},G_{\sigma}^{\prime},\psi_{a}^{\prime},g_{a,b}^{\prime})$
be a complexes of groups and $f:\mathfrak{C}\rightarrow\mathfrak{C}^{\prime}$
a functor. A (possibly degenerate) morphism of complexes of groups
$\phi:(\phi_{\sigma},\phi(a)):\Lambda\rightarrow\Lambda^{\prime}$ over $f$
consists of:

  * •

a homomorphism $\phi_{\sigma}:G_{\sigma}\rightarrow G_{f(\sigma)}$ for each
$\sigma\in\mathrm{Obj}(\mathfrak{C})$; and

  * •

an element $\phi(a)\in G_{t(f(a))}$ for each $a\in\mathrm{Arr}(\mathfrak{C})$
such that,

    * –

$\mathrm{Ad}(\phi(a))\psi_{f(a)}(\phi_{i(a)})=\phi_{t(a)}\psi_{a}$,

where $\mathrm{Ad}(\phi(a))$ is the conjugation by $\phi(a)$ in
$G_{t(f(a)))}$,

and for each pairs of composable arrows $(a,b)\in E^{(2)}(\mathfrak{C})$,

    * –

$\phi_{t(a)}(g_{a,b})\phi(ab)=\phi(a)\psi_{f(a)}(\phi(b))g_{f(a),f(b)}$.

When each of the homomorphisms are injective we get,

######  Definition 2.10.

Let $\phi=(\phi_{\sigma},\phi(a)):\Lambda\rightarrow\Lambda^{\prime}$ be a
morphism of complexes of groups. If each homorphism $\phi_{\sigma}$ is
injective we say that $\phi$ is injective on local groups.

A B.H. category is constructed to carry the same data as the complex of groups
it represents. It follows that a morphism of complexes of groups induces a
functor between their B.H. categories. This is the content of the next
definition.

######  Definition 2.11.

[BH99, III.$\mathcal{C}$ 2.8 p.538] Let $\Lambda$, $\Lambda^{\prime}$ be
complexes of groups and $\mathcal{C}\Lambda$, $\mathcal{C}\Lambda^{\prime}$
their B.H. categories. A morphism of complexes of groups
$\phi:\Lambda\rightarrow\Lambda^{\prime}$ induces the induced functor between
their B.H. categories
$\widehat{\phi}:\mathcal{C}\Lambda\rightarrow\mathcal{C}\Lambda^{\prime}$ and
a functor between B.H. categories
$\widehat{\phi}:\mathcal{C}\Lambda\rightarrow\mathcal{C}\Lambda^{\prime}$
induces the induced morphism between the complexes of groups they represent
$\phi:\Lambda\rightarrow\Lambda^{\prime}$.

The importance of our next lemma is to provide a translation between complexes
of groups and their B.H. categories. Each morphism of complexes of groups
induces a functor between their B.H. categories that carries the same data and
conversely each functor between B.H. categories induces a morphism of
complexes of groups that carries the same data.

######  Lemma 2.12 (cf, [BH99, III.$\mathcal{C}$ 2.8 p.538]).

The procedure of constructing B.H. categories from complexes of groups induces
a bijection between morphism of complexes of groups and functors between their
B.H. categories.

We introduce the trivial scwol which aids us in subsequent definitions.

######  Definition 2.13.

The trivial scwol $\mathfrak{P}$ is a scwol with one object and no arrows.

Given a group $G$ we construct the following complex of groups,

######  Definition 2.14.

Let $G$ be a group. The complex of groups constructed from the group $G$ is
the (unique!) complex of groups $\Theta(G)$ over $\mathfrak{P}$ with local
group $G$.

Let $\Lambda$ be a complex of groups, $G$ a group and
$\phi:\Lambda\rightarrow\Theta(G)$ a morphism. Due to the lack of composable
edges in $\Theta(G)$ the definition of a morphism becomes (cf. [BH99,
III.$\mathcal{C}$ 2.5 p.537])

######  Definition 2.15.

A morphism $\phi=(\phi_{\sigma},\phi(a))$ from a complex of groups $\Lambda$
to $\Theta(G)$ consists of a homorphism $\phi_{\sigma}:G_{\sigma}\rightarrow
G$ for each $\sigma\in\mathrm{Obj}(\Lambda)$ and an element $\phi(a)\in G$ for
each $a\in\mathrm{Arr}(\Lambda)$ such that

$\phi_{t(a)}\psi_{a}=\mathrm{Ad}\big{(}\phi(a)\big{)}\phi_{i(a)}\hskip
7.22743pt\text{ and }\hskip
7.22743pt\phi_{t(a)}(g_{a,b})\phi(ab)=\phi(a)\phi(b)$

Let $\Lambda$ be a complex of groups over a scwol $\mathfrak{C}$,
$\sigma\in\mathrm{Obj}(\mathfrak{C})$, $\mathcal{C}\Lambda$ the B.H. category
and $\sigma^{\prime}\in\mathrm{Obj}(\mathcal{C}\Lambda)$ the object
constructed from $\sigma$. Each local group $G_{\sigma}$ of $\Lambda$
corresponds to a full subcategory over each
$\sigma^{\prime}\in\mathcal{C}\Lambda$. We make this precise.

######  Definition 2.16.

Let $\Lambda$ be a complex of groups over a scwol $\mathfrak{C}$ and
$\mathcal{C}\Lambda$ the B.H category with
$\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$. Then $S_{\sigma}$ is the full
subcategory of $\mathcal{C}\Lambda$ over $\sigma$.

For any group $G$ we can construct the following category,

######  Definition 2.17.

Let $G$ be a group. The category constructed from the group $\widehat{G}$ is
defined by taking,

  * •

$\mathrm{Obj}(\widehat{G})=\tau_{G}$

  * •

$\mathrm{Arr}(\widehat{G})=\big{\\{}\alpha_{G}(g):g\in G\big{\\}}$

  * •

With composition defined,

$\alpha_{G}(g)\alpha_{G}(h)=\alpha_{G}(gh)$

Observe that for a group $G$ we obtain,

######  Lemma 2.18.

Let $G$ be a group, $\Theta(G)$ the complex of groups construct from the
group, $\mathcal{C}\Theta(G)$ the B.H. category and $\widehat{G}$ the category
constructed from the group. Then $\mathcal{C}\Theta(G)$ and $\widehat{G}$ are
isomorphic.

######  Definition 2.19.

Let $G$ be a group, $\Theta(G)$ the complex of groups constructed from $G$,
$\mathcal{C}\Theta(G)$ the B.H. category and $\widehat{G}$ the category
constructed from $G$. The B.H. to hat map is the functor that realizes the
isomorphism of Lemma 2.18 and is given by,

$\psi_{G}:\mathcal{C}\Theta(G)\rightarrow\widehat{G}$

such that,

  * •

for $\sigma\in\mathrm{Obj}(\mathcal{C}\Theta(G))$,
$\psi_{G}(\sigma)=\tau_{G}$; and

  * •

for $(g,\mathbbm{1}_{\sigma})\in\mathrm{Arr}(\mathcal{C}\Theta(G))$,
$\psi_{G}((g,\mathbbm{1}_{\sigma}))=\alpha_{G}(g)$.

Let $\Lambda$ be a complex of groups over a scwol $\mathfrak{C}$, $G_{\sigma}$
a local group of $\Lambda$ with $\sigma\in\mathrm{Obj}(\mathfrak{C})$,
$\mathcal{C}\Lambda$ the B.H. category and
$S_{\sigma}\subseteq\mathcal{C}\Lambda$ the full subcategory over
$\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$. We get,

######  Lemma 2.20.

For $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$,

$S_{\sigma}\cong\mathcal{C}\Theta(\mathrm{Aut}_{\mathcal{C}\Lambda}(\sigma))\cong\mathcal{C}\Theta(G_{\sigma})\cong\widehat{G}_{\sigma}$

From Lemma 2.20 we define,

######  Definition 2.21.

The full subcategory to B.H. category functor is,

$\Upsilon_{S_{\sigma}}:S_{\sigma}\rightarrow\mathcal{C}\Theta(G_{\sigma})$

Let $\Lambda$ be a complex of groups over a scwol $\mathfrak{C}$, $G$ a group.
for $\sigma\in\mathrm{Obj}(\mathfrak{C})$ and $a\in\mathrm{Arr}(\mathfrak{C})$
the map $\phi=(\phi_{\sigma},\phi(a)):\Lambda\rightarrow\Theta(G)$ is a
morphism of complexes of groups with local group homomorphism
$\phi_{\sigma}:G_{\sigma}\rightarrow G$. By Lemma 2.11, $\phi$ induces the
functor $\widehat{\phi}:\mathcal{C}\Lambda\rightarrow\mathcal{C}\Theta(G)$ and
the map $\phi_{\sigma}$ induces the functor
$\widehat{\phi}_{\sigma}:\mathcal{C}\Theta(G_{\sigma})\rightarrow\mathcal{C}\Theta(G)$.
Let $\psi_{G}:\mathcal{C}\Theta(G)\rightarrow\widehat{G}$ be the B.H. to hat
map from Lemma 2.18 and
$\Upsilon_{S_{\sigma}}:S_{\sigma}\rightarrow\mathcal{C}\Theta(G_{\sigma})$ the
full subcategory to B.H. category functor from Definition 2.21. We define the
following two functors,

######  Definition 2.22.

The cat to hat map is,

  * $\widehat{\Psi}_{G}=\widehat{\psi}_{G}\circ\widehat{\phi}:\mathcal{C}\Lambda\rightarrow\mathcal{C}\Theta(G)\rightarrow\widehat{G}$

For $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ the local cat to hat map is,

  * $\widehat{\Psi}_{G_{\sigma}}=\widehat{\psi}_{G}\circ\widehat{\phi}_{\sigma}\circ\widehat{\Upsilon}_{S_{\sigma}}:S_{\sigma}\rightarrow\mathcal{C}\Theta(G_{\sigma})\rightarrow\widehat{G}_{\sigma}\rightarrow\widehat{G}$

Observe that by restricting $\mathcal{C}\Lambda$ to the full subcategory
$S_{\sigma}$ over $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ we get,

$\widehat{\Psi}_{G}|_{S_{\sigma}}=\widehat{\Psi}_{G_{\sigma}}$

The definition of a group $G$ acting of a scwol $\mathcal{X}$ is stronger than
the group of automorphisms $\mathrm{Aut}(\mathcal{X})$ of $\mathcal{X}$ so
that the quotient category $G\setminus\mathcal{X}$ is always a scwol. See
[BH99, III.$\mathcal{C}$ 1.11 p.528] for the definition of a group $G$ acting
on a scwol $\mathcal{X}$. The most natural way to build a complex of groups
$\Lambda=(\mathcal{Y},G_{\sigma},\psi_{a},g_{a,b})$ is to construct $\Lambda$
over a quotient scwol $\mathcal{Y}=G\setminus\mathcal{X}$. Here the local
groups $G_{\sigma}$ of $\Lambda$ are stabilizers in $G$ of objects in
$\mathcal{X}$. Furthermore, when a complex of groups $\Lambda$ is the result
of a global quotient we say that $\Lambda$ is developable. We give the precise
definition below.

######  Definition 2.23.

A complex of groups $\Lambda=(\mathcal{Y},G_{\sigma},\psi_{a},g_{a,b})$ is
called developable if it is isomorphic to a complex of groups that is
associated to an action of a group $G$ on a scwol $\mathcal{X}$ with
$\mathcal{Y}=G\setminus\mathcal{X}$ the quotient scwol. That is, $\mathcal{Y}$
is the scwol for $\Lambda$.

Not all complexes of groups are developable. See Example (5) [BH99, II.12.17
(5) p.378] for an enxample of a non-developable complex of groups.

In [BH99, III.$\mathcal{C}$ 2.15 p.544] Bridson and Haefliger give the
following characterization of developability of a complex of groups.

######  Theorem 2.24.

A complex of groups $\Lambda$ is developable if and only if there exists a
group $G$ and a morphism $\phi:\Lambda\rightarrow\Theta(G)$ which is injective
on local groups.

We make a definition so that we may phrase developability of a complex of
groups in terms of the group $G$.

######  Definition 2.25.

Let $\Lambda$ be a developable complex of groups and $G$ a group such that
there exists a morphism $\phi:\Lambda\rightarrow\Theta(G)$ that is injective
on local groups. Then we say that $G$ witnesses the developability of
$\Lambda$.

In case of an ordinary complex take $G=\\{1\\}$ (or any other groups like
$\mathrm{GL}(V)$, with all homomorphisms trivial). So although the morhpism
$\phi:\pi_{1}(\Lambda)\rightarrow G$ is injective on local groups, $\phi$
needn’t be injecitive.

In the next section we define sheaves.

##  3 Sheaves

We restate our main definition, See 1.1

The B.H. category is constructed to carry the data of a complex of groups.
When $\Lambda$ is a complex of groups a sheaf over $\Lambda$ will mean a sheaf
over $\mathcal{C}\Lambda$.

We define sheaf constructions that we use later in this paper.

######  Definition 3.1.

Let $\mathcal{C}$, $\mathcal{C}^{\prime}$ be categories and
$\phi:\mathcal{C}\rightarrow\mathcal{C}^{\prime}$ a functor. Let $\mathcal{F}$
be a sheaf on $\mathcal{C}^{\prime}$. We define the pullback sheaf
$\phi^{*}\mathcal{F}$ on $\mathcal{C}$ to be.

$\phi^{*}\mathcal{F}=\mathcal{F}\circ\phi$

######  Definition 3.2.

Let $\mathcal{F}$ be a sheaf over a category $\mathcal{C}$ and let
$n\in\mathbb{N}$. If for each $\sigma\in\mathrm{Obj}(\mathcal{C})$ we have
$\dim(\mathcal{F}(\sigma))=n$ then $\mathcal{F}$ has constant rank.

Let $\Lambda$ be a complex of groups and $\mathcal{C}\Lambda$ the B.H.
category. Since the full subcategory $S_{\sigma}$ over
$\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ carries data of the local group
$G_{\sigma}$ of $\Lambda$ we obtain a sheaf version of Definition 2.10.

######  Definition 3.3.

Let $\mathcal{C}$ be a category and $\mathcal{F}$ a sheaf over $\mathcal{C}$.
If for each $\sigma\in\mathrm{Obj}(\mathcal{C})$ the restriction
$\mathcal{F}|_{S_{\sigma}}:S_{\sigma}\rightarrow\mathbb{K}\mathrm{-Vect}$ is
injective then $\mathcal{F}$ is said to be injective on local groups.

We summarize the previous sheaf properties into a single definition along with
one more property.

######  Definition 3.4.

Let $\mathcal{F}$ be a sheaf. We say that $\mathcal{F}$ satisfies the dev
properties if,

  * •

$\mathcal{F}$ has constant rank;

  * •

if for each $\lambda\in\mathrm{Mor}(\mathcal{C}\Lambda)$,
$\mathcal{F}(\lambda)$ is invertible; and if

  * •

$\mathcal{F}$ is injective on local groups.

Observe that when we construct a category from a group $G$ we obtain,

######  Example 3.5.

Let $G$ be a group, $\widehat{G}$ the category constructed from $G$ as in
Definition 2.17. Then a sheaf $\mathcal{F}$ over $\widehat{{G}}$ is a linear
representation of $G$.

Let $\mathrm{GL}(V)$ be the general linear group over the vector space $V$ and
let $\widehat{\mathrm{GL}(V)}$ be the category constructed from
$\mathrm{GL}(V)$.

######  Definition 3.6.

The tautological sheaf is the sheaf
$\mathcal{Z}_{taut}^{V}:\widehat{\mathrm{GL}(V)}\rightarrow\mathbb{K}\mathrm{-Vect}$
so that,

  * •

$\mathcal{Z}_{taut}^{V}\big{(}\tau_{\mathrm{GL}(V)}\big{)}=V$ for
$\tau_{\mathrm{GL}(V)}\in\mathrm{Obj}(\widehat{\mathrm{GL}(V)})$; and

  * •

$\mathcal{Z}^{V}_{taut}\big{(}\alpha_{\mathrm{GL}(V)}(\rho)\big{)}=\rho$ for
$\alpha_{\mathrm{GL}(V)}(\rho)\in\mathrm{Arr}(\widehat{\mathrm{GL}(V)})$

.

Recall that $\mathrm{GL}(V)\subset\mathrm{Arr}(\mathbb{K}\mathrm{-Vect})$ so
$\alpha_{\mathrm{GL}(V)}(\rho)\in\mathrm{Arr}(\widehat{\mathrm{GL}(V)})$ where
$\rho\in\mathrm{GL}(V)$. When we pass $\alpha_{\mathrm{GL}(V)}(\rho)$ through
the tautological sheaf $\mathcal{Z}_{taut}^{V}$ we recover the group element
$\mathcal{Z}^{V}_{taut}\big{(}\alpha_{\mathrm{GL}(V)}(\rho)\big{)}=\rho\in\mathrm{GL}(V)$.

######  Lemma 3.7.

Let $\Lambda$ be a developable complex of groups such that $\mathrm{GL}(V)$
witnesses the developability of $\Lambda$, let
$\phi:\Lambda\rightarrow\Theta(\mathrm{GL}(V))$ be a morphism that is
injective on local groups and $\widehat{\Psi}_{G}$ the cat to hat map of
Definition 2.22. Then $\widehat{\Psi}_{G}\circ\mathcal{Z}^{V}_{taut}$ is a
sheaf that satisfies the dev-properties.

###### Proof.

The complex of groups $\Theta(\mathrm{GL}(V))$ is constructed over the trivial
scowl $\mathfrak{P}$. The trivial scwol has one object and no arrows so the
rank of $\widehat{\Psi}^{\ast}\circ\mathcal{Z}^{V}_{taut}$ is constant and
each arrow represents an invertible group element of $\mathrm{GL}(V)$ so all
morphisms are invertible. We proceed to prove injectivity on local groups.

Let $\mathfrak{C}$ be the scwol that $\Lambda$ is over,
$\sigma\in\mathrm{Obj}(\mathfrak{C})$, $a\in\mathrm{Arr}(\mathfrak{C})$ and
recall that for $\phi=(\phi_{\sigma},\phi(a))$ the map
$\phi_{\sigma}:G_{\sigma}\rightarrow\mathrm{GL}(V)$ is a homomorphism and
$\widehat{\Psi}_{G_{\sigma}}:S_{\sigma}\rightarrow\widehat{\mathrm{GL}(V)}$ is
the local cat to hat map from Definition 2.22.

Since $\widehat{\Psi}_{G}|_{S_{\sigma}}=\widehat{\Psi}_{G_{\sigma}}$, it
suffices to show that for all $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ each
$\widehat{\Psi}_{G_{\sigma}}^{\ast}\circ\mathcal{Z}^{V}_{taut}$ is injective.

For $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ and
$(k,\mathbbm{1}_{\sigma})\in\mathrm{Arr}(S_{\sigma})$ we have the following
chain of equalities,

  * (1)

$\phi_{\sigma}(k)=\mathcal{Z}^{V}_{taut}\big{(}\alpha_{\mathrm{GL}(V)}(\phi_{\sigma}(k))\big{)}=\widehat{\Psi}_{G_{\sigma}}^{\ast}\circ\mathcal{Z}^{V}_{taut}\big{(}(k,\mathbbm{1}_{\sigma})\big{)}$.

Let
$(g,\mathbbm{1}_{\sigma}),(h,\mathbbm{1}_{\sigma})\in\mathrm{Arr}(S_{\sigma})$
so
$\widehat{\Psi}_{G_{\sigma}}^{\ast}\circ\mathcal{Z}^{V}_{taut}\big{(}(g,\mathbbm{1}_{\sigma})\big{)}=\widehat{\Psi}_{G_{\sigma}}^{\ast}\circ\mathcal{Z}^{V}_{taut}\big{(}(h,\mathbbm{1}_{\sigma})\big{)}$.
From equation $(1)$ above we get,

$\displaystyle\phi_{\sigma}(g)$
$\displaystyle=\mathcal{Z}^{V}_{taut}\big{(}\alpha_{\mathrm{GL}(V)}(\phi_{\sigma}(g))\big{)}$
$\displaystyle=\widehat{\Psi}_{G_{\sigma}}^{\ast}\circ\mathcal{Z}^{V}_{taut}\big{(}(g,\mathbbm{1}_{\sigma})\big{)}$
$\displaystyle=\widehat{\Psi}_{G_{\sigma}}^{\ast}\circ\mathcal{Z}^{V}_{taut}\big{(}(h,\mathbbm{1}_{\sigma})\big{)}$
$\displaystyle=\mathcal{Z}^{V}_{taut}\big{(}\alpha_{\mathrm{GL}(V)}(\phi_{\sigma}(h))\big{)}$
$\displaystyle=\phi_{\sigma}(h)$

We see that $\phi_{\sigma}(g)=\phi_{\sigma}(h)$. Since $\phi$ is injective on
local groups then $\phi_{\sigma}$ is injective. It follows that $g=h$ and
hence $\widehat{\Psi}_{G_{\sigma}}^{\ast}\circ\mathcal{Z}^{V}_{taut}$ is
injective. Since the choice of $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ was
arbitrary it follows that
$\widehat{\Psi}_{G}^{\ast}\circ\mathcal{Z}^{V}_{taut}$ is injective on local
groups. ∎

Proving the other direction of Theorem A will be the content of the next
section.

##  4 Proof of Theorem A.

We restate and prove Theorem A. The proof technique will be familiar to
constructing the fundamental group of a graph via a maximal tree. We take the
maximal tree $T$ of a scwol $\mathfrak{C}$ that a complex of groups $\Lambda$
is defined over and witness how the data interacts when observed through a
sheaf. In Subsection 4.1 we give the technical definitions concerning the
scwol $\mathfrak{C}$. In Subsection 4.2 we define functors that will then be
to define sheaf paths and a morphism of complexes of groups in Subsection 4.3
which allows us to prove Theorem A in Subsection 4.4.

###  4.1 Edge paths and a Tree

In this subsection we define edge paths of a scwol $\mathcal{X}$ and give the
definition of a maximal tree $T$ of $\mathcal{X}$. We use $T$ in Subsection
4.3 to construct a morphism of complexes of groups. Many of these definitions
can be found in or are inspired from [BH99, III.$\mathcal{C}$ 1.6 p.526].

Let $\mathfrak{C}$ be a scwol and let $E^{\pm}(\mathfrak{C})$ be the set of
symbols $a^{+}$ and $a^{-}$, where $a\in\mathrm{Arr}(\mathfrak{C})$.

######  Definition 4.1.

The element $e\in E^{\pm}$ is an oriented edge of $\mathfrak{C}$. If $e=a^{+}$
then $i(e)=t(a)$, $t(e)=i(a)$, and if $e=a^{-}$ we have $i(e)=i(a)$ and
$t(e)=t(a)$.

######  Definition 4.2.

Let $v,w\in\mathrm{Obj}(\mathfrak{C})$. An edge path of $\mathfrak{C}$ joining
$v$ to $w$ is a sequence of elements in $E^{\pm}(\mathfrak{C})$,
$c=(a_{1}^{\epsilon},\cdots,a_{n}^{\epsilon_{n}})$ with
$a_{k}^{\epsilon_{k}}\in E^{\pm}(\mathfrak{C})$,
$a_{k}\in\mathrm{Arr}(\mathfrak{C})$, $\epsilon_{k}\in\big{\\{}-1,1\big{\\}}$,
such that for all $1<k<n$ we have
$i(a_{k}^{\epsilon_{k}})=t(a_{k-1}^{\epsilon_{k-1}})$ and $i(c)=v$, $t(c)=w$.

Given $\sigma\in\mathrm{Obj}(\mathfrak{C})$ the constant path over $\sigma$ is
realized by $\mathrm{id}_{\sigma}$.

######  Definition 4.3.

Let $c=(a_{1}^{\epsilon},\cdots,a_{n}^{\epsilon_{n}})$ be an edge path. We say
that backtracking occurs in $c$ if for any sequential edges $a_{j},a_{j+1}$ in
$c$ we have $a_{j}=a_{j+1}$ and $\epsilon_{j}=\epsilon^{-1}_{j+1}$ and reduce
$c$ by removing $a_{j}$ and $a_{j+1}$ from $c$ and forming a new edge path
from the remaining edges. If $c$ exhibits no backtracking then $c$ is said to
be fully reduced.

######  Definition 4.4.

Let $c=(a_{1}^{\epsilon},\cdots,a_{n}^{\epsilon_{n}})$ be an edge path in
$\mathfrak{C}$. We say that $c$ is a loop if $i(c)=t(c)$ and say that $c$ is a
circuit if $c$ is also embedded.

######  Definition 4.5.

A tree $T$ is a subset of objects
$\mathrm{Obj}(T)\subseteq\mathrm{Obj}(\mathfrak{C})$ and a subset of arrows
$\mathrm{Arr}(T)\subseteq\mathrm{Arr}(\mathfrak{C})$ so that for all
$a\in\mathrm{Arr}(T)$ we have $i(a),t(a)\in\mathrm{Obj}(T)$, $T$ is connected,
and $T$ has no circuits. We say that $T$ is a maximal tree if
$\mathrm{Obj}(T)=\mathrm{Obj}(\mathfrak{C})$.

######  Definition 4.6.

Let $T\subseteq\mathfrak{C}$ be a tree with $v,w\in\mathrm{Obj}(T)$ and let
$p_{T}(v,w)$ be the unique reduced edge path between $v$ and $w$ in $T$. Then
$p_{T}(v,w)$ is unique tree path between $v$ and $w$.

We next define and explain the functors that we use to prove Theorem A.

###  4.2 The Functors

Let $V$, $W$ be vector spaces and
$L\in\mathrm{Arr}(\mathbb{K}\mathrm{-Vect})$, $L:V\rightarrow W$ an
isomorphism of vector spaces. We construct the categories
$\widehat{\mathrm{GL}(V)}$, $\widehat{\mathrm{GL}(W)}$. Then $L$ induces the
following functor,

######  Definition 4.7.

The $\widehat{\textbf{L}}$-functor
$\widehat{L}:\widehat{\mathrm{GL}(V)}\rightarrow\widehat{\mathrm{GL}(W)}$ is,
defined by,

  * •

$\widehat{L}\big{(}\tau_{\mathrm{GL}(V)}\big{)}=\tau_{\mathrm{GL}(W)})$; and

  * •

$\widehat{L}\big{(}\alpha_{\mathrm{GL}(V)}(\rho)\big{)}=\alpha_{\mathrm{GL}(W)}\big{(}L\rho
L^{-1}\big{)}$.

The $\widehat{L}$-functor induces the following natural transformation,

######  Definition 4.8.

The L-transformation
$\eta^{L}_{\mathrm{GL}(V)}:\mathcal{Z}^{V}_{taut}\rightarrow\widehat{L}^{\ast}\mathcal{Z}^{W}_{taut}$
is the map $\eta^{L}_{\mathrm{GL}(V)}=L$.

It is a quick exercise to show $\widehat{L}$ is indeed a functor. Whats more,
it is not hard to show that $\eta^{L}_{\mathrm{GL}(V)}$ is a natural
isomorphism. This follows from $L$ being invertible since a natural
isomorphism is a natural transformation whose component maps are isomorphisms.

Let $\Lambda$ be a complex of groups and $\mathcal{C}\Lambda$ the B.H.
category. For $\sigma\in\mathrm{Obj}(\mathcal{C}\Lambda)$ let
$S_{\sigma}\subseteq\mathcal{C}\Lambda$ be the full subcategory over $\sigma$
with inclusion map $i_{\sigma}:S_{\sigma}\rightarrow\mathcal{C}\Lambda$.
Recall that $S_{\sigma}\cong\widehat{G_{\sigma}}$. Let $\mathcal{F}$ be a
sheaf over $\Lambda$. .

######  Definition 4.9.

The $\widehat{\textbf{I}_{\sigma}}$-functor
$\widehat{I_{\sigma}}:S_{\sigma}\rightarrow\widehat{\mathrm{GL}(\mathcal{F}(\sigma))}$
is defined by,

  * •

$\widehat{I_{\sigma}}(\sigma)=\tau_{\mathrm{GL}(\mathcal{F}(\sigma))}$; and

  * •

$\widehat{I_{\sigma}}((g,\mathbbm{1}_{\sigma}))=\alpha_{\mathrm{GL}(\mathcal{F}(\sigma))}(\mathcal{F}((g,\mathbbm{1}_{\sigma})))$.

Furthermore, let $\mathcal{Z}_{taut}^{\mathcal{F}(\sigma)}$ be the
tautological sheaf. It is not difficult to see that that
$i^{\ast}_{\sigma}\mathcal{F}$ and
$\widehat{I}_{\sigma}^{\ast}\mathcal{Z}_{taut}^{\mathcal{F}(\sigma)}$ are
natural isomorphisms and furthermore,

$i^{\ast}_{\sigma}\mathcal{F}=\widehat{I}_{\sigma}^{\ast}\mathcal{Z}_{taut}^{\mathcal{F}(\sigma)}.$

This is summarized in the following diagram,

$\textstyle{S_{\sigma}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i_{\sigma}}$$\scriptstyle{\widehat{I_{\sigma}}}$$\textstyle{\widehat{\mathrm{GL}(\mathcal{F}(\sigma))}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathcal{Z}_{taut}^{\mathcal{F}(\sigma)}}$$\textstyle{\mathcal{C}\Lambda\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathcal{F}}$$\textstyle{\mathbb{K}\mathrm{-Vect}}$

###  4.3 Sheaf Paths and a Morphism of Complexes of Groups

We utilize the functors from the previous subsection to define paths in the
sheaf $\mathcal{F}$ over edge paths in the scwol. We use sheaf paths to define
a functor $\widehat{\phi}$ which induces a morphism of complexes of groups.

The following is an example of an $\widehat{L}$-functor.

######  Definition 4.10.

Let $\Lambda$ be a complex of groups over a scwol $\mathfrak{C}$ with maximal
tree $T\subseteq\mathfrak{C}$ and
$p_{T}(v,w)=(a_{1}^{\epsilon_{1}},\cdots,a_{n}^{\epsilon_{n}})$ a unique tree
path in $T$. Let $\mathcal{F}$ be a sheaf over $\Lambda$ such that
$\mathcal{F}(v)=V$. A sheaf path towards $w$
$M_{w}:V\rightarrow\mathcal{F}(w)$ is,

$M_{w}=\prod_{j=0}^{n-1}\mathcal{F}\big{(}(\mathbf{1},a_{n-j})\big{)}^{\epsilon_{n-j}}$

Each sheaf path towards $w$, $M_{w}$ induces a natural isomorphism
$\eta_{\mathrm{GL}(V)}^{M_{w}}:\mathcal{Z}_{taut}^{V}\rightarrow\widehat{M}^{\ast}_{w}\mathcal{Z}_{taut}^{\mathcal{F}(w)}$.

We now define the local group functor.

######  Definition 4.11.

Let $\Lambda=(\mathfrak{C},G_{\sigma},\psi_{a},g_{a,b})$ be a complex of
groups, $\mathcal{F}$ a sheaf over $\Lambda$, $V$ a vector space,
$M_{w}:V\rightarrow\mathcal{F}(w)$ a sheaf path towards $w$. Let
$\sigma\in\mathrm{Obj}(\mathfrak{C})$. The local group functor
$\widehat{\phi_{\sigma}}:\mathcal{C}\Theta(G_{\sigma})\rightarrow\widehat{\mathrm{GL}(V)}$
is given by,

  * •

$\widehat{\phi_{\sigma}}(\tau_{G_{\sigma}})=\tau_{\mathrm{GL}(V)}$ for
$\tau_{G_{\sigma}}\in\mathrm{Obj}(\mathcal{C}\Theta(G_{\sigma}))$; and

  * •

$\widehat{\phi_{\sigma}}(\alpha_{G_{\sigma}}(g))=\alpha_{\mathrm{GL}(V)}\big{(}M^{-1}_{\sigma}\mathcal{F}(g,\mathbbm{1}_{\sigma})M_{\sigma}\big{)}$
for $\alpha_{G_{\sigma}}(g)\in\mathrm{Arr}(\mathcal{C}\Theta(G_{\sigma}))$.

By composing natural isomorphisms it is not hard to see,

######  Lemma 4.12.

If $\mathcal{F}$ satisfies the dev-properties then for all
$\sigma\in\mathrm{Obj}(\mathfrak{C})$, $\widehat{\phi_{\sigma}}$ is injective.

By focusing on group elements we get,

######  Lemma 4.13.

If $\mathcal{F}$ satisfies the dev-properties then for all
$\sigma\in\mathrm{Obj}(\mathfrak{C})$, $\widehat{\phi_{\sigma}}$ induces an
injective group homomorphism
$\phi_{\sigma}:G_{\sigma}\rightarrow\mathrm{GL}(V)$

We define the following element of the group $\mathrm{GL}(V)$,

######  Definition 4.14.

Let $a\in\mathrm{Arr}(\mathfrak{C})$, $g\in G_{t(a)}$,
$\mathcal{F}(g,a):\mathcal{F}(i(a))\rightarrow\mathcal{F}(t(a))$, and let
$M_{t(a)}:V\rightarrow\mathcal{F}(i(a))$ and
$M^{-1}_{t(a)}:\mathcal{F}(t(a))\rightarrow V$ be sheaf paths. We define
$\phi_{g}(a)\in\mathrm{GL}(V)$ as,

$\phi_{g}(a)=M^{-1}_{t(a)}\circ\mathcal{F}(g,a)\circ M_{i(a)}$

######  Definition 4.15.

Let $T\subseteq\mathfrak{C}$ be a maximal tree. We define the map
$\phi=(\phi_{\sigma},\phi_{\mathbf{1}}(a)):\Lambda\rightarrow\Theta\big{(}\mathrm{GL}(V)\big{)}$
by,

  * •

for each $\sigma\in\mathrm{Obj}(T)$, let
$\phi_{\sigma}:G_{\sigma}\rightarrow\mathrm{GL}(V)$ be the homomorphism
constructed in Definition 4.11; and

  * •

for $a\in\mathrm{Arr}(\mathfrak{C})$, let
$\phi_{\mathbf{1}}(a)\in\mathrm{GL}(V)$ be the construction from Definition
4.14.

We state the key lemma used to prove the other direction of Theorem A.

######  Lemma 4.16 (Key Lemma).

Let $\phi=(\phi_{\sigma},\phi_{\mathbf{1}}(a))$ be the map constructed in
Definition 4.15. Then $\phi$ is a morphism of complexes of groups. If
furthermore $\mathcal{F}$ satisfies the dev-properties then $\phi$ is
injective on local groups.

Before we prove the Key Lemma we state and prove two easy technical lemmas
concerning a constant rank sheaf whose linear morphisms are all invertible.
These results rely on the construction of the B.H category and on the fact
that functors preserve composition of arrows.

######  Lemma 4.17.

Let $\Lambda=(\mathfrak{C},G_{\sigma},\psi_{a},g_{a,b})$ be a complex of
groups, $C\Lambda$ the B.H. category and $\mathcal{F}$ a constant rank sheaf
over $\Lambda$ whose linear morphisms are all invertible. Then for
$(\mathbf{1},a),(g,\mathbbm{1}_{i(a)}),(\psi_{a}(g),\mathbbm{1}_{t(a)})\in\mathrm{Arr}(C\Lambda)$
we get the relation,

$\mathcal{F}((g,\mathbbm{1}_{i(a)}))=\mathcal{F}\big{(}(\mathbf{1},a)\big{)}^{-1}\circ\mathcal{F}\big{(}(\psi_{a}(g),\mathbbm{1}_{t(a)})\big{)}\circ\mathcal{F}\big{(}(\mathbf{1},a)\big{)}$

###### Proof.

The arrows fit into the commutative diagram,

$\textstyle{\tau_{i(a)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\mathbf{1},a)}$$\scriptstyle{(g,\mathbbm{1}_{\tau_{i(a)}})}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\tau_{t(a)}}$$\scriptstyle{(\psi_{a}(g),\mathbbm{1}_{\tau_{t(a)}})}$$\textstyle{\tau_{i(a)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{(\mathbf{1},a)}$$\textstyle{\tau_{t(a)}}$

The diagram yields the relation,

$(\mathbf{1},a)(g,\mathbbm{1}_{\tau_{i(a)}})=(\psi_{a}(g),\mathbbm{1}_{\tau_{t(a)}})(\mathbf{1},a)$

Functors preserve composition of arrows. Since all linear morphisms of
$\mathcal{F}$ are invertible and the rank of $\mathcal{F}$ is constant,

$\displaystyle\mathcal{F}\big{(}(\mathbf{1},a)\big{)}\mathcal{F}\big{(}(g,\mathbbm{1}_{\tau_{i(a)}})\big{)}$
$\displaystyle=\mathcal{F}\big{(}(\psi_{a}(g),\mathbbm{1}_{\tau_{t(a)}})\big{)}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}$
$\displaystyle\mathcal{F}\big{(}(g,\mathbbm{1}_{\tau_{i(a)}})\big{)}$
$\displaystyle=\mathcal{F}\big{(}(\mathbf{1},a)\big{)}^{-1}\mathcal{F}\big{(}(\psi_{a}(g),\mathbbm{1}_{\tau_{t(a)}})\big{)}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}$

∎

######  Lemma 4.18.

Let $\Lambda=(\mathfrak{C},G_{\sigma},\psi_{a},g_{a,b})$ be a complex of
groups, $C\Lambda$ the B.H. category and $\mathcal{F}$ a constant rank sheaf
over $\Lambda$ whose linear morphisms are all invertible. Then for composable
arrows $(\mathbf{1},a),(\mathbf{1},b)\in\mathrm{Arr}(C\Lambda)$ we get the
relation,

$\mathcal{F}\big{(}(\mathbf{1},a)\big{)}\circ\mathcal{F}\big{(}(\mathbf{1},b)\big{)}=\mathcal{F}(g_{a,b},\mathbbm{1}_{t(a)})\circ\mathcal{F}\big{(}(\mathbf{1},ab)\big{)}$

###### Proof.

We compose $(\mathbf{1},a)$ and $(\mathbf{1},b)$,

$\displaystyle(\mathbf{1},a)(\mathbf{1},b)$ $\displaystyle=(g_{a,b},ab)$
$\displaystyle=(g_{a,b},\mathbbm{1}_{t(a)})(\mathbf{1},ab)$

Functors preserve composition of arrows,

$\displaystyle\mathcal{F}\big{(}(\mathbf{1},a)\big{)}\mathcal{F}\big{(}(\mathbf{1},b)\big{)}$
$\displaystyle=\mathcal{F}\big{(}(g_{a,b},\mathbbm{1}_{t(a)})\big{)}\mathcal{F}\big{(}(\mathbf{1},ab)\big{)}$

∎

We now give the proof of Lemma 4.16 the Key Lemma.

###### Proof (Key Lemma).

We start by proving the two conditions from Definition 2.15

$\phi_{t(a)}\psi_{a}=\mathrm{Ad}\big{(}\phi_{\mathbf{1}}(a)\big{)}\phi_{i(a)}\hskip
7.22743pt\text{ and }\hskip
7.22743pt\phi_{t(a)}(g_{a,b})\phi(ab)=\phi(a)\phi(b)$

Suppose first $a\in T$. There are two cases,

Case 1: $\displaystyle\phi_{\mathbf{1}}(a)$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}M_{i(a)}$
$\displaystyle=M_{i(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}M_{i(a)}$
$\displaystyle=\mathbf{1}_{V}$ Case 2: $\displaystyle\phi_{\mathbf{1}}(a)$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}M_{i(a)}$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}^{-1}M_{t(a)}$
$\displaystyle=\mathbf{1}_{V}$

For $a\not\in T$, let $g\in G_{i(a)}$. The left hand side of the first
condition reads

$\displaystyle\phi_{t(a)}\big{(}\psi_{a}(g)\big{)}$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\psi_{a}(g),\mathbbm{1}_{t(a)})\big{)}M_{t(a)}$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}\mathcal{F}\big{(}(g,\mathbbm{1}_{i(a)})\big{)}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}^{-1}M_{t(a)}$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}M_{i(a)}M_{i(a)}^{-1}\mathcal{F}\big{(}(g,\mathbbm{1}_{i(a)})\big{)}M_{i(a)}M_{i(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}^{-1}M_{t(a)}$
$\displaystyle=\phi_{\mathbf{1}}(a)\phi_{i(a)}(g)\phi_{\mathbf{1}}(a)^{-1}$
$\displaystyle=\mathrm{Ad}\big{(}\phi_{\mathbf{1}}(a)\big{)}\phi_{i(a)}(g)$

The second line is justified by Lemma 4.17

For composable edges $a,b\not\in\mathrm{Arr}(T)$, $i(a)=t(b)$, we observe the
right hand side of the second equation,

$\displaystyle\phi_{\mathbf{1}}(a)\phi_{\mathbf{1}}(b)$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}M_{i(a)}M_{t(b)}^{-1}\mathcal{F}\big{(}(\mathbf{1},b)\big{)}M_{i(b)}$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},a)\big{)}\mathcal{F}\big{(}(\mathbf{1},b)\big{)}M_{i(b)}$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}(g_{a,b},\mathbbm{1}_{t(a)})\mathcal{F}\big{(}(\mathbf{1},ab)\big{)}M_{i(b)}$
$\displaystyle=M_{t(a)}^{-1}\mathcal{F}(g_{a,b},\mathbbm{1}_{t(a)})M_{t(a)}M_{t(a)}^{-1}\mathcal{F}\big{(}(\mathbf{1},ab)\big{)}M_{i(b)}$
$\displaystyle=\phi_{t(a)}(g_{a,b})\phi_{\mathbf{1}}(ab)$

The third line is justified by Lemma 4.18.

We make the further assumption that $\mathcal{F}$ satisfies the dev-
properties, by Lemma 4.13 each $\phi_{\sigma}$ is injective. Hence, $\phi$ is
injective on local groups. ∎

This gives the other direction of Theorem A

######  Theorem 4.19.

Let $\Lambda$ be a complex of groups and $\mathcal{F}$ a sheaf over $\Lambda$
that satisfies the dev-properties with witness $\mathrm{GL}(V)$. Then
$\Lambda$ is developable.

###### Proof.

By Lemma 4.16 the map $\phi=(\phi_{\sigma},\phi_{\mathbf{1}}(a))$ constructed
in Definition 4.15 is a morphism of complexes of groups and by the same lemma
is injective on local groups if $\mathcal{F}$ satisfies the dev-properties.
Thus, by Theorem 2.24, $\Lambda$ is developable. ∎

###  4.4 Theorem A

See A

###### Proof.

One direction is given by Theorem 4.19 while the other is the content of Lemma
3.7. ∎

## References

  * [Hae92] André Haefliger  “Extension of complexes of groups”  In _Annales de l’institut Fourier_ 42.1-2, 1992, pp. 275–311
  * [BH99] Martin R. Bridson and André Haefliger  “Metric Spaces of Non-Positive Curvature” 319, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]  Springer-Verlag, Berlin, 1999, pp. xxii+643  DOI: 10.1007/978-3-662-12494-9
  * [Fri15] Joel Friedman  “Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an appendix by Warren Dicks” With an appendix by Warren Dicks  In _Mem. Amer. Math. Soc._ 233.1100, 2015, pp. xii+106  DOI: 10.1090/memo/1100


# A Comparison Between Invariant and Equivariant Classical and Quantum Graph
Neural Networks

Roy T. Forestano
IFT, Department of Physics
University of Florida
Gainesville, FL 32611
<EMAIL_ADDRESS>
&Marçal Comajoan Cara
Department of Signal Theory and Communications
Polytechnic University of Catalonia
Barcelona, Barcelona 08034, Spain
<EMAIL_ADDRESS>
&Gopal Ramesh Dahale
Indian Inst. of Technology Bhilai
Kutelabhata, Khapri,
Chhattisgarh – 491001, India
<EMAIL_ADDRESS>
&Zhongtian Dong
Dep. Physics & Astronomy
University of Kansas
Lawrence, KS 66045
<EMAIL_ADDRESS>
&Sergei Gleyzer
Dep. Physics & Astronomy
University of Alabama
Tuscaloosa, AL 35487
<EMAIL_ADDRESS>
&Daniel Justice
Software Engineering Institute
Carnegie Mellon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>&Kyoungchul Kong
Dep. Physics & Astronomy
University of Kansas
Lawrence, KS 66045
<EMAIL_ADDRESS>
&Tom Magorsch
Physik-Department
Technische Univ. München
85748 Garching, Germany
<EMAIL_ADDRESS>
&Konstantin T. Matchev
IFT, Physics Department,
University of Florida
Gainesville, FL 32611
<EMAIL_ADDRESS>
&Katia Matcheva
IFT, Physics Department,
University of Florida
Gainesville, FL 32611
<EMAIL_ADDRESS>
&Eyup B. Unlu
IFT, Physics Department,
University of Florida
Gainesville, FL 32611
<EMAIL_ADDRESS>
###### Abstract

Machine learning algorithms are heavily relied on to understand the vast
amounts of data from high-energy particle collisions at the CERN Large Hadron
Collider (LHC). The data from such collision events can naturally be
represented with graph structures. Therefore, deep geometric methods, such as
graph neural networks (GNNs), have been leveraged for various data analysis
tasks in high-energy physics. One typical task is jet tagging, where jets are
viewed as point clouds with distinct features and edge connections between
their constituent particles. The increasing size and complexity of the LHC
particle datasets, as well as the computational models used for their
analysis, greatly motivate the development of alternative fast and efficient
computational paradigms such as quantum computation. In addition, to enhance
the validity and robustness of deep networks, one can leverage the fundamental
symmetries present in the data through the use of invariant inputs and
equivariant layers. In this paper, we perform a fair and comprehensive
comparison between classical graph neural networks (GNNs) and equivariant
graph neural networks (EGNNs) and their quantum counterparts: quantum graph
neural networks (QGNNs) and equivariant quantum graph neural networks (EQGNN).
The four architectures were benchmarked on a binary classification task to
classify the parton-level particle initiating the jet. Based on their AUC
scores, the quantum networks were shown to outperform the classical networks.
However, seeing the computational advantage of the quantum networks in
practice may have to wait for the further development of quantum technology
and its associated APIs.

##  1 Introduction

Through the measurement of byproducts of particle collisions, the Large Hadron
Collider (LHC) collects a substantial amount of information about the
fundamental particles and their interactions. The data produced from these
collisions can be analyzed using various supervised and unsupervised machine
learning methods [2, 32, 23, 24, 22]. Jet tagging is a key task in high energy
physics which seeks to identify the likely parton-level particle from which
the jet originated. By viewing individual jets as point clouds with distinct
features and edge connections between the constituent particles which make
them up, a graph neural network (GNN) has been considered as a well-suited
architecture for jet tagging [23, 32].

Classified as deep geometric networks, GNNs have the potential to draw
inferences about a graph structure, including the interactions among elements
in the graph [36, 41]. Graph neural networks are typically thought of as
generalizations of convolutional neural networks (CNNs), which are
predominantly used for image recognition, pattern recognition, and computer
vision [15, 16]. This can be attributed to the fact that, in an image, each
pixel is connected to its nearest neighboring pixels, whereas in a general
dataset, one would ideally like to construct an arbitrary graph structure
among the samples. Many instances in nature can be described well in terms of
graphs, including molecules, maps, social networks, and the brain. For
example, in molecules, the nodal data can be attributed to the atoms, the
edges can be characterized as the strength of the bond between atoms, and the
features embedded within each node can be the atom characteristics, such as
the reactivity.

Generally, graphically-structured problems involve unordered sets of elements
with learnable embedding of the input features. Useful information can be
extracted from such graph structured data by the embedding it within GNNs.
Many subsequent developments have been made to progress GNNs since their first
implementation in 2005, including graph convolutional, recurrent, message
passing, graph attention, and graph transformer, architectures [36, 32, 14,
37].

To enhance the validity and robustness of deep networks, invariant and
equivariant networks have been constructed to learn the symmetries embedded
within a dataset by preserving an oracle in the former and by enforcing weight
sharing across filter orientations in the latter [18, 7]. Utilizing analytical
invariant quantities characteristic of physical symmetry representations,
computational methods have successfully rediscovered fundamental Lie group
structures, such as the $SO(n)$, $SO(1,3)$, and $U(n)$ groups [10, 12, 11, 9].
Non-linear symmetry discovery methods have also been applied across
classification tasks in data domains [29]. The simplest and most useful
embedded symmetry transformations include translations, rotations, and
reflections, which have been the primary focus in invariant (IGNN) and
equivariant graph neural networks (EGNN) [19, 30].

The learned representations from the collection of these network components
can be used to understand unobservable causal factors, uncover fundamental
physical principles governing these processes, and possibly even discover
statistically significant hidden anomalies. However, with increasing amounts
of available data and the computational cost of these deep learning networks,
large computing resources will be required to efficiently run these machine
learning algorithms. The extension of classical networks, which relies on bit-
wise computation, to quantum networks, which relies on qubit-wise computation,
is already underway as a solution to this complexity problem. Many API’s,
including Xanadu’s Pennylane, Google’s Cirq, and IBM’s Qiskit, have been
developed to allow for the testing of quantum circuits and quantum machine
learning algorithms running on these quantum devices. In the quantum graph
structure, classical nodes can be mapped to quantum states, real valued
features to the complex valued characteristics of the states, edges to the
interactions between states, and edge attributes to the strength of the
interactions between the quantum states. Through a well-defined Hamiltonian
operator, the larger structure of a classical model can then be embedded into
the quantum model. This parameterized Hamiltonian determines the evolution of
the quantum system by acting on the quantum states within the graph. Following
several layers of application, a final state measurement of the quantum system
can then be made to reach a final prediction. The theory and application of
unsupervised and supervised learning tasks involving quantum graph neural
networks (QGNNs), quantum graph recurrent neural networks (QGRNNs), and
quantum graph convolutional neural networks (QGCNNs) have already been
developed [3, 38]. Improvements of these models to arbitrarily sized graphs
have been made with the implemenation of ego-graph based quantum graph neural
networks (egoQGNN) [1]. Quantum analogs of other advanced classical
architectures, including generative adversarial networks (GANs), transformers,
natural language processors (NLPs), and equivariant networks, have also been
proposed [3, 27, 5, 33, 4, 21, 26, 31].

With the rapid development of quantum deep learning, this work intends to
offer a fair and comprehensive comparison between GNNs and their quantum
counterparts. To classify whether a particle jet has originated from a quark
or a gluon, a binary classification task was carried out across four different
architectures. These architectures include a GNN, SE(2) EGNN, QGNN, and
permutation EQGNN. Each quantum model was fine tuned to have an analogous
structure to its classical form. In order to provide a fair comparison, all
models used similar hyperparameters, as well as a similar number of total
trainable parameters. The final results across each architecture using
identical training, validation, and testing sets were recorded. We find that
the QGNN and EQGNN outperform their classical analogs on the particular binary
classification task described above. Although these results seem promising for
the future of quantum computing, further development of quantum application
programming interfaces (APIs) is required to allow for more general
implementations of quantum architectures.

##  2 Data

Figure 1: Distributions of the jet transverse momenta $p_{T}$, total momenta
$p$, and energies $E$.

The jet-tagging binary classification task is illustrated with the high energy
physics (HEP) dataset Pythia8 Quark and Gluon Jets for Energy Flow [17], which
contains two million jets split equally into one million quark jets and one
million gluon jets. These jets resulted from LHC collisions with total center
of mass energy $\sqrt{s}=14$ TeV and were selected to have transverse momenta
$p_{T}^{jet}$ between $500$ to $550$ GeV and rapidities $|y^{jet}|<1.7$. The
jet kinematic distributions are shown in Fig. 1. For each jet $\alpha$, the
classification label is provided as either a quark with $y_{\alpha}=1$ or a
gluon with $y_{\alpha}=0$, and each particle $i$ within the jet is listed with
its transverse momentum $p^{(i)}_{T,\alpha}$, rapidity $y_{\alpha}^{(i)}$,
azimuthal angle $\phi_{\alpha}^{(i)}$, and PDG id $I_{\alpha}^{(i)}$.

Figure 2: A visualization of graphically structured data (left) and a sample
jet shown in the $(\phi,y)$ plane (right) with each particle color-coded by
its transverse momentum $p_{T,\alpha}^{(i)}$.

###  2.1 Graphically structured data

A graph $\mathcal{G}$ is typically defined as a set of nodes $\mathcal{V}$ and
edges $\mathcal{E}$, i.e. $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$. Each
node $v^{(i)}\in\mathcal{V}$ is connected to its neighboring nodes $v^{(j)}$
via edges $e^{(ij)}\in\mathcal{E}$. In our case, each jet $\alpha$ can be
considered as a graph $\mathcal{J}_{\alpha}$ composed of the jet’s constituent
particles as nodes $v_{\alpha}^{(i)}$ with node features $h_{\alpha}^{(i)}$
and edge connections $e_{\alpha}^{(ij)}$ between the nodes in
$\mathcal{J}_{\alpha}$ with edge features $a_{\alpha}^{(ij)}$. It should be
noted that the number of nodes within a graph can vary. This is especially
true for the case of particle jets, where the number of particles within each
jet can vary greatly. Each jet $\mathcal{J}_{\alpha}$ can be considered as a
collection of $m_{\alpha}$ particles with $l$ distinct features per particle.
An illustration of graphically structured data and an example jet in the
$(\phi,y)$ plane can be seen in Fig. 2.

###  2.2 Feature engineering

We use the Particle package [28] to find the particle masses
$m_{\alpha}^{(i)}$ from the respective particle id’s $I_{\alpha}^{(i)}$. From
the available kinematic information for each particle $i$, we construct new
physically meaningful kinematic variables [13], which will be used as
additional features in the analysis. In particular, we consider the transverse
mass $m_{T,\alpha}^{(i)}$, the energy $E_{\alpha}^{(i)}$, and the Cartesian
momentum components, $p_{x,\alpha}^{(i)}$, $p_{y,\alpha}^{(i)}$, and
$p_{z,\alpha}^{(i)}$, defined respectively as

$\displaystyle m_{T,\alpha}^{(i)}$
$\displaystyle=\sqrt{m_{\alpha}^{(i)2}+p_{T,\alpha}^{(i)2}},\qquad
E_{\alpha}^{(i)}=m_{T,\alpha}^{(i)}\text{cosh}(y_{\alpha}^{(i)}),$ (1a)
$\displaystyle p_{x,\alpha}^{(i)}$
$\displaystyle=p_{T,\alpha}^{(i)}\text{cos}(\phi_{\alpha}^{(i)}),\qquad
p_{y,\alpha}^{(i)}=p_{T,\alpha}^{(i)}\text{sin}(\phi_{\alpha}^{(i)}),\qquad
p_{z,\alpha}^{(i)}=m_{T,ij}\text{sinh}(y_{\alpha}^{(i)}).$ (1b)

The original kinematic information in the dataset is then combined with the
additional kinematic variables (1) into a feature set $h_{\alpha}^{(il)}$,
$l=0,1,2,\ldots,7$, as follows

$h_{\alpha}^{(il)}\equiv\left\\{p^{(i)}_{T,\alpha},y_{\alpha}^{(i)},\phi_{\alpha}^{(i)},m_{T,\alpha}^{(i)},E_{\alpha}^{(i)},p_{x,\alpha}^{(i)},p_{y,\alpha}^{(i)},p_{z,\alpha}^{(i)}\right\\}.$
(2)

These features were then max scaled by their maximum value across all jets
$\alpha$ and particles $i$, i.e. $h_{\alpha}^{(il)}\to
h_{\alpha}^{(il)}/max_{\alpha,i}(h_{\alpha}^{(il)})$.

Edge connections are formed via the Euclidean distance $\Delta
R=\sqrt{\Delta\phi^{2}+\Delta y^{2}}$ between one particle and its neighbor in
$(\phi,y)$ space. Therefore, the edge attribute matrix for each jet can be
expressed as

$\displaystyle a_{\alpha}^{(ij)}\equiv\Delta
R_{\alpha}^{(ij)}=\sqrt{\left(\phi_{\alpha}^{(i)}-\phi_{\alpha}^{(j)}\right)^{2}+\left(y_{\alpha}^{(i)}-y_{\alpha}^{(j)}\right)^{2}}.$
(3)

###  2.3 Training, Validation, and Testing Sets

We consider jets with at least $10$ particles. This leaves us with
$N=1,997,445$ jets, $997,805$ of which are quark jets. While the classical GNN
is more flexible in terms of its hidden features, the size of the quantum
state and the Hamiltonian scale as $2^{n}$, where $n$ is the number of qubits.
As we shall see, the number of qubits will be given by the number of nodes
$n_{\alpha}$ in the graph, i.e. the number of particles in the jet. Therefore,
jets with large particle multiplicity will require prohibitively complex
quantum networks. This is why, we limit ourselves to the case of
$n_{\alpha}=3$, and for each jet, only consider the three highest $p_{T}$
particles. In other words, each graph contains the set
$\mathbf{h}_{\alpha}=(\mathbf{h}_{\alpha}^{(1)},\mathbf{h}_{\alpha}^{(2)},\mathbf{h}_{\alpha}^{(3)})$
where each $\mathbf{h}_{\alpha}^{(i)}\in\mathbb{R}^{8}$ and
$\mathbf{h}_{\alpha}\in\mathbb{R}^{3\times 8}$. For training, we randomly
picked $N=12,500$ jets and used the first $10,000$ for training, the next
$1,250$ for validation, and the last $1,250$ for testing. These sets happened
to contain $4982$, $658$, and $583$ quark jets, respectively.

##  3 Models

The four different models described below, including a GNN, EGNN, QGNN, and
EQGNN, were constructed to perform graph classification. The binary
classification task was to determine whether a jet $\mathcal{J}_{\alpha}$
originated from a quark or a gluon.

###  3.1 Invariance and Equivariance

By making a network invariant or equivariant to particular symmetries within a
dataset, a more robust architecture can be developed. In order to introduce
invariance and equivariance, one must assume or learn a certain symmetry group
$G$ of transformations on the dataset. A function $\varphi:X\to Y$ is
equivariant with respect to a set of group transformations $T_{g}:X\to X$,
$g\in G$, acting on the input vector space $X$, if there exists a set of
transformations $S_{g}:Y\to Y$ which similarly transform the output space $Y$,
i.e.

$\displaystyle\varphi(T_{g}x)=S_{g}\varphi(x).$ (4)

A model is said to be invariant when for all $g\in G$, $S_{g}$ becomes the set
containing only the trivial mapping, i.e. $S_{g}=\\{\mathbb{I}_{G}\\}$, where
$\mathbb{I}_{G}\in G$ is the identity element of the group $G$ [18, 8].

Invariance has been shown to perform better as an input embedding, whereas
equivariance can be more easily incorporated into the model layers. For each
model, the invariant component corresponds to the translational and rotational
invariant embedding distance $\varphi\equiv\Delta R_{\alpha}^{(ij)}$, where in
this case $\varphi:\mathbb{R}^{2}\times\mathbb{R}^{2}\to\mathbb{R}$, which
makes up the edge attribute matrix $a_{\alpha}^{(ij)}$, as defined in Eq. 3.
This distance is used as opposed to solely incorporating the raw coordinates.
Equivariance has been accomplished through the use of simple nontrivial
functions along with higher order methods involving the use of spherical
harmonics to embed the equivariance within the network [25, 39]. Equivariance
takes different forms in each model presented here.

###  3.2 Graph neural network

Classical GNNs take in a collection of graphs $\\{\mathcal{G}_{\alpha}\\}$
each with nodes $v_{\alpha}^{(i)}\in\mathcal{V}_{\alpha}$ and edges
$e_{\alpha}^{(ij)}\in\mathcal{E}_{\alpha}$ where
$\mathcal{G}_{\alpha}=\\{\mathcal{V}_{\alpha},\mathcal{E}_{\alpha}\\}$. Each
node $v_{\alpha}^{(i)}$ has an associated feature vector $h_{\alpha}^{(i)}$,
and the entire graph has an associated edge attribute tensor
$a_{\alpha}^{(ijr)}$ describing $r$ different relationships between node
$v_{\alpha}^{(i)}$ and its neighbors $v_{\alpha}^{(j)}$. Here, we can define
$\mathcal{N}(i)$ as the set of neighbors of node $v_{\alpha}^{(i)}$ and take
$r=1$, as we will only consider one edge attribute, i.e.
$a_{\alpha}^{(ijr)}\to a_{\alpha}^{(ij)}$. The edge attributes are typically
formed from the features corresponding to each node and its neighbors.

Figure 3: Graph neural network (GNN, left) and equivariant graph neural
network (EGNN, right) schematic diagrams.

Figure 4: Quantum graph neural network (QGNN, left) and equivariant quantum
graph neural network (EQGNN, right) schematic diagrams.

In the layer structure of a GNN, multilayer perceptions (MLPs) are used to
update the node features and edge attributes before aggregating, or mean
pooling, the updated node features for each graph to make a final prediction.
To simplify notation, we will omit the graph index $\alpha$, lower the node
index $i$, and introduce a model layer index $l$. The first MLP is the edge
MLP $\phi_{e}$ which, at each layer $l$, collects the features
$\mathbf{h}_{i}^{l}$, its neighbors’ features $\mathbf{h}_{j}^{l}$, and the
edge attribute $a_{ij}$ corresponding to the pair. Once the new edge matrix
$m_{ij}$ is formed, we sum along the neighbor dimension $j$ to create a new
node feature $\mathbf{m}_{i}$. This extra feature is then added to the
original node features $\mathbf{h}_{i}$ before being input into a second node
updating MLP $\phi_{h}$ to form new node features $h_{i}^{l+1}$ [15, 14, 30].
Therefore, a GNN is defined as

$\displaystyle\mathbf{m}_{ij}$
$\displaystyle=\phi_{e}(\mathbf{h}_{i}^{l},\mathbf{h}_{j}^{l},a_{ij}),$ (5a)
$\displaystyle\mathbf{m}_{i}$
$\displaystyle=\sum_{j\in\mathcal{N}(i)}\mathbf{m}_{ij},$ (5b)
$\displaystyle\mathbf{h}_{i}^{l+1}$
$\displaystyle=\phi_{h}(\mathbf{h}_{i}^{l},\mathbf{m}_{i}).$ (5c)

Here, $h_{i}^{l}\in\mathbb{R}^{k}$ is the $k$-th dimensional embedding of node
$v_{i}$ at layer $l$ and $\mathbf{m}_{ij}$ is typically referred to as the
message passing function. Once the data is sent through the $P$ graph layers
of the GNN, the updated nodes $\mathbf{h}_{i}^{P}$ are aggregated via mean
pooling for each graph to form a set of final features
$\frac{1}{n_{\alpha}}\sum_{i=1}^{n_{\alpha}}\mathbf{h}_{i}^{P}$. These final
features are sent through a fully connected neural network (NN) to output the
predictions. Typically, a fixed number of hidden features $k=N_{h}$ is defined
for both the edge and node MLPs. The described GNN architecture is pictorially
shown in the left panel of Fig. 3.

###  3.3 SE(2) equivariant graph neural network

For the classical EGNN, the approach used here was informed by the successful
implementation of SE(3), or rotational, translational, and permutational,
equivariance on dynamical systems and the QM9 molecular dataset [30]. It
should be noted that GNNs are naturally permutation equivariant, in particular
invariant, when averaging over the final node feature outputs of the graph
layers [35]. An SE(2) EGNN takes the same form as a GNN, however, the
coordinates are equivariantly updated within each graph layer, i.e.
$\mathbf{x}_{i}\to\mathbf{x}_{i}^{l}$ where $\mathbf{x}_{i}=(\phi_{i},y_{i})$
in our case. The new form of the network becomes

$\displaystyle\mathbf{m}_{ij}$
$\displaystyle=\phi_{e}(\mathbf{h}_{i}^{l},\mathbf{h}_{j}^{l},a_{ij},|\mathbf{x}_{i}^{l}-\mathbf{x}_{j}^{l}|),$
(6a) $\displaystyle\mathbf{m}_{i}$
$\displaystyle=\sum_{j\in\mathcal{N}(i)}\mathbf{m}_{ij},$ (6b)
$\displaystyle\mathbf{x}_{i}^{l+1}$
$\displaystyle=\mathbf{x}_{i}^{l}+C\sum_{j\neq
i}(\mathbf{x}_{i}^{l}-\mathbf{x}_{j}^{l})\phi_{x}(\mathbf{m}_{ij}),$ (6c)
$\displaystyle\mathbf{h}_{i}^{l+1}$
$\displaystyle=\phi_{h}(\mathbf{h}_{i}^{l},\mathbf{m}_{i}).$ (6d)

Since the coordinates $\mathbf{x}_{i}^{l}$ of each node $v_{i}$ are
equivariantly evolving, we also introduce a second invariant embedding
$|\mathbf{x}_{i}^{l}-\mathbf{x}_{j}^{l}|$ based on the equivariant coordinates
into the edge MLP $\phi_{e}$. The coordinates $\mathbf{x}_{i}$ are updated by
adding the summed difference between coordinate $\mathbf{x}_{i}$ and its
neighbors $\mathbf{x}_{j}$ where the added term is enhanced by a factor of
$C$, which we take as $C=\frac{1}{\ln(2n_{\alpha})}$, and a coordinate MLP
$\phi_{x}$ which takes as input the message passing function
$\mathbf{m}_{ij}$. For a proof on the rotational and translational
equivariance of $\mathbf{x}_{i}^{l+1}$, see Appendix A. The described EGNN
architecture is pictorially shown in the right panel of Fig. 3.

###  3.4 Quantum graph neural network

For a QGNN, the input data, as a collection of graphs
$\\{\mathcal{G}_{\alpha}\\}$, is the same as described above. We fix the
number of qubits $n$ to be the number of nodes $n_{\alpha}$ in each graph. For
the quantum algorithm, we first form a normalized qubit product state from an
embedding MLP $\phi_{|\psi^{0}\rangle}$ which takes in the features
$\mathbf{h}_{i}$ of each node $v_{i}$ and reduces each of them to a qubit
state $|\phi_{|\psi^{0}\rangle}(\mathbf{h}_{i})\rangle\in\mathbb{C}^{2}$ [20].
The initial product state describing the system then becomes
$|\psi_{\alpha}^{0}\rangle=\bigotimes_{i=1}^{n}|\phi_{|\psi\rangle}(\mathbf{h}_{i})\rangle\in\mathbb{C}^{2^{n}}$,
which we normalize by
$\sqrt{\langle\psi_{\alpha}^{0}|\psi_{\alpha}^{0}\rangle}$.

Figure 5: $8\times 8$ matrix representations of the coupling and transverse
Hamiltonians defined in Eq. (7).

A fully parameterized Hamiltonian can then be constructed based on the
adjacency matrix $a_{ij}$ and node features $\mathbf{h}_{i}$ or trainable
interaction $\mathcal{W}_{ij}$ and feature $\mathcal{M}_{i}$ weights [38].
Here, for the coupling term of the Hamiltonian $H_{C}$, we utilize the edge
matrix $a_{ij}$ connected to two coupled Pauli-Z operators, $\sigma_{i}^{z}$
and $\sigma_{j}^{z}$, which act on the Hilbert spaces of qubits $i$ and $j$,
respectively. Since we embed the quantum state $|\psi^{0}\rangle$ based on the
node features $\mathbf{h}_{i}$, we omit the self-interaction term, which
utilizes the chosen features applied to the Pauli-Z operator,
$\sigma_{i}^{z}$, acting on the Hilbert space of qubit $i$. We also introduce
a transverse term $H_{T}$ to each node in the form of a Pauli-X operator,
$\sigma_{i}^{x}$ with a fixed or learnable constant coefficient
$\mathcal{Q}_{0}$, which we take to be $\mathcal{Q}_{0}=1$. Note that the
Hamiltonian $H$ contains $\mathcal{O}(2^{n}\times 2^{n})$ entries due to the
Kronecker products between Pauli operators. To best express the properties of
each graph, we take the Hamiltonian of the form

$\displaystyle H(a_{ij})$
$\displaystyle=\underbrace{\sum_{(i,j)\in\mathcal{E}}a_{ij}\left(\frac{\hat{\mathbb{I}}_{i}-\sigma_{i}^{z}}{2}-\frac{\hat{\mathbb{I}}_{j}-\sigma_{j}^{z}}{2}\right)^{2}}_{H_{C}}+\underbrace{\sum_{i\in\mathcal{V}}\sigma_{i}^{x}}_{H_{T}},$
(7)

where the $8\times 8$ matrix representations of $H_{C}$ and $H_{T}$ are shown
in Fig. 5. We generate the unitary form of the operator by complex
exponentiating the Hamiltonian with real learnable coefficients
$\gamma_{lq}\in\mathbb{R}^{P\times Q}$, which can be thought of as
infinitesimal parameters running over $Q=2$ Hamiltonian terms and $P$ layers
of the network. Therefore, the QGNN can be defined as

$\displaystyle U_{ij}$
$\displaystyle=\phi_{u}(a_{ij})=e^{-i\sum_{q=1}^{Q}\gamma_{lq}H_{q}(a_{ij})},$
(8a) $\displaystyle|\psi^{l+1}\rangle$
$\displaystyle=\phi_{|\psi\rangle}(|\psi^{l}\rangle,U_{ij})=U_{\theta}^{l}U_{ij}U_{\theta}^{l^{\dagger}}|\psi^{l}\rangle,$
(8b)

where
$U_{\theta}^{l}=(\mathbf{\theta}^{\prime}-i\mathbb{I})(\mathbf{\theta}^{\prime}+i\mathbb{I})^{-1}$
is a parameterized unitary Cayley transformation in which we force
$\mathbf{\theta}^{\prime}=\mathbf{\theta}+\mathbf{\theta}^{\dagger}$ to be
self-adjoint, i.e. $\mathbf{\theta}^{\prime}=\mathbf{\theta}^{\prime\dagger}$,
with $\mathbf{\theta}\in\mathbb{C}^{2^{n}\times 2^{n}}$ as the trainable
parameters. The QGNN evolves the quantum state $|\psi^{0}\rangle$ by applying
unitarily transformed ansatz Hamiltonians with $Q$ terms to the state over $P$
layers. The final product state $|\psi^{P}\rangle\in\mathbb{C}^{2^{n}}$ is
measured for output which is sent to a classical fully connected NN to make a
prediction. The analogy between the quantum unitary interaction function
$\phi_{u}$ and classical edge MLP $\phi_{e}$, as well as, between the quantum
unitary state update function $\phi_{|\psi\rangle}$ and classical node update
function $\phi_{h}$ should be clear. For a reduction of the coupling
Hamiltonian $H_{C}$ in Eq. (7), see Appendix B. The described QGNN
architecture is pictorially shown in the left panel of Fig. 4.

###  3.5 Permutation equivariant quantum graph neural Network

The EQGNN takes the same form as the QGNN, however, we aggregate the final
elements of the product state
$\frac{1}{2^{n}}\sum_{k=1}^{2^{n}}|\psi^{P}_{k}\rangle$ via mean pooling
before sending this complex value to a fully connected NN [26, 20, 34]. See
appendix C for a proof of the quantum product state permutation equivariance
over the sum of its elements. The resulting EQGNN architecture is shown in the
right panel of Fig. 4.

##  4 Results and Analysis

For each model, a range of total parameters were tested, however, the overall
comparison test was done using the largest optimal number of total parameters
for each network. A feed forward NN was used to reduce each network’s graph
layered output to a binary one followed by the softmax activation function to
obtain the logits in the classical case and the norm of the complex values to
obtain the logits in the quantum case. Each model trained over $20$ epochs
with the Adam optimizer consisting of a learning rate of $\eta=10^{-3}$ and a
cross-entropy loss function. The classical networks trained with a batch size
of $64$ and the quantum networks with a batch size of one due to the limited
capabilities of broadcasting unitary operators in the quantum APIs. The best
model weights were saved when the validation AUC, or area under the curve of
the true positive rate (TPR) as a function of the false positive rate (FPR),
was maximized after epoch $15$. The results of the training for the largest
optimal total number of parameters $|\Theta|\approx 5100$ can be seen in Fig.
6 with more details listed in Table 1.

Figure 6: (a) GNN, (b) EGNN, (c) QGNN, and (d) EQGNN training history plots. Table 1: Metric comparison between the classical and quantum graph models. Model | $|\Theta|$ | $N_{h}$ | P | Train ACC | Val ACC | Test AUC
---|---|---|---|---|---|---
GNN | 5122 | 10 | 5 | $74.25\%$ | $74.80\%$ | $\mathbf{63.36\%}$
EGNN | 5252 | 10 | 4 | $73.66\%$ | $74.08\%$ | $\mathbf{67.88\%}$
QGNN | 5156 | 8 | 6 | $74.00\%$ | $73.28\%$ | $\mathbf{61.43\%}$
EQGNN | 5140 | 8 | 6 | $74.42\%$ | $72.56\%$ | $\mathbf{75.17\%}$

Figure 7: Model ROC curves (left) and AUC scores as a function of parameters
(right).

Recall that for each model, we vary the number of hidden features $N_{h}$ in
the $P$ graph layers. Since we fix the number of nodes $n_{\alpha}=3$ per jet,
the hidden feature number $N_{h}=2^{3}=8$ becomes fixed in the quantum case,
and therefore, we also varied the parameters of the encoder
$\phi_{|\psi^{0}\rangle}$ and decoder NN in the quantum algorithms.

Based on the AUC scores, the EGNN outperformed both the classical and quantum
GNN, however, this algortihm was outperformed by the EQGNN with a $7.29\%$
increase in AUC representing the strength of the EQGNN. Although the GNN
outperformed the QGNN in the final parameter test by $1.93\%$, the QGNN
performed more consistently and outperformed the GNN in the mid parameter
range $|\Theta|\in(1500,4000)$. Through the variation of the number of
parameters, the AUC scores were recorded for each case where the number of
parameters taken for each point corresponds to
$|\Theta|\approx\\{500,1200,1600,2800,3500,5100\\}$ as shown in the right
panel of Fig. 7.

##  5 Conclusions

Through several computational experiments, the quantum GNNs seem to exhibit
enhanced classifier performance over their classical GNN counterparts based on
the best test AUC scores produced after the training of the models while
relying on a similar number of parameters, hyperparameters, and model
structures. These results seem promising for the quantum advantage over
classical models. Despite this result, the quantum algorithms take over $100$
times as long to train than the classical networks. This may be attributed to
the limited capabilities in the quantum APIs, where the inability to train
with broadcastable unitary operators forced the quantum models to take in a
batch size of one, or train on a single graph at a time.

The action of the equivariance in the EGNN and EQGNN could be further explored
and developed. This is especially true in the quantum case where more general
permutation and SU(2) equivariance have been explored [34, 20, 6, 40].
Expanding the flexibility of the networks to an arbitrary number of nodes per
graph should also offer increased robustness, however, this may continue to
pose challenges in the quantum case due to the current limited flexibility of
quantum software. A variety of different forms of the networks can also be
explored, such as introducing attention components and altering the structure
of the quantum graph layers to achieve enhanced performance of both classical
and quantum GNNs. In particular, one can further parameterize the quantum
graph layer structure to better align with the total number of parameters used
in the classical structures. These avenues will be explored in future work.

##  6 Software and Code

PyTorch and Pennylane were the primary APIs used in the formation and testing
of these algorithms. The code corresponding to this paper can be found at
$\href https://github.com/royforestano/2023_gsoc_ml4sci_qmlhep_gnn$.

## Acknowledgements

KM is supported in part by the U.S. Department of Energy award number DE-
SC0022148. KK is supported in part by US DOE DE-SC0024407. CD is supported in
part by College of Liberal Arts and Sciences Research Fund at the University
of Kansas.

## References

  * Ai et al. [2022] X. Ai, Z. Zhang, L. Sun, J. Yan, and E. R. Hancock.  Decompositional quantum graph neural network.  _CoRR_ , abs/2201.05158, 2022.
  * Andreassen et al. [2019] A. Andreassen, I. Feige, C. Frye, and M. D. Schwartz.  JUNIPR: a framework for unsupervised machine learning in particle physics.  _The European Physical Journal C_ , 79(2), feb 2019.  doi: 10.1140/epjc/s10052-019-6607-9.  URL https://doi.org/10.1140%2Fepjc%2Fs10052-019-6607-9.
  * Beer et al. [2023] K. Beer, M. Khosla, J. Köhler, T. J. Osborne, and T. Zhao.  Quantum machine learning of graph-structured data.  _Phys. Rev. A_ , 108:012410, Jul 2023.  doi: 10.1103/PhysRevA.108.012410.  URL https://link.aps.org/doi/10.1103/PhysRevA.108.012410.
  * Cherrat et al. [2023] E. A. Cherrat, I. Kerenidis, N. Mathur, J. Landman, M. C. Strahm, and Y. Y. Li.  Quantum vision transformers, 2023.  URL https://openreview.net/forum?id=p7xPXoKB0H.
  * Chu et al. [2023] C. Chu, G. Skipper, M. Swany, and F. Chen.  Iqgan: Robust quantum generative adversarial network for image synthesis on nisq devices.  In _ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 1–5, 2023.  doi: 10.1109/ICASSP49357.2023.10096772.
  * East et al. [2023] R. D. P. East, G. Alonso-Linaje, and C.-Y. Park.  All you need is spin: Su(2) equivariant variational quantum circuits based on spin networks, 2023.
  * Ecker et al. [2019] A. S. Ecker, F. H. Sinz, E. Froudarakis, P. G. Fahey, S. A. Cadena, E. Y. Walker, E. Cobos, J. Reimer, A. S. Tolias, and M. Bethge.  A rotation-equivariant convolutional neural network model of primary visual cortex.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=H1fU8iAqKX.
  * Esteves [2020] C. Esteves.  Theoretical aspects of group equivariant neural networks, 2020.
  * Forestano et al. [2023a] R. T. Forestano, K. T. Matchev, K. Matcheva, A. Roman, E. B. Unlu, and S. Verner.  Identifying the Group-Theoretic Structure of Machine-Learned Symmetries.  9 2023a.
  * Forestano et al. [2023b] R. T. Forestano, K. T. Matchev, K. Matcheva, A. Roman, E. B. Unlu, and S. Verner.  Deep learning symmetries and their Lie groups, algebras, and subalgebras from first principles.  _Mach. Learn. Sci. Tech._ , 4(2):025027, 2023b.  doi: 10.1088/2632-2153/acd989.
  * Forestano et al. [2023c] R. T. Forestano, K. T. Matchev, K. Matcheva, A. Roman, E. B. Unlu, and S. Verner.  Accelerated Discovery of Machine-Learned Symmetries: Deriving the Exceptional Lie Groups G2, F4 and E6.  7 2023c.
  * Forestano et al. [2023d] R. T. Forestano, K. T. Matchev, K. Matcheva, A. Roman, E. B. Unlu, and S. Verner.  Discovering Sparse Representations of Lie Groups with Machine Learning.  _Physics Letters B_ , 844, 9 2023d.  doi: 10.1016/j.physletb.2023.138086.
  * Franceschini et al. [2022] R. Franceschini, D. Kim, K. Kong, K. T. Matchev, M. Park, and P. Shyamsundar.  Kinematic Variables and Feature Engineering for Particle Phenomenology.  6 2022.
  * Gilmer et al. [2017] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl.  Neural message passing for quantum chemistry.  In D. Precup and Y. W. Teh, editors, _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 1263–1272. PMLR, 06–11 Aug 2017.  URL https://proceedings.mlr.press/v70/gilmer17a.html.
  * Kipf and Welling [2016] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Kipf and Welling [2017] T. N. Kipf and M. Welling.  Semi-Supervised Classification with Graph Convolutional Networks.  In _Proceedings of the 5th International Conference on Learning Representations_ , ICLR ’17, 2017.  URL https://openreview.net/forum?id=SJU4ayYgl.
  * Komiske et al. [2019] P. T. Komiske, E. M. Metodiev, and J. Thaler.  Energy flow networks: deep sets for particle jets.  _Journal of High Energy Physics_ , 2019(1), jan 2019.  doi: 10.1007/jhep01(2019)121.  URL https://doi.org/10.1007%2Fjhep01%282019%29121.
  * Lim and Nelson [2022] L. Lim and B. J. Nelson.  What is an equivariant neural network?  _CoRR_ , abs/2205.07362, 2022.  doi: 10.48550/arXiv.2205.07362.  URL https://doi.org/10.48550/arXiv.2205.07362.
  * Maron et al. [2019] H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman.  Invariant and equivariant graph networks.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=Syx72jC9tm.
  * Mernyei et al. [2022] P. Mernyei, K. Meichanetzidis, and İsmail İlkan Ceylan.  Equivariant quantum graph circuits, 2022.
  * Meyer et al. [2023] J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, and J. Eisert.  Exploiting symmetry in variational quantum machine learning.  _PRX Quantum_ , 4(1), mar 2023.  doi: 10.1103/prxquantum.4.010328.  URL https://doi.org/10.1103%2Fprxquantum.4.010328.
  * Mikuni and Canelli [2020] V. Mikuni and F. Canelli.  Abcnet: an attention-based method for particle tagging.  _The European Physical Journal Plus_ , 135(6):463, 2020.  doi: 10.1140/epjp/s13360-020-00497-3.  URL https://doi.org/10.1140/epjp/s13360-020-00497-3.
  * Mikuni and Canelli [2021] V. Mikuni and F. Canelli.  Point cloud transformers applied to collider physics.  _Machine Learning: Science and Technology_ , 2(3):035027, jul 2021.  doi: 10.1088/2632-2153/ac07f6.  URL https://doi.org/10.1088%2F2632-2153%2Fac07f6.
  * Mokhtar et al. [2022] F. Mokhtar, R. Kansal, and J. Duarte.  Do graph neural networks learn traditional jet substructure?  In _36th Conference on Neural Information Processing Systems_ , 11 2022.
  * Murnane et al. [2023] D. Murnane, S. Thais, and A. Thete.  Equivariant graph neural networks for charged particle tracking, 2023\.
  * Nguyen et al. [2022] Q. T. Nguyen, L. Schatzki, P. Braccia, M. Ragone, P. J. Coles, F. Sauvage, M. Larocca, and M. Cerezo.  Theory for equivariant quantum neural networks.  _ArXiv_ , abs/2210.08566, 2022.  URL https://api.semanticscholar.org/CorpusID:252917789.
  * Niu et al. [2022] M. Y. Niu, A. Zlokapa, M. Broughton, S. Boixo, M. Mohseni, V. Smelyanskyi, and H. Neven.  Entangling Quantum Generative Adversarial Networks.  _Phys. Rev. Lett._ , 128(22):220505, 2022.  doi: 10.1103/PhysRevLett.128.220505.
  * Rodrigues and Schreiner [2023] E. Rodrigues and H. Schreiner.  scikit-hep/particle: Version 0.23.0, July 2023.  URL https://doi.org/10.5281/zenodo.8112280.
  * Roman et al. [2023] A. Roman, R. T. Forestano, K. T. Matchev, K. Matcheva, and E. B. Unlu.  Oracle-preserving latent flows.  _Symmetry_ , 15(7), 2023.  ISSN 2073-8994.  doi: 10.3390/sym15071352.  URL https://www.mdpi.com/2073-8994/15/7/1352.
  * Satorras et al. [2021] V. G. Satorras, E. Hoogeboom, and M. Welling.  E(n) equivariant graph neural networks.  _ArXiv_ , abs/2102.09844, 2021.  URL https://api.semanticscholar.org/CorpusID:231979049.
  * Schatzki et al. [2022] L. Schatzki, M. Larocca, Q. T. Nguyen, F. Sauvage, and M. Cerezo.  Theoretical guarantees for permutation-equivariant quantum neural networks, 2022.
  * Shlomi et al. [2020] J. Shlomi, P. Battaglia, and J.-R. Vlimant.  Graph neural networks in particle physics.  _Machine Learning: Science and Technology_ , 2(2):021001, Dec 2020.  doi: 10.1088/2632-2153/abbf9a.  URL https://dx.doi.org/10.1088/2632-2153/abbf9a.
  * Sipio et al. [2021] R. D. Sipio, J.-H. Huang, S. Y.-C. Chen, S. Mangini, and M. Worring.  The dawn of quantum natural language processing.  _ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 8612–8616, 2021.  URL https://api.semanticscholar.org/CorpusID:238744248.
  * Skolik et al. [2023] A. Skolik, M. Cattelan, S. Yarkoni, T. Bäck, and V. Dunjko.  Equivariant quantum circuits for learning on weighted graphs.  _npj Quantum Information_ , 9(1):47, 2023.  doi: 10.1038/s41534-023-00710-y.  URL https://doi.org/10.1038/s41534-023-00710-y.
  * Thiede et al. [2020] E. H. Thiede, T. S. Hy, and R. Kondor.  The general theory of permutation equivarant neural networks and higher order graph variational encoders, 2020.
  * Veličković [2023] P. Veličković.  Everything is connected: Graph neural networks.  _Current Opinion in Structural Biology_ , 79:102538, 2023\.  ISSN 0959-440X.  doi: https://doi.org/10.1016/j.sbi.2023.102538.  URL https://www.sciencedirect.com/science/article/pii/S0959440X2300012X.
  * Veličković et al. [2018] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio.  Graph attention networks.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=rJXMpikCZ.
  * Verdon et al. [2019] G. Verdon, T. Mccourt, E. Luzhnica, V. Singh, S. Leichenauer, and J. D. Hidary.  Quantum graph neural networks.  _ArXiv_ , abs/1909.12264, 2019.  URL https://api.semanticscholar.org/CorpusID:202889158.
  * Worrall et al. [2017] D. E. Worrall, S. J. Garbin, D. Turmukhambetov, and G. J. Brostow.  Harmonic networks: Deep translation and rotation equivariance.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 7168–7177, Los Alamitos, CA, USA, jul 2017. IEEE Computer Society.  doi: 10.1109/CVPR.2017.758.  URL https://doi.ieeecomputersociety.org/10.1109/CVPR.2017.758.
  * Zheng et al. [2023] H. Zheng, C. Kang, G. S. Ravi, H. Wang, K. Setia, F. T. Chong, and J. Liu.  Sncqa: A hardware-efficient equivariant quantum convolutional circuit architecture, 2023.
  * Zhou et al. [2020] J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun.  Graph neural networks: A review of methods and applications.  _AI Open_ , 1:57–81, 2020.  ISSN 2666-6510.  doi: https://doi.org/10.1016/j.aiopen.2021.01.001.  URL https://www.sciencedirect.com/science/article/pii/S2666651021000012.

##  Appendix A Equivariant coordinate update function

Let $T_{g}:X\to X$ be the set of translational and rotational group
transformations with elements $g\in T_{g}\subset G$ which act on the vector
space $X$. The function $\varphi:X\to X$ defined by

$\displaystyle\varphi(x)=x_{i}+C\sum_{j\neq i}(x_{i}-x_{j})$ (9)

is equivariant with respect to $T_{g}$.

###### Proof.

Let a general transformation $g\in T_{g}$ act on $X$ by $gX=RX+T$, where $R\in
T_{g}$ denotes a general rotation and $T\in T_{g}$ a general translation.
Then, under the transformation $g$ on $X$ of the function $\varphi$ defined
above, we have

$\displaystyle\varphi(gx)$ $\displaystyle=(gx_{i})+C\sum_{j\neq
i}(gx_{i}-gx_{j})$ $\displaystyle=(Qx_{i}+T)+C\sum_{j\neq
i}(Qx_{i}+T-Qx_{j}-T)$ $\displaystyle=(Qx_{i}+T)+C\sum_{j\neq
i}(Qx_{i}-Qx_{j})$ $\displaystyle=Qx_{i}+C\sum_{j\neq i}Q(x_{i}-x_{j})+T$
$\displaystyle=Q[x_{i}+C\sum_{j\neq i}(x_{i}-x_{j})]+T$
$\displaystyle=g\varphi(x),$

where $\varphi(gx)=g\varphi(x)$ shows $\varphi$ transforms equivariantly under
transformations $g\in T_{g}$ acting on $X$. ∎

##  Appendix B Coupling Hamiltonian simplification

The reduction of the coupling Hamiltonian becomes

$\displaystyle\hat{H}_{C}$
$\displaystyle=\frac{1}{2}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\left(\frac{\hat{I}_{j}-\sigma_{j}^{z}}{2}\right)-\left(\frac{\hat{I}_{k}-\sigma_{k}^{z}}{2}\right)\right]^{2}$
$\displaystyle=\frac{1}{8}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\left(\hat{I}_{j}-\sigma_{j}^{z}\right)-\left(\hat{I}_{k}-\sigma_{k}^{z}\right)\right]^{2}$
$\displaystyle=\frac{1}{8}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\left(\hat{I}_{j}-\sigma_{j}^{z}\right)^{2}-\left(\hat{I}_{j}-\sigma_{j}^{z}\right)\left(\hat{I}_{k}-\sigma_{k}^{z}\right)-\left(\hat{I}_{k}-\sigma_{k}^{z}\right)\left(\hat{I}_{j}-\sigma_{j}^{z}\right)+\left(\hat{I}_{k}-\sigma_{k}^{z}\right)^{2}\right]$
$\displaystyle=\frac{1}{8}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\Big{[}\hat{I}_{j}\hat{I}_{j}-\hat{I}_{j}\sigma_{j}^{z}-\sigma_{j}^{z}\hat{I}_{j}+\sigma_{j}^{z}\sigma_{j}^{z}-\hat{I}_{j}\hat{I}_{k}+\hat{I}_{j}\sigma_{k}^{z}+\sigma_{j}^{z}\hat{I}_{k}-\sigma_{j}^{z}\sigma_{k}^{z}-\hat{I}_{k}\hat{I}_{j}+\hat{I}_{k}\sigma_{j}^{z}+\sigma_{k}^{z}\hat{I}_{j}$
$\displaystyle\qquad\qquad\qquad-\sigma_{k}^{z}\sigma_{j}^{z}+\hat{I}_{k}\hat{I}_{k}-\hat{I}_{k}\sigma_{k}^{z}-\sigma_{k}^{z}\hat{I}_{k}+\sigma_{k}^{z}\sigma_{k}^{z}\Big{]}$
$\displaystyle=\frac{1}{8}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\hat{I}_{j}\hat{I}_{j}-2\hat{I}_{j}\sigma_{j}^{z}+\sigma_{j}^{z}\sigma_{j}^{z}-2\hat{I}_{j}\hat{I}_{k}+2\hat{I}_{j}\sigma_{k}^{z}+2\sigma_{j}^{z}\hat{I}_{k}-2\sigma_{j}^{z}\sigma_{k}^{z}+\hat{I}_{k}\hat{I}_{k}-2\hat{I}_{k}\sigma_{k}^{z}+\sigma_{k}^{z}\sigma_{k}^{z}\right]$
$\displaystyle=\frac{1}{8}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\hat{I}_{j}-2\sigma_{j}^{z}+{\sigma_{j}^{z}}^{2}-2\hat{I}_{j}\hat{I}_{k}+2\hat{I}_{j}\sigma_{k}^{z}+2\sigma_{j}^{z}\hat{I}_{k}-2\sigma_{j}^{z}\sigma_{k}^{z}+\hat{I}_{k}-2\sigma_{k}^{z}+{\sigma_{k}^{z}}^{2}\right]$
$\displaystyle=\frac{1}{8}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[2\hat{I}_{j}-2\sigma_{j}^{z}-2\hat{I}_{j}\hat{I}_{k}+2\hat{I}_{j}\sigma_{k}^{z}+2\sigma_{j}^{z}\hat{I}_{k}-2\sigma_{j}^{z}\sigma_{k}^{z}+2\hat{I}_{k}-2\sigma_{k}^{z}\right]$
$\displaystyle=\frac{1}{4}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\hat{I}_{j}-\sigma_{j}^{z}-\hat{I}_{j}\hat{I}_{k}+\hat{I}_{j}\sigma_{k}^{z}+\sigma_{j}^{z}\hat{I}_{k}-\sigma_{j}^{z}\sigma_{k}^{z}+\hat{I}_{k}-\sigma_{k}^{z}\right],$

and multiplying on the left by $\hat{I}_{j}$ and on the right by $\hat{I}_{k}$
admits

$\displaystyle\implies\hat{H}_{C}$
$\displaystyle=\frac{1}{4}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\hat{I}_{j}\hat{I}_{k}-\sigma_{j}^{z}\hat{I}_{k}+\hat{I}_{j}\sigma_{k}^{z}+\sigma_{j}^{z}\hat{I}_{k}-\sigma_{j}^{z}\sigma_{k}^{z}-\hat{I}_{j}\sigma_{k}^{z}\right]$
$\displaystyle=\frac{1}{4}\sum_{(j,k)\in\mathcal{E}}\Lambda_{jk}\left[\hat{I}_{j}\hat{I}_{k}-\sigma_{j}^{z}\sigma_{k}^{z}\right].$
(10)

##  Appendix C Quantum product state permutation equivariance

For $V$ a commutable vector space, the product state
$\bigotimes_{i=1}^{m}\mathbf{v}_{i}:V^{n}\times\cdots\times V^{n}\to
V^{n^{m}}$ is permutation equivariant with respect to the sum of its entries.
We prove the $n=2$ case for all $m\in\mathbb{Z}_{>0}$.

###### Proof.

(By Induction) Assume we have $n=1$ final qubit state,

$\displaystyle|\psi_{1}\rangle=\bigotimes_{i=1}^{1}\begin{pmatrix}v_{1}^{1}\\\
v_{1}^{2}\end{pmatrix}=\begin{pmatrix}v_{1}^{1}\\\ v_{1}^{2}\end{pmatrix},$

the sum of the product state elements will be trivially equivariant with
respect to similar graphs. If we have $n=2$ final qubit states, the product
state is

$\displaystyle|\psi_{i}\rangle=\bigotimes_{i=\\{1,2\\}}\begin{pmatrix}v_{i}^{1}\\\
v_{i}^{2}\end{pmatrix}=\begin{pmatrix}v_{1}^{1}\\\
v_{1}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{2}^{1}\\\
v_{2}^{2}\end{pmatrix}=\begin{pmatrix}v_{1}^{1}v_{2}^{1}\\\
v_{1}^{2}v_{2}^{1}\\\ v_{1}^{1}v_{2}^{2}\\\ v_{1}^{2}v_{2}^{2}\end{pmatrix},$

where the sum of elements becomes

$\displaystyle
v_{1}^{1}v_{2}^{1}+v_{1}^{2}v_{2}^{1}+v_{1}^{1}v_{2}^{2}+v_{1}^{2}v_{2}^{2}$
$\displaystyle=v_{2}^{1}v_{1}^{1}+v_{2}^{1}v_{1}^{2}+v_{2}^{2}v_{1}^{1}+v_{2}^{2}v_{1}^{2}$
$\displaystyle=v_{2}^{1}v_{1}^{1}+v_{2}^{2}v_{1}^{1}+v_{2}^{1}v_{1}^{2}+v_{2}^{2}v_{1}^{2},$

which is equivalent to the sum of the elements

$\displaystyle\begin{pmatrix}v_{2}^{1}v_{1}^{1}\\\ v_{2}^{2}v_{1}^{1}\\\
v_{2}^{1}v_{1}^{2}\\\
v_{2}^{2}v_{1}^{2}\end{pmatrix}=\begin{pmatrix}v_{2}^{1}\\\
v_{2}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{1}^{1}\\\
v_{1}^{2}\end{pmatrix}=\bigotimes_{i=\\{2,1\\}}\begin{pmatrix}v_{i}^{1}\\\
v_{i}^{2}\end{pmatrix}$

for commutative spaces where $v_{i}^{j}\in\mathbb{C}$ and
$\\{1,2\\},\\{2,1\\}$ should be regarded as ordered sets, which again shows
the sum of the state elements remaining unchanged when the qubit states switch
positions in the product. We will now assume the statement is true for $n=N$
final qubit states and proceed to show the $N+1$ case is true. The quantum
product state over $N$ elements becomes

$\displaystyle\bigotimes_{i=1}^{N}|\psi_{i}\rangle=\bigotimes_{i}\begin{pmatrix}v_{i}^{1}\\\
v_{i}^{2}\end{pmatrix}$ $\displaystyle=\begin{pmatrix}v_{1}^{1}\\\
v_{1}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{2}^{1}\\\
v_{2}^{2}\end{pmatrix}\otimes\cdots\otimes\begin{pmatrix}v_{N}^{1}\\\
v_{N}^{2}\end{pmatrix},$ (11)

which we assume to be permutation equivariant over the sum of its elements. We
can rewrite the form of this state as

$\displaystyle\bigotimes_{i=1}^{N}|\psi_{i}\rangle=\begin{pmatrix}A_{1}\\\
A_{2}\\\ \vdots\\\ A_{2^{N}}\end{pmatrix}=A_{j},$ (12)

where $A_{j}$ define the $2^{N}$ terms in the final product state. Replacing
the $i+1$-th entry of the Kronecker product above with a new $N+1$-th state,
we have

$\displaystyle\bigotimes_{i=1}^{N+1}|\psi_{i}\rangle=\bigotimes_{i}\begin{pmatrix}v_{i}^{1}\\\
v_{i}^{2}\end{pmatrix}$ $\displaystyle=\underbrace{\begin{pmatrix}v_{1}^{1}\\\
v_{1}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{2}^{1}\\\
v_{2}^{2}\end{pmatrix}\otimes\cdots\otimes\begin{pmatrix}v_{i}^{1}\\\
v_{i}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{N+1}^{1}\\\
v_{N+1}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{i+1}^{1}\\\
v_{i+1}^{2}\end{pmatrix}\otimes\cdots\otimes\begin{pmatrix}v_{N}^{1}\\\
v_{N}^{2}\end{pmatrix}}_{N+1\text{ terms}}.$

When this occurs, this new state consisting of $2^{N+1}$ elements with the
$N+1$ state in the $i+1$-th entry of the product can be written in terms of
the old state with groupings of the new elements in $2^{N+1-i}$ batches of
$2^{i}$ elements, i.e.

$\displaystyle\bigotimes_{i=1}^{N+1}|\psi_{i}\rangle$
$\displaystyle=\begin{pmatrix}B_{1}=A_{1}v_{N+1}^{1}\\\
B_{2}=A_{2}v_{N+1}^{1}\\\ \vdots\\\ B_{2^{i}}=A_{2^{i}}v_{N+1}^{1}\\\
B_{2^{i}+1}=A_{1}v_{N+1}^{2}\\\ \vdots\\\ B_{2^{i+1}}=A_{2^{i}}v_{N+1}^{2}\\\
\vdots\\\ B_{2^{N+1}-2^{i+1}+1}=A_{2^{N}-2^{i}+1}v_{N+1}^{1}\\\ \vdots\\\
B_{2^{N+1}-2^{i}}=A_{2^{N}}v_{N+1}^{1}\\\
B_{2^{N+1}-2^{i}+1}=A_{2^{N}-2^{i}+1}v_{N+1}^{2}\\\ \vdots\\\
B_{2^{N+1}}=A_{2^{N}}v_{N+1}^{2}\\\ \end{pmatrix},$ (13)

which when summed becomes

$\displaystyle\sum_{k=1}^{2^{N+1}}B_{k}$
$\displaystyle=\sum_{j=1}^{2^{N}}A_{j}v_{N+1}^{1}+\sum_{j=1}^{2^{N}}A_{j}v_{N+1}^{2}$
$\displaystyle=(v_{N+1}^{1}+v_{N+1}^{2})\sum_{j=1}^{2^{N}}A_{j}.$

However, the $i+1$-th entry is arbitrary, and due to the summation permutation
equivariance of the initial state $\bigotimes_{i=1}^{N}|\psi_{i}\rangle$, the
sum $\sum_{j=1}^{2^{N}}A_{j}$ is equivariant, in fact invariant, under all
reorderings of the elements $|\psi_{i}\rangle$ in the product
$\bigotimes_{i=1}^{N}|\psi_{i}\rangle$. Therefore, we conclude
$\bigotimes_{i=1}^{N+1}|\psi_{i}\rangle$ is permutation equivariant with
respect to the sum of its elements. ∎

To show a simple illustration of why 13 is true, let us take two initial
states and see what happens when we insert a new state between them, i.e. in
the $2$nd entry in the product. This should lead to $2^{2+1-1}=2^{2}=4$
groupings of $2^{1}=2$ elements. To begin, we have

$\displaystyle\begin{pmatrix}v_{1}^{1}\\\
v_{1}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{2}^{1}\\\
v_{2}^{2}\end{pmatrix}=\begin{pmatrix}v_{1}^{1}v_{2}^{1}\\\
v_{1}^{2}v_{2}^{1}\\\ v_{1}^{1}v_{2}^{2}\\\
v_{1}^{2}v_{2}^{2}\end{pmatrix}=\begin{pmatrix}A_{1}\\\ A_{2}\\\ A_{3}\\\
A_{4}\end{pmatrix},$

and when we insert the new third state in the $1$-th entry of the product
above, we have

$\displaystyle\begin{pmatrix}v_{1}^{1}\\\
v_{1}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{3}^{1}\\\
v_{3}^{2}\end{pmatrix}\otimes\begin{pmatrix}v_{2}^{1}\\\
v_{2}^{2}\end{pmatrix}=\begin{pmatrix}v_{1}^{1}v_{3}^{1}v_{2}^{1}\\\
v_{1}^{2}v_{3}^{1}v_{2}^{1}\\\ v_{1}^{1}v_{3}^{2}v_{2}^{1}\\\
v_{1}^{2}v_{3}^{2}v_{2}^{1}\\\ v_{1}^{1}v_{3}^{1}v_{2}^{2}\\\
v_{1}^{2}v_{3}^{1}v_{2}^{2}\\\ v_{1}^{1}v_{3}^{2}v_{2}^{2}\\\
v_{1}^{2}v_{3}^{2}v_{2}^{2}\end{pmatrix}=\begin{pmatrix}A_{1}v_{3}^{1}\\\
A_{2}v_{3}^{1}\\\ A_{1}v_{3}^{2}\\\ A_{2}v_{3}^{2}\\\ A_{3}v_{3}^{1}\\\
A_{4}v_{3}^{1}\\\ A_{3}v_{3}^{2}\\\ A_{4}v_{3}^{2}\end{pmatrix},$

which sums to

$\displaystyle(A_{1}+A_{2}+A_{3}+A_{4})v_{3}^{1}+(A_{1}+A_{2}+A_{3}+A_{4})v_{3}^{2}=(v_{3}^{1}+v_{3}^{2})\sum_{i=1}^{2^{N}=2^{2}=4}A_{j}.$