Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy,
<EMAIL_ADDRESS>Hausdorff Center for Mathematics, University of
Bonn, Germany and
<EMAIL_ADDRESS>work was done while this author was working at Université de Lorraine, CNRS,
Inria, LORIA, F-54000 Nancy, France Department of Mathematics, University of
Luxembourg and<EMAIL_ADDRESS>Université de
Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France and
<EMAIL_ADDRESS>This work
was partially supported by grant ANR-17-CE40-0033 of the French National
Research Agency ANR (project SoS) and INTER/ANR/16/11554412/SoS of the
Luxembourg National Research fund FNR https://SoS.loria.fr/.[300]Mathematics
of computing Geometric topology [500]Theory of computation Computational
geometry Erin Chambers and Joachim Gudmundsson 2 39th Symposium on
Computational Geometry SoCG 2023 SoCG 2023 June 12-15, 2023 Dallas, USA YY 89

# Computing a Dirichlet domain for a hyperbolic surface

Vincent Despré  Benedikt Kolbe  Hugo Parlier  Monique Teillaud

###### Abstract

The goal of this paper is to exhibit and analyze an algorithm that takes a
given closed orientable hyperbolic surface and outputs an explicit Dirichlet
domain. The input is a fundamental polygon with side pairings. While grounded
in topological considerations, the algorithm makes key use of the geometry of
the surface. We introduce data structures that reflect this interplay between
geometry and topology and show that the algorithm finishes in polynomial time,
in terms of the initial perimeter and the genus of the surface.

###### keywords:

Hyperbolic geometry; Topology; Voronoi diagram; Algorithm

##  1 Introduction and motivation

Hyperbolic surfaces and their moduli spaces play an ubiquitous role in
mathematics, namely, through relationships with other areas including
Riemannian geometry, number theory, geometric group theory and mathematical
physics. Algorithms for surface groups, as combinatorial or topological
objects, have a rich history dating back to Dehn. Recently, in part motivated
by applications in other sciences [1, 16], there has been a push to understand
hyperbolic structures on surfaces from the point of view of computational
geometry.

Dealing with hyperbolic surfaces necessarily involves describing them — or
even visualizing them — meaningfully. A fundamental domain (in the hyperbolic
plane) with a side pairing is one way to determine a hyperbolic metric on the
surface. Lengths of curves in a pants decomposition and their associated
pasting parameters (so-called Fenchel-Nielsen coordinates) are another. No
matter which construction or parameter set used, it is always interesting to
know to which extent two different constructions output the “same” surface,
where “same” can take different meanings. However, these representations,
either by a fundamental domain or a set of Fenchel-Nielsen coordinates, are
not unique, and determining a canonical representation is challenging for
either option. In this paper, we tackle this question for fundamental domains,
by computing a so-called Dirichlet domain.

Roughly speaking, a Dirichlet domain of a hyperbolic surface is a fundamental
polygon in the hyperbolic plane, with a special point where distances to that
point in the polygon correspond to distances on the surface. Another way of
thinking of them is that it is a Voronoi cell associated to a lift of a single
point of the surface to its universal cover $\mathbb{H}^{2}$. A more precise
definition is given in the next section. Note that for hyperbolic surfaces any
given surface has infinitely many Dirichlet domains up to isometry. This is in
strong contrast to, for example, flat tori. Nonetheless, when describing a
surface via fundamental domains, the prize for the most relevant geometric
domain undoubtedly goes to Dirichlet domains because they visualize the
distance function for a given point. As far as we know, there is only one
algorithm in the literature that computes a Dirichlet domain for a hyperbolic
surface and a given point [17]. Unfortunately, the run-time of the algorithm
is not studied and an analysis seems complicated.

The contribution of this paper is an algorithm that computes a Dirichlet
domain efficiently, and its analysis. The point defining the domain is not
given as input, but it is part of the output. The Dirichlet domain of a given
input point can then be computed with a complexity that only depends of the
genus of the surface [10]. Our main result is the following:

######  Theorem 1.1.

Let $S$ be a closed orientable hyperbolic surface of genus $g$ given by a
fundamental polygon of perimeter $L$ and side pairings. A Dirichlet domain for
$S$ can be computed in $O((g^{2}L)^{6g-4})$ time.

A key ingredient is the use of _Delaunay triangulations_ on hyperbolic
surfaces, an area of research that has recently gained traction, both from an
experimental and a theoretical perspective [3, 7, 4, 14, 8, 12]. Recently, it
has been shown that the well-known flip algorithm that computes the Delaunay
triangulation of a set of points in the Euclidean plane $\mathbb{E}^{2}$ also
works on a hyperbolic surface; the complexity result announced in Theorem 1.1
crucially depends on the only known upper bound on the complexity of this
Delaunay flip algorithm [11]. The algorithm subsumes the real RAM model.
Studying the algebraic numbers involved in the computations goes beyond the
scope of this paper.

The paper is structured as follows: In Section 3, we give an overview of the
algorithm and we present the data structure. Sections 4 and 5 explain in
detail the main two steps of the algorithm, which output a geometric
triangulation of the surface having only one vertex. Finally, Section 6 builds
on the literature and concludes the proof of Theorem 1.1 with the last step of
the algorithm.

##  2 Preliminaries

We begin by recalling a collection of facts and setting notations, and we
refer to [2, 5, 13] for details. The surfaces studied in this paper are
assumed to be closed, orientable, and of genus $g\geq 2$. We begin with a
topological surface and endow it with a hyperbolic metric to obtain a
hyperbolic surface, generally denoted by $S$. A hyperbolic surface is locally
isometric to its universal covering space, the hyperbolic plane
$\mathbb{H}^{2}$. Such surfaces can always be obtained by considering the
quotient of $\mathbb{H}^{2}$ under the action of $\Gamma$, a discrete subgroup
of isometries of $\mathbb{H}^{2}$ isomorphic to the fundamental group
$\pi_{1}(S)$.

Let $S:=\mathbb{H}^{2}/\Gamma$ be a hyperbolic surface of genus $g$ and
fundamental group $\Gamma$. The projection map is denoted as
$\rho:\mathbb{H}^{2}\rightarrow S=\mathbb{H}^{2}/\Gamma$. We denote by
$\widetilde{x}\in\rho^{-1}(x)$ one of the lifts, to $\mathbb{H}^{2}$, of an
object $x$ on $S$. More generally, objects in $\mathbb{H}^{2}$ are denoted
with $\widetilde{\leavevmode\nobreak\ }$.

A _fundamental domain_ $\mathcal{F}$ for the action of $\Gamma$ is defined as
a closed domain, i.e.,
$\overline{\operatorname{int}(\mathcal{F})}=\mathcal{F}$, such that
$\Gamma\mathcal{F}=\mathbb{H}^{2}$ and the interiors of different copies of
$\mathcal{F}$ under $\Gamma$ are disjoint.

For a point $\widetilde{x}\in\mathbb{H}^{2}$, the _Dirichlet domain_
$\mathcal{D}_{\widetilde{x}}$ is defined as the Voronoi cell containing
$\widetilde{x}$, of the Voronoi diagram associated to the point set
$\Gamma\widetilde{x}$. In other words,

$\mathcal{D}_{\widetilde{x}}=\\{\>\widetilde{y}\in\mathbb{H}^{2}\>|\>d_{\mathbb{H}^{2}}(\widetilde{x},\widetilde{y})\leq
d_{\mathbb{H}^{2}}(\widetilde{x},\Gamma\widetilde{y})\>\\}=\\{\>\widetilde{y}\in\mathbb{H}^{2}\>|\>d_{\mathbb{H}^{2}}(\widetilde{x},\widetilde{y})\leq
d_{\mathbb{H}^{2}}(\Gamma\widetilde{x},\widetilde{y})\>\\},$

where the equality is true since $\Gamma$ acts as isometries w.r.t.
$d_{\mathbb{H}^{2}}$. The Dirichlet domain is a compact convex fundamental
domain for $\Gamma$ with finitely many geodesic sides [2, §9.4] and is
generally considered a canonical choice of fundamental domain. A property of
Dirichlet domains, of interest for the conception of algorithms, is that, by
the triangle inequality,

$\operatorname{diam}(\mathcal{D}_{\widetilde{x}})\leq
2\operatorname{diam}(S)\leq
2\operatorname{diam}(\mathcal{D}_{\widetilde{x}}),$

where $\operatorname{diam}(\cdot)$ denotes the diameter.

###  2.1 Curves, paths, and loops

Recall that a closed curve is the image of $\mathbb{S}^{1}$ under a continuous
map; a curve is non-trivial (or essential) if it is not freely homotopic to a
point. Similarly, a path is a continuous image of the interval $[0,1]$, and
the images of $0$ and $1$ are referred to as its endpoints. A loop is a path
whose endpoints are equal; this endpoint is referred to as its basepoint.

For a closed curve or loop $c$, we will denote by $[c]$ its free homotopy
class, and, if $c$ is based in a point $p$, by $[c]_{p}$ its homotopy class of
loops based in $p$. For a path $c$ between points $p$ and $q$, we denote by
$[c]_{p,q}$ the homotopy class of the path with fixed endpoints. We will
readily make use of the fact that if $c$ is closed non-trivial curve on a
hyperbolic surface, then in $[c]$ there is a unique closed geodesic.
Similarly, if $c$ is a loop based in $p$, in $[c]_{p}$ there is a unique
closed geodesic loop, and if $c$ is a path between $p$ and $q$, in $[c]_{p,q}$
there is a unique geodesic path. If $c$ is a simple closed curve then the
closed geodesic in $[c]$ is also simple, but this is no longer necessarily the
case for loops or paths with basepoints.

The intersection number $i(c,c^{\prime})$ between homotopy classes of curves
$c$ and $c^{\prime}$ is defined as the minimal intersection among its
representatives. Note that closed geodesics on a hyperbolic surface always
intersect minimally. The situation for paths is slightly different. The unique
geodesic representatives of paths (with fixed end points) might not intersect
minimally. This subtlety plays a key technical role in our story.

###  2.2 Fundamental polygon

Let $S$ be a (closed) hyperbolic surface of genus $g$ and fundamental group
$\Gamma$. A polygon $P\subset\mathbb{H}^{2}$ (i.e., a circular sequence of
geodesic edges) bounding a fundamental domain for $\Gamma$ (as defined in the
introduction) is called a fundamental polygon. Poincaré’s theorem implies that
$\Gamma$ is generated by the side pairings on $P$ [2, $\S 9.8$]. The edges and
vertices of $P$ project to a graph $G_{P}$ on $S$; the region enclosed by $P$
projects to the unique face of $G_{P}$.

The numbers $n_{G}$ of vertices and $m_{G}$ of edges of $G_{P}$ satisfy
Euler’s relation $n_{G}-m_{G}+1=2-2g$, as there is only one face. It follows
that if $G_{P}$ only has one vertex, then that vertex is incident to the
$m_{G}=2g$ edges, which are actually all loops. The number of vertices is
maximal when they all have degree 3 (then there are no loops); in this case
$3n_{G}=2m_{G}$, so, $m_{G}=6g-3$ and $n_{G}=4g-2$. More generally, the number
$2m_{G}$ of edges and vertices of $P$ lies between the two extreme cases:
$4g\leq 2m_{G}\leq 12g-6$. When $2m_{G}<12g-6$, some vertices of $P$ project
to the same vertex of $G_{P}$, i.e., they belong to the same orbit under
$\Gamma$. $G_{P}$ has a loop for each edge whose vertices are in the same
orbit; then the projected point on $S$ is incident to that loop twice.

##  3 Algorithm overview

Let $S$ be a (closed) hyperbolic surface of genus $g$ and fundamental group
$\Gamma$.

We propose the algorithm sketched below to compute a Dirichlet fundamental
domain of $S$. The output of Step 1 will be denoted with primes; it will be
used as input for Step 2, whose output will be denoted with double primes.

  1. 1.

Construct a system $\beta^{\prime}_{0},\ldots,\beta^{\prime}_{2g-1}$ of simple
topological loops based at the same point $b^{\prime}$ that cuts $S$ into a
disk (Section 4).

  2. 2.

Find a point $b^{\prime\prime}$ so that the system of geodesic loops based at
$b^{\prime\prime}$, conjugate to the ones computed in Step (1), is embedded
(Section 5).

  3. 3.

Construct the Dirichlet domain of a lift $\widetilde{b^{\prime\prime}}$ of
$b^{\prime\prime}$ (Section 6).

Obviously, the complexity of the algorithm heavily depends on the data
structure used to store the objects involved in the constructions. As the
algorithm actually operates in the universal covering space $\mathbb{H}^{2}$
of $S$, it is natural to present the data structure in $\mathbb{H}^{2}$. We
assume that, as input, we are given a fundamental polygon
$\Pi\subset\mathbb{H}^{2}$ for $\Gamma$, together with side pairings, as in
Section 2.2. The data structure described below is actually equivalent to a
combinatorial map [15, Section 3.3] on $S$, enriched with geometric
information. In particular, for each vertex $x$ of $G_{\Pi}$ (the projection
of $\Pi$ onto $S$, as in Section 2.2), the sequence of edges around $x$ is
ordered (edges that correspond to a loop appear twice).

#### Description of the input.

Let a representative $\widetilde{e_{i}},i=0,\ldots,m-1$ be chosen for each
couple of paired edges of $\Pi$ and denote as $\gamma_{0},\ldots,\gamma_{m-1}$
the corresponding side pairings in $\Pi$: the other edge of the couple is
${\gamma_{i}}^{\scriptscriptstyle-1}\widetilde{e_{i}}$, where
${\gamma_{i}}^{\scriptscriptstyle-1}$ is the inverse of $\gamma_{i}$. We
denote the set of the $2m$ edges of $\Pi$ as $E_{\Pi}$ and the set of its $2m$
vertices as $V_{\Pi}$. We choose a representative
$\widetilde{v_{j}},j=0,\ldots,n-1$ for each orbit of vertices of $\Pi$; $n$ is
the number of vertices of $G_{\Pi}$.

Each element of $\Gamma$ can be represented as a word on the alphabet
$\mathcal{A}_{\Gamma}=\\{\mathbb{1},\gamma_{0},\ldots,\gamma_{m-1},\\\
{\gamma_{0}}^{\scriptscriptstyle-1},\ldots,{\gamma_{m-1}}^{\scriptscriptstyle-1}\\}$,
where $\mathbb{1}$ denotes the identity in $\Gamma$. Here, letters of
$\mathcal{A}_{\Gamma}$ and the corresponding generators in $\Gamma$ are
denoted by the same symbol; this should not cause any confusion.

The data structure is roughly a doubly linked list of edges of $\Pi$, which
stores the combinatorial information. Additional information is necessary to
store the geometry (i.e., the positions of the vertices of $\Pi$ in
$\mathbb{H}^{2}$) and the side pairings. The data stored for each edge and
vertex is constant, so the size of the data structure is $O(g)$ (we do not try
to shave constants in the $O()$).

Concretely, for each edge $\widetilde{x}\in E_{\Pi}$, the data structure
stores:

  * •

two pointers $\mathsf{prev}(\widetilde{x})$ and $\mathsf{next}(\widetilde{x})$
that give access to the previous and next edges in $\Pi$, respectively (in
counterclockwise order);

  * •

two pointers $\mathsf{source}(\widetilde{x})$ and
$\mathsf{target}(\widetilde{x})$ that give access to the source and target of
$\widetilde{x}$ in $\Pi$, respectively (in counterclockwise order); when
$\rho\widetilde{x}$ is a loop in $G_{\Pi}$, $\mathsf{source}(\widetilde{x})$
and $\mathsf{target}(\widetilde{x})$ lie in the same orbit under $\Gamma$;

  * •

a pointer to the paired edge $\mathsf{pair}(\widetilde{x})$ in $\Pi$;

  * •

a letter $\mathsf{w}(\widetilde{x})\in\mathcal{A}_{\Gamma}$ that encodes the
relation between $\widetilde{x}$ and $\mathsf{pair}(\widetilde{x})$:
$\mathsf{w}(\widetilde{x})=\begin{dcases*}\mathbb{1}&if
$\widetilde{x}=\widetilde{e_{i}}$\\\ \gamma_{i}&if
$\widetilde{x}={\gamma_{i}}^{\scriptscriptstyle-1}\widetilde{e_{i}}$\end{dcases*}$
for some $i\in\\{0,\ldots,m-1\\}$.

By definition,
$\mathsf{pair}(\widetilde{x})=\begin{dcases*}{\gamma_{i}}^{\scriptscriptstyle-1}\widetilde{x}&when
$\mathsf{w}(\widetilde{x})=\mathbb{1}$ ($\widetilde{x}=\widetilde{e_{i}}$)\\\
\gamma_{i}\widetilde{x}&when
$\mathsf{w}(\widetilde{x})=\gamma_{i}$\end{dcases*}$.

For each vertex $\widetilde{y}\in V_{\Pi}$, the data structure stores:

  * •

$\mathsf{point}(\widetilde{y})$, which is the representative point of its
orbit: $\mathsf{point}(\widetilde{y})=\widetilde{v_{j}}$ for some
$j\in\\{0,\ldots,n-1\\}$;

  * •

a word $\gamma_{\widetilde{y}}$ on $\mathcal{A}_{\Gamma}$ (equivalently,
$\gamma_{\widetilde{y}}\in\Gamma$), which specifies the precise position
$\gamma_{\widetilde{y}}\,\mathsf{point}(\widetilde{y})$ of $\widetilde{y}$ in
$\mathbb{H}^{2}$.

The graph $G_{\Pi}$ lifts in the universal covering space $\mathbb{H}^{2}$ to
the (infinite) graph $\rho^{-1}{G_{\Pi}}=\Gamma\Pi$. In particular, the
sequence of edges of $\Gamma\Pi$ incident to a given vertex
$\widetilde{v}\in\rho^{-1}{v}$ is a sequence of lifts of the edges incident to
$v$ in $G_{\Pi}$. Each of these lifts is the image by an element of $\Gamma$
of an edge of $\Pi$ (Figure 1). The following result is straightforward from
the data structure. We still prove it for completeness.

######  Lemma 3.1.

Let $e$ be an edge of $G_{\Pi}$ and $v$ a vertex of $e$. The sequence of edges
of $G_{\Pi}$ incident to $v$ can be found in time $O(g)$.

######  Proof 3.2.

Without loss of generality (this can always be achieved by renaming edges and
vertices of $\Pi$) $\widetilde{v}=\mathsf{source}(\widetilde{e})$ (as in
Figure 1 for $e=e_{0}$), or $\widetilde{v}=\mathsf{target}(\widetilde{e})$.
Consider the first case. After $e$, the next edge incident to $v$ in
counterclockwise order in $G_{\Pi}$ is given in $\Pi$ by
$\widetilde{x}=\mathsf{prev}(\widetilde{e})$, whose vertex
$\mathsf{target}(\widetilde{x})$ is $\widetilde{v}$. The next edge incident to
$v$ in $G_{\Pi}$ is given by $\mathsf{prev}(\mathsf{pair}(\widetilde{x}))$,
whose target vertex lies in the same orbit as $\widetilde{v}$ under $\Gamma$.
And so on: a sequence of accesses to $\mathsf{pair}(\cdot)$ and
$\mathsf{prev}(\cdot)$ allows us to find the edges of $\Gamma\Pi$ incident to
$\widetilde{v}$ in counterclockwise order. The process perfoms a constant
number of accesses for each edge incident to $\widetilde{v}$, and the number
of such edges is linear in $g$ as recalled above. The case when
$\widetilde{v}=\mathsf{target}(\widetilde{e})$ is similar:
$\mathsf{next}(\cdot)$ is used instead of $\mathsf{prev}(\cdot)$.

In addition, the precise positions in $\mathbb{H}^{2}$ of all vertices of
$\Pi$ in the orbit $\rho^{-1}{v}$ can be computed along the process using the
information $\mathsf{point}(\cdot)$ and $\mathsf{w}(\cdot)$ stored in the data
structure, without changing the complexity.

Relations in the finitely presented group [6, Chapter 5.5] $\Gamma$ can be
deduced by comparing the two sequences of edges —clockwise and
counterclockwise— around each vertex.

Figure 1: (Top) The graph $G_{\Pi}$. The arrow around vertex $v$ shows its
incident edges. (Bottom) The fundamental polygon $\Pi$. Vertices
$\widetilde{s},\widetilde{u},\widetilde{v}$, and $\widetilde{w}$ of $\Pi$ are
chosen as representatives of the orbits of $s,u,v$, and $w$, respectively. The
arrows show the combinatorics of the tiling $\Gamma\Pi$ at the three vertices
of $\Pi$ in the orbit $\rho^{-1}{v}$:
$\widetilde{v},\gamma_{0}\widetilde{v}=\gamma_{2}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{v}$,
and
${\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{v}={\gamma_{2}}^{\scriptscriptstyle-1}\gamma_{0}$.

##  4 Constructing the initial system of simple loops

The combinatorial part of Step 1 of the algorithm is quite common in the
topology literature: it consists in computing a spanning tree $\mathcal{T}$ of
$G_{\Pi}$, then the edges of $\mathcal{T}$ are contracted, so that each vertex
of $\mathcal{T}$ is merged into the root, and each edge of $G_{\Pi}$ that is
not an edge of $\mathcal{T}$ is transformed into a loop based at the root.
This is illustrated in genus 2 by Figure 2(Top). In this example,
$\mathcal{T}$ has three edges $e_{1},e_{5},$ and $e_{6}$. If $v$ is chosen as
the root, edge $e_{0}$ transforms into a loop based at $v$ when $e_{1}$ and
$e_{6}$ are contracted.

However, topology is not enough in this work. We actually compute the geometry
of each loop that is obtained from the contraction of $\mathcal{T}$ by
precisely computing a lift.

The main result of this section is as follows:

######  Proposition 4.1.

Let $S$ be a closed orientable surface of genus $g$ and $\Pi$ a fundamental
polygon of $S$ with $2m$ edges and side pairings as described in Section 3. A
system of loops based at a common point on $S$, given by a circular list of
geodesic segments in $\mathbb{H}^{2}$ and side pairings, can be constructed in
time $O(g^{3})$. The total length of this system of loops is $O(gL)$, where
$L$ denotes the perimeter of $\Pi$.

The construction algorithm proceeds in three phases:

  1. (i).

Compute a spanning tree $\mathcal{T}$ of $G_{\Pi}$. A root $b$ is chosen for
$\mathcal{T}$, together with an edge $e_{0}$ incident to $b$ in
$G_{\Pi}\setminus\mathcal{T}$ and lifts $\widetilde{b}$ and
$\widetilde{e_{0}}$ in $\Pi$. Up to a renaming of representatives in orbits,
we can assume that $\widetilde{b}=\mathsf{source}(\widetilde{e_{0}})$.

  2. (ii).

Construct a new fundamental domain $\Pi^{\prime}$, as a polygon whose edges
are paths consisting of $O(g)$ geodesic segments in $\Gamma\Pi$: in each such
path, one segment is a lift of an edge of $G_{\Pi}\setminus\mathcal{T}$, and
the other segments are lifts of edges of $\mathcal{T}$; the endpoints of each
path lie in the orbit of $\widetilde{v}$. The side pairings in $\Pi^{\prime}$
are also computed.

  3. (iii).

Replace each path computed in the previous stage by the geodesic segment
between its vertices and keep the side pairings.

Note that $\Pi^{\prime}$ is a fundamental domain, but not a fundamental
polygon in the sense of Section 2.2: its edges are paths consisting of several
geodesic segments; the geodesic segments between its vertices (i.e., endpoints
of these paths) will intersect in general, so they do not bound a fundamental
domain. We will call such a polygon a _topological polygon_. Section 5 will
present the construction of a fundamental polygon from this topological
polygon (Step 2 of the algorithm).

The rest of this section is devoted to proving Proposition 4.1, by detailing
the construction.

######  Proof 4.2.

As in Section 3, $n$ denotes the number of vertices of $G_{\Pi}$. Phase (i) is
performed by a standard constuction of a minimum spanning tree $\mathcal{T}$
in $O(m\log n)$ or $O(m+n\log n)$, i.e., $O(g\log g)$. The tree has $n-1$
edges.

Phase (ii) consists of walking along the edges of $\Gamma\Pi$. The walk
constructs the new fundamental domain $\Pi^{\prime}$ in counterclockwise order
and stores it in a data structure that is very similar to the data structure
defined in Section 3 for $\Pi$. However some of its elements have a different
meaning, which will be detailed in the sequel; in particular, the elements
$\mathsf{pair}(\cdot)$ are actually not yet side pairings in this phase, but
temporary elements of $\Gamma$.

As a preprocessing step, for each edge $x$ of $G_{\Pi}\setminus\mathcal{T}$,
we find the path $\mathtt{p}(x)$ on $S$ whose homotopy class contains the loop
that will eventually replace $x$: it is given by the (unique and simple) path
in $\mathcal{T}$ from the root to a first vertex of $x$, followed by $x$, and
finally by the path in $\mathcal{T}$ from the second vertex of $x$ to the
root. In the example of Figure 2(Top), $e_{0}$ is replaced by a loop based at
$b=v$ that is homotopic to the sequence $\mathtt{p}(e_{0})=e_{0}\cdot
e_{6}\cdot e_{1}$, where $\cdot$ denotes concatenation of paths. The path for
edge $e_{4}$ is $\mathtt{p}(e_{4})=e_{1}\cdot e_{4}\cdot e_{6}\cdot
e_{1}^{-1}$; here, edge $e_{1}$ is traversed in both directions.

The walk starts at $\widetilde{b}$ and first considers edge
$\widetilde{e_{0}}$ chosen in stage (i). For each considered edge
$\widetilde{x}$ not in $\rho^{-1}{\mathcal{T}}$, by the pre-processing we have
just mentioned, we look for lifts of edges of $\mathtt{p}(x)$ in order in
$\Gamma\Pi$. This is easily done by a sequence of operations
$\mathsf{next}(\cdot),\mathsf{prev}(\cdot)$, and $\mathsf{pair}(\cdot)$ on
edges of $\Pi$, and turning around their vertices $\mathsf{source}(\cdot)$ and
$\mathsf{target}(\cdot)$ as in Lemma 3.1 until a lift of the next element of
$\mathtt{p}(x)$ is found. On the way, the elements $\mathsf{w}(\cdot)$ of
$\Gamma$ found in the data structure are collected so that the precise lift of
each edge or vertex of $\Pi^{\prime}$ is known.

Each time a lift of a path $\mathtt{p}(x)$, i.e., an edge of $\Pi^{\prime}$,
has been found, the algorithm proceeds to the next one. Note that edges (i.e.,
paths) appear on $\Pi^{\prime}$ in the same order as the order in which the
corresponding edges appear on $\Pi$: indeed, contracting the edges of
$\mathcal{T}$ does not change the order in which edges on $S$ are traversed to
describe the boundary of the face of $G_{\Pi}$.

Figure 2: (Top) The spanning tree $\mathcal{T}$ of $G_{\Pi}$ has edges
$e_{1},e_{5},e_{6}$ and is rooted at $v=b$. Each edge of
$G_{\Pi}\setminus\mathcal{T}$ is replaced by a loop based at $b$ when
contracting $\mathcal{T}$. (Bottom) The path in $\mathbb{H}^{2}$ corresponding
to the loop replacing $e_{0}$ starts at $\widetilde{b}$ and ends at
$\gamma_{6}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{b}$.

This is illustrated in Figure 2(Bottom). The walk starts from $\widetilde{b}$
and follows $\widetilde{e_{0}}$. The next edge in $\Pi$ is
$\mathsf{next}(\widetilde{e_{0}})=\widetilde{e_{6}}$, which projects onto the
next edge in $\mathtt{p}(e_{0})$. Then we must look for a lift of $e_{1}$
incident to $\mathsf{target}(\widetilde{e_{6}})$. This is done by going to
$\mathsf{pair}(\widetilde{e_{6}})={\gamma_{6}}^{\scriptscriptstyle-1}\widetilde{e_{6}}$
and turning around its source vertex. The first edge in counterclockwise order
is ${\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{e_{1}}$; the source vertex
of its image $\gamma_{6}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{e_{1}}$
is the target vertex of $\widetilde{e_{6}}$ and the walk traverses it. Its
target vertex is $\gamma_{6}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{b}$,
which is in the orbit of $\widetilde{b}$. We have now found the lift of
$\mathtt{p}(e_{0})$ in $\Gamma\Pi$ that forms the first edge of
$\Pi^{\prime}$: it is the sequence
$\widetilde{e_{0}}\cdot\widetilde{e_{6}}\cdot\gamma_{6}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{e_{1}}$.
From vertex $\gamma_{6}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{b}$ we
will now construct the edge of $\Pi^{\prime}$ corresponding to
$\widetilde{e_{2}}$, as $\widetilde{e_{2}}$ is the edge following
${\gamma_{0}}^{\scriptscriptstyle-1}\widetilde{e_{0}}$ in
$\Pi\setminus\rho^{-1}{\mathcal{T}}$. We know that
$\mathtt{p}(e_{2})=e_{2}\cdot e_{5}\cdot e_{1}$. Here, turning around the
source vertex of ${\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{e_{1}}$ gives
${\gamma_{2}}^{\scriptscriptstyle-1}\widetilde{e_{2}}$, and the walk continues
with $\gamma_{6}{\gamma_{2}}^{\scriptscriptstyle-1}\widetilde{e_{2}}$, then
turning around the source of
${\gamma_{2}}^{\scriptscriptstyle-1}\widetilde{e_{2}}$ we find
$\widetilde{e_{5}}$, and the walk follows $\gamma_{6}\widetilde{e_{5}}$. So
far we have only followed edges of $\gamma_{6}\Pi$, as the edge that we were
looking for when turning around vertices was always the first one. However,
this is not the case after $\gamma_{6}\widetilde{e_{5}}$. The target of the
representative ${\gamma_{5}}^{\scriptscriptstyle-1}\widetilde{e_{5}}$ is
${\gamma_{4}}^{\scriptscriptstyle-1}\widetilde{u}$, around which we must turn
until we find a lift of $e_{1}$; the next edge of $\Gamma\Pi$ that we follow
is thus
$\gamma_{6}\gamma_{5}{\gamma_{5}}^{\scriptscriptstyle-1}\gamma_{6}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{e_{1}}=\gamma_{6}\gamma_{6}{\gamma_{1}}^{\scriptscriptstyle-1}\widetilde{e_{1}}$,
which finishes the edge of $\Pi^{\prime}$ corresponding to
$\widetilde{e_{2}}$. Next, we would continue with $\widetilde{e_{3}}$ in the
same vein. And so on.

Note that, as we are constructing the fundamental domain $\Pi^{\prime}$,
following the order of the edges of $\Pi$, each edge
$\widetilde{e^{\prime}_{i}}$ of $\Pi^{\prime}$ defines a topological loop
$\beta_{i}^{\prime}$ based at $b$ on $S$, which represents the homotopy class
$[e^{\prime}_{i}]$. Such an edge $\widetilde{e^{\prime}_{i}}$ is formed by a
sequence of edges of $\Gamma\Pi$ that corresponds to the path
$\mathtt{p}(e_{i})$, for $e_{i}\in G_{\Pi}\setminus\mathcal{T}$, and will
naturally be paired with another sequence for the same $\mathtt{p}(e_{i})$
(traversed in the opposite direction around $\Pi^{\prime}$). The words
associated with the edges in the two sequences differ by an element of
$\Gamma$, which gives the side pairing $\gamma_{i}^{\prime}\in\Gamma$ for
$\Pi^{\prime}$.

Phase (iii) is easy. It consists in replacing each edge of $\Pi^{\prime}$ by
the geodesic segment between its two vertices, and keeping the associated side
pairings. As mentioned above, the corresponding geodesic loops may intersect
on $S$, though the topological loops that we choose to represent their
homotopy classes only intersect at their common basepoint.

As the edges of $\Pi^{\prime}$ project by construction to loops, all based at
the same point, there are $2g$ such loops on $S$ and $\Pi^{\prime}$ has $4g$
edges, each consisting of $O(g)$ edges (and vertices) of $\Gamma\Pi$. By Lemma
3.1, $O(g)$ operations are performed at each vertex. This shows the complexity
annonced in Proposition 4.1. The bound on the sum of the lengths of the
geodesic loops also follows directly.

Note that during the traversal detailed in the proof, we have computed for
each vertex $\widetilde{x}$ of $\Pi^{\prime}$ the element $\gamma\in\Gamma$
such that $\widetilde{x}=\gamma\widetilde{b}$. We store these elements of
$\Gamma$ in a table t, which will be used in the sequel, in addition to the
data main data structure.

We denote the output of this step 2 as follows: we re-index the sides of the
topological polygon $\Pi^{\prime}$ (which has $4g\leq 2m$ edges) so that the
side pairings are denoted as
$\gamma^{\prime}_{0},\ldots,\gamma^{\prime}_{2g-1}$ and the corresponding $2g$
topological loops on $S$ are
$\beta^{\prime}_{0},\ldots,\beta^{\prime}_{2g-1}$; these loops on $S$ do not
intersect except at their common basepoint $b$, which is now renamed to
$b^{\prime}$ for global consistency of notation, as announced at the beginning
of Section 3.

##  5 Finding an embedded system of loops

We want to find a collection of geodesic loops on a hyperbolic surface $S$,
all based in a single point and disjoint otherwise, and such that the
complementary region of the loops is a convex hyperbolic polygon. What we show
is that in fact we can retain the choice of topological loops
$\beta^{\prime}_{0},\ldots,\beta^{\prime}_{2g-1}$ made in Section 4 by moving
the basepoint appropriately to ensure that their geodesic realizations satisfy
the desired properties.

Consider the set of topological loops
$\beta^{\prime}_{0},\ldots,\beta^{\prime}_{2g-1}$ all based at point
$b^{\prime}$ constructed in the previous section. We choose a pair that
intersects minimally exactly once which, up to reordering, we can suppose are
$\beta^{\prime}_{0}$ and $\beta^{\prime}_{1}$. For future reference we set
$L_{0}:=\max\\{\ell(\beta^{\prime}_{0}),\ell(\beta^{\prime}_{1})\\}$, where
$\ell$ denotes the length.

######  Remark 5.1.

We can fix any loop to be $\beta^{\prime}_{0}$ and find a loop
$\beta^{\prime}_{1}$ intersecting it exactly once. Indeed, the set
$\beta^{\prime}_{0},\ldots,\beta^{\prime}_{2g-1}$ contains curves that
pairwise intersect at most once, and are all non-separating and thus
homologically non-trivial. As it generates homotopy, it also generates
homology and in particular every curve must be intersected by at least one
other curve. As they can intersect at most once, they intersect exactly once.

We begin by taking the unique geodesic loops, based in $b^{\prime}$, in the
free homotopy classes of $\beta^{\prime}_{0}$ and $\beta^{\prime}_{1}$, and we
replace the curves with these geodesic representatives (we keep the same
notation for convenience). Now we further consider the unique simple closed
geodesic representatives in the free homotopy class of $\beta^{\prime}_{0}$
and $\beta^{\prime}_{1}$, which we denote $\beta^{\prime\prime}_{0}$ and
$\beta^{\prime\prime}_{1}$, respectively. By hypothesis, they intersect in a
single point $b^{\prime\prime}$, which will be our new basepoint.

We now define a path between $b^{\prime\prime}$ and $b^{\prime}$ as follows.
We consider a single lift $\widetilde{\beta^{\prime}_{0}}$ of
$\beta_{0}^{\prime}$. Its endpoints both correspond to distinct lifts of
$b^{\prime}$ which are related by a unique translation $g_{0}$ in $\Gamma$.
The copies of $\widetilde{\beta^{\prime}_{0}}$ by iterates of $g_{0}$ form a
broken geodesic line with the same end points at infinity as the geodesic axis
of $g_{0}$. This singular geodesic, which we denote
$\hat{\beta_{0}^{\prime}}$, separates $\mathbb{H}^{2}$ into two half-spaces,
only one of which is convex. We now choose an endpoint of
$\widetilde{\beta^{\prime}_{0}}$ and consider a lift of $\beta_{1}^{\prime}$
that lies in the convex half-space. This lift we denote by
$\widetilde{\beta^{\prime}_{1}}$ and, as before, we consider the corresponding
translation $g_{1}$ in $\Gamma$ and its geodesic axis and its corresponding
singular geodesic $\hat{\beta_{1}^{\prime}}$. Now, we obtain
$\widetilde{b^{\prime\prime}}$ as the intersection of the axes of $g_{0}$ and
$g_{1}$. We consider the unique geodesic path $\widetilde{c}$ between
$\widetilde{b^{\prime}}$ and $\widetilde{b^{\prime\prime}}$ and its projection
$c$ on $S$. We first observe that we can control the length of this path $c$:

######  Lemma 5.2.

$\ell(c)<2L_{0}$.

######  Proof 5.3.

We observe that the axis of $g_{0}$ must lie in an $R$ neighborhood of
$\hat{\beta_{0}^{\prime}}$ where $R<\ell(\beta_{1}^{\prime})$. In particular,
the axis of $g_{1}$ intersects $\widetilde{\beta^{\prime}_{0}}$. Similarly,
the axis of $g_{0}$ intersects $\widetilde{\beta^{\prime}_{1}}$. Now the proof
essentially follows from drawing a picture of the above situation in
$\mathbb{H}^{2}$ (see Figure 3).

Figure 3: $c$ is homotopic on $S$ to the projection of the concatenation of
the bold arc of $\widetilde{\beta^{\prime}_{0}}$ from $\widetilde{b^{\prime}}$
and the bold segment of the axis of $g_{1}$.

By following an arc of $\widetilde{\beta^{\prime}_{0}}$ from
$\widetilde{b^{\prime}}$ and then a segment of length at most
$\ell(\widetilde{\beta^{\prime\prime}_{1}})$ on the axis $g_{1}$, we obtain a
path between $\widetilde{b^{\prime}}$ to $\widetilde{b^{\prime\prime}}$. As
such, we have

$\hskip
130.0002pt\ell(\widetilde{c})<\ell(\widetilde{\beta^{\prime}_{0}})+\ell(\widetilde{\beta^{\prime\prime}_{1}})$

and so by passing to the surface

$\hskip 150.00023pt\ell(c)<2L_{0}.$

Observe that for $i=0,1$, $\beta^{\prime\prime}_{i}$, based in
$b^{\prime\prime}$, is freely homotopic to $c^{-1}\cdot\beta^{\prime}_{i}\cdot
c$ and that there is a homeomorphism of $S$, isotopic to the identity, that
takes $b^{\prime}$ to $b^{\prime\prime}$ and that sends (the homotopy class
of) $\beta^{\prime}_{i}$ to $\beta^{\prime\prime}_{i}$. This homeomorphism is
often referred to as the point pushing map (see for instance [13, Section 4.2]
for details).

We can apply this same homeomorphism to the remaining curves. For
$i=0,\ldots,2g-1$ we set the homotopy class of loop $\beta^{\prime\prime}_{i}$
to be:

$[\beta^{\prime\prime}_{i}]_{b^{\prime\prime}}=[c^{-1}\cdot\beta^{\prime}_{i}\cdot
c]_{b^{\prime\prime}}.$ (5.1)

As we have just moved the basepoint by a homeomorphism, the homotopy classes
$[\beta^{\prime\prime}_{i}]_{b^{\prime\prime}}$ all have simple
representatives and can be realized disjointly outside of $b^{\prime\prime}$.
The following lemma implies that their unique geodesic representatives enjoy
this same property. It is well known to specialists, but we include a proof
sketch for completeness.

######  Lemma 5.4.

Let $\Sigma$ be a hyperbolic surface with piecewise-geodesic boundary such
that the interior angles on the singular points $s_{0},\ldots,s_{k-1}$ of the
boundary are cone points of angle $\leq\pi$. If
$[\alpha]_{p_{i},q_{i}},[\alpha^{\prime}]_{p_{j},q_{j}}$ are simple homotopy
classes of paths (with endpoints $p_{i},p_{j},q_{i},q_{j}$ in the set
$s_{0},\ldots,s_{k-1}$), and disjoint except for possibly in their endpoints,
then the unique geodesic representatives are also simple and disjoint.

_Sketch of proof._ We consider $\widetilde{\Sigma}$, the universal cover of
$\Sigma$, which we view as a (geodesically convex) subset of $\mathbb{H}^{2}$.
We lift $\partial\Sigma$ to $\widetilde{\Sigma}$ and representatives of
$[\alpha]_{p_{i},q_{i}}$ and $[\alpha^{\prime}]_{p_{j},q_{j}}$, which are
simple and disjoint, to the universal cover. Observe that being simple and
disjoint is equivalent to all individual lifts in $\mathbb{H}^{2}$ being
simple and pairwise disjoint. Now take two individual lifts of either $\alpha$
or $\alpha^{\prime}$, and their unique geodesic representatives. We will see
that they are also disjoint. Note that in general, given two simple disjoint
paths in the hyperbolic (or Euclidean) plane, the unique geodesics between
their endpoints might intersect (as already mentioned in Section 2.1).
However:

Observation: Let $C\subset\mathbb{H}^{2}$ be a convex with non-empty boundary,
and $p_{0},q_{0},p_{1},q_{1}\in\partial C$. Let $\alpha_{1}:[0,1]\to C$ and
$\alpha_{2}:[0,1]\to C$ be simple paths, disjoint in their interior, with
$\alpha_{0}(0)=p_{0},\alpha_{0}(1)=q_{0}$ and
$\alpha_{1}(0)=p_{1},\alpha_{1}(1)=q_{1}$. Then the unique geodesic between
$p_{0}$ and $q_{0}$ and the unique geodesic between $p_{1}$ and $q_{1}$ are
disjoint in their interior as well.

A key point is that, thanks to the angle condition on the cone points,
$\widetilde{\Sigma}$ is a convex region of $\mathbb{H}^{2}$. (This is just a
slightly more sophisticated observation than the elementary fact that a
polygon with all interior angles less than $\pi$ is convex.) The observation
now implies that the lifts of geodesics corresponding to $\alpha$ and
$\alpha^{\prime}$ are disjoint in their interior if and only if there are
representatives of $[\alpha]_{p_{i},q_{i}}$ and
$[\alpha^{\prime}]_{p_{j},q_{j}}$ that are, too, which, by hypothesis, is the
case. ∎

We can now apply Lemma 5.4 to the geodesic representatives of
$[\beta^{\prime\prime}_{i}]_{b^{\prime\prime}}$. For simplicity we denote by
$\beta^{\prime\prime}_{i}$ the unique geodesic loop in the corresponding
homotopy class.

######  Theorem 5.5.

Let $\beta^{\prime\prime}_{0},\ldots,\beta^{\prime\prime}_{2g-1}$ be a set of
topological loops based in $b^{\prime\prime}$ that cuts a surface $S$ into a
disk. Assume that $\beta^{\prime\prime}_{0}$ and $\beta^{\prime\prime}_{1}$
are closed geodesics. Then, the geodesic loops homotopic to
$\beta^{\prime\prime}_{0},\ldots,\beta^{\prime\prime}_{2g-1}$ are simple and
pairwise disjoint in their interiors. Furthermore, by cutting $S$ along those
geodesics and lifting to $\mathbb{H}^{2}$, one obtains a convex hyperbolic
polygon with $4g$ edges.

######  Proof 5.6.

As $\beta^{\prime\prime}_{0}$ and $\beta^{\prime\prime}_{1}$ are closed
geodesics, they form $4$ angles in $b^{\prime\prime}$, and the opposite ones
are equal. These angles thus satisfy $2\theta+2\theta^{\prime}=2\pi$ so in
particular both $\theta$ and $\theta^{\prime}$ are strictly less than $\pi$.
Thus by cutting along $\beta^{\prime\prime}_{0}$ and
$\beta^{\prime\prime}_{1}$, we obtain a genus $g-1$ surface with a boundary
consisting of $4$ geodesic segments, and with $4$ cone point singularities of
angles $<\pi$ (see Figure 4).

Figure 4: A visualization of the cutting along $\beta^{\prime\prime}_{0}$ and
$\beta^{\prime\prime}_{1}$.

We now proceed inductively for $i\geq 3$ and consider the unique geodesic path
$\beta^{\prime\prime}_{i}$, which by virtue of Lemma 5.4, has disjoint
interior from the previous geodesic segments. Furthermore, as each segment
further splits the angles, the angles are all less than $\pi$.

The end result is a polygon with all interior angles less than $\pi$ which, by
elementary hyperbolic geometry, is convex.

######  Proposition 5.7.

Let $S$ be hyperbolic of genus $g$ and $\Pi^{\prime}$ a topological
fundamental polygon of $S$ with $4g$ edges and side pairings as described at
the end of Section 4. A convex fundamental polygon $\Pi^{\prime\prime}$ with
its side pairing and whose vertices project to a single vertex on $S$, can be
constructed in $O(g)$ time. The perimeter of $\Pi^{\prime\prime}$ is
$O(gL^{\prime})$, where $L^{\prime}$ denotes the total length of the sides of
$\Pi^{\prime}$.

######  Proof 5.8.

We need to compute the output convex polygon $\Pi^{\prime\prime}$ i.e., $4g$
lifts of $b^{\prime\prime}$ and $2g$ side pairings
$\gamma^{\prime\prime}_{0},\cdots,\gamma^{\prime\prime}_{2g-1}$. As homotopy
classes of $\beta^{\prime\prime}_{i}$ and $\beta^{\prime}_{i}$ are conjugates
for $i=0,\ldots,2g-1$ (Equation 5.1), the side pairing
$\gamma^{\prime\prime}_{i}$ is equal to $\gamma^{\prime\prime}_{i}$ for each
$i$.

The key point here is the computation of a lift of $b^{\prime\prime}$. The
first step consists in finding the loops $\beta^{\prime}_{0}$ and
$\beta^{\prime}_{1}$ satisfying $i(\beta^{\prime}_{0},\beta^{\prime}_{1})=1$.
As shown in Remark 5.1, we can choose any loop for $\beta^{\prime}_{0}$. We
also fix $\widetilde{b_{0}^{\prime}}$ to be an endpoint of one of the two
paired sides of $\Pi^{\prime}$ that are lifts of $\beta^{\prime}_{0}$. We
compute the ordered sequence of loops around $b^{\prime}$ as in Lemma 3.1, in
$O(g)$ operations; recall that each loop
$\beta^{\prime}_{0},\ldots,\beta^{\prime}_{2g-1}$ appears twice in the
sequence (Section 2.2). We take as $\beta^{\prime}_{1}$ one of the loops that
alternate with $\beta^{\prime}_{0}$ in the sequence, and choose for
$\widetilde{\beta^{\prime}_{1}}$ one of its two lifts that are incident to
$\widetilde{b_{0}^{\prime}}$.

The second step consists in finding the free geodesics in the homotopy classes
of $\beta^{\prime}_{0}$ and $\beta^{\prime}_{1}$, respectively. In t, we find
the word $g_{0}$ on $\\{\gamma^{\prime}_{0},\cdots,\gamma^{\prime}_{2g-1}\\}$
representing the translation that sends $\widetilde{b_{0}^{\prime}}$ to the
other endpoint of $\widetilde{\beta^{\prime}_{0}}$ (see Figure 5). The
sequences $g_{0}^{n}(\widetilde{b^{\prime}_{0}})$ and
$g_{0}^{-n}(\widetilde{b^{\prime}_{0}})$ converge in $\mathbb{C}$ to two
points on the unit circle: these points are the two (infinite in
$\mathbb{H}^{2}$) fixed points of the translation $g_{0}$, i.e., the two
solutions of equation $g_{0}(z)=z$ in $\mathbb{C}$. The axis of $g_{0}$, i.e.,
the geodesic between these two points, projects onto $S$ to the free geodesic
in $[\beta^{\prime}_{0}]$.

Figure 5: The computation of $b^{\prime\prime}$ from $b^{\prime}$.

We repeat the same process with $\widetilde{\beta^{\prime}_{1}}$ and find the
geodesic in $\mathbb{H}^{2}$ that projects to the free geodesic in
$[\beta^{\prime}_{1}]$. The point $\widetilde{b_{0}^{\prime\prime}}$ comes as
the intersection point of the two geodesics in $\mathbb{H}^{2}$. We now define
$\widetilde{\beta^{\prime\prime}_{0}}$ as the geodesic segment between
$\widetilde{b_{0}^{\prime\prime}}$ and
$w_{0}(\widetilde{b_{0}^{\prime\prime}})$, and
$\widetilde{\beta^{\prime\prime}_{1}}$ in the same way. This step is performed
in constant time.

We can now compute the $4g$ lifts of $b^{\prime\prime}$ that are the vertices
of $\Pi^{\prime\prime}$ by applying the elements of t to
$\widetilde{b_{0}^{\prime\prime}}$. This last step has complexity $O(g)$.
Additionally, we have

$\hskip
100.00015pt\ell(\beta_{i}^{\prime\prime})\leq\ell(\beta_{i}^{\prime})+2\ell(c)=5\cdot(\max_{j}\ell(\beta_{j}^{\prime}))$

for each $i=1,\ldots,2g-1$ (by Lemma 5.2) and thus the perimeter of
$\Pi^{\prime\prime}$ is $O(g)$ times bigger than the perimeter $\Pi^{\prime}$.

##  6 Finding a Dirichlet domain from an embedded system of loops

We first summarize what we have obtained so far. We started with a polygon
$\Pi$ of perimeter $L$ and we obtained a convex polygon $\Pi^{\prime\prime}$
of total length $O(g^{2}L)$. Additionally, all vertices of
$\Pi^{\prime\prime}$ project on a single vertex $b^{\prime\prime}$ on $S$.
This construction has complexity $O(g^{3})$ by Propositions 4.1 and 5.7. At
this point, it is easy to compute a Dirichlet domain. Indeed, we can now
triangulate $\Pi^{\prime\prime}$ easily since it is convex and, thus, we
obtain a geometric triangulation $T$, on to which the Delaunay flip algorithm
can be applied [11]. The complexity of this algorithm depends on the diameter
of $T$, for which the perimeter of $\Pi^{\prime\prime}$ is an upper bound.

The output of the flip algorithm is a Delaunay triangulation $DT$ of $S$ with
the single vertex $b^{\prime\prime}$ computed in Section 5. To obtain a
Dirichlet domain from $DT$, we just have to compute the triangles of
$\widetilde{DT}$ incident to a lift $\widetilde{b^{\prime\prime}}$ of
$b^{\prime\prime}$ and their dual: we compute the circumcenter of each
triangle to obtain the vertices of the Dirichlet domain and we put a geodesic
between vertices that correspond to adjacent triangles around
$\widetilde{b^{\prime\prime}}$. This step is also clearly done in $O(g)$
operations. Putting all together we obtain the following theorem:

######  Theorem 6.1.

Let $S$ be a closed orientable hyperbolic surface of genus $g$ given by a
fundamental polygon of perimeter $L$ and side pairings. A Dirichlet domain of
$S$ can be computed in time $O(f(g^{2}L)+g^{3})$ where $f(\Delta)$ is the
complexity of the flip algorithm for a triangulation of diameter $\Delta$ with
a single vertex.

Using the best known bound for the flip algorithm so far, we obtain Theorem
1.1 stated in the introduction as a corollary. Note that the constant in the
$O()$ depends on the metric on $S$. However, there are experimental and
theoretical insights suggesting that the actual complexity of the flip
algorithm may be much better [9].

## References

  * [1] N.L. Balazs and A. Voros.  Chaos on the pseudosphere.  Physics Reports, 143(3):109–240, 1986.  doi:10.1016/0370-1573(86)90159-6.
  * [2] Alan F. Beardon.  The Geometry of Discrete Groups.  Springer-Verlag, 1983.
  * [3] Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud.  Hyperbolic Delaunay complexes and Voronoi diagrams made practical.  Journal of Computational Geometry, 5:56–85, 2014.  doi:10.20382/jocg.v5i1a4.
  * [4] Mikhail Bogdanov, Monique Teillaud, and Gert Vegter.  Delaunay triangulations on orientable surfaces of low genus.  In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:17, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik.  doi:10.4230/LIPIcs.SoCG.2016.20.
  * [5] Peter Buser.  Geometry and spectra of compact Riemann surfaces.  Modern Birkhäuser classics. Birkhaäuser, Boston, Mass., 2nd edition, 2010.
  * [6] H. S. M. Coxeter and W. O. J. Moser.  Generators and Relations for Discrete Groups.  Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1957.
  * [7] Jason DeBlois.  The centered dual and the maximal injectivity radius of hyperbolic surfaces.  Geometry and Topology, 19(2):953–1014, 2015.  doi:10.2140/gt.2015.19.953.
  * [8] Jason DeBlois.  The Delaunay tessellation in hyperbolic space.  Mathematical Proceedings of the Cambridge Philosophical Society, 164(1):15–46, 2018.  doi:10.1017/S0305004116000827.
  * [9] Vincent Despré, Loïc Dubois, Benedikt Kolbe, and Monique Teillaud.  Experimental analysis of Delaunay flip algorithms on genus two hyperbolic surfaces.  Preprint, INRIA, May 2021.  URL: https://hal.inria.fr/hal-03462834/.
  * [10] Vincent Despré, Benedikt Kolbe, and Monique Teillaud.  Representing infinite hyperbolic periodic Delaunay triangulations using finitely many Dirichlet domains.  Preprint, INRIA, July 2021.  URL: https://hal.archives-ouvertes.fr/hal-03045921.
  * [11] Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud.  Flipping geometric triangulations on hyperbolic surfaces.  In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.SoCG.2020.35.
  * [12] Matthijs Ebbens, Hugo Parlier, and Gert Vegter.  Minimal Delaunay triangulations of hyperbolic surfaces.  In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.SoCG.2021.31.
  * [13] Benson Farb and Dan Margalit.  A Primer on Mapping Class Groups (PMS-49).  Princeton University Press, 2012.  URL: http://www.jstor.org/stable/j.ctt7rkjw.
  * [14] Iordan Iordanov and Monique Teillaud.  Implementing Delaunay triangulations of the Bolza surface.  In 33rd International Symposium on Computational Geometry (SoCG 2017), pages 44:1–44:15, Brisbane, Australia, July 2017.  doi:10.4230/LIPIcs.SoCG.2017.44.
  * [15] Bojan Mohar and Carsten Thomassen.  Graphs on Surfaces.  Johns Hopkins University Press, Baltimore, 2001.
  * [16] Nikolai C Passler, Xiang Ni, Guangwei Hu, Joseph R Matson, Giulia Carini, Martin Wolf, Mathias Schubert, Andrea Alù, Joshua D Caldwell, Thomas G Folland, et al.  Hyperbolic shear polaritons in low-symmetry crystals.  Nature, 602(7898):595–600, 2022.  doi:10.1038/s41586-021-04328-y.
  * [17] John Voight.  Computing fundamental domains for Fuchsian groups.  Journal de Théorie des Nombres de Bordeaux, 21(2):467–489, 2009\.  doi:10.5802/jtnb.683.


# Quantum Superposition States: Spin Glasses and Entanglement

Aslı Tuncer<EMAIL_ADDRESS>Koç University, Institute of Physics,
Istanbul,Turkey  Serhat C. Kadıoğlu<EMAIL_ADDRESS>Koç University,
Institute of Physics, Istanbul,Turkey

###### Abstract

Spin-glass (SG) is a fascinating system that has garnered significant
attention due to its intriguing properties and implications for various
research fields. In condensed matter physics, SGs are a prototypical example
of disordered systems and have been studied extensively to understand the
behavior of complex systems with the random disorder. One of the key
characteristics of SGs is that they contain random disorder, which leads to
many possible states of the system occurring with very close probabilities. We
explore the concept of spin-glass superposition states (SSs), which are
equiprobable SSs of possible electronic configurations. Using the Edward-
Anderson (EA) type SG order parameter and magnetization, we demonstrate that
these SSs can be classified based on their contribution to distinguishing
magnetic order (disorder), such as SG, (anti)ferromagnetic, and paramagnetic
phases. We also generalize these SSs based on the system size and investigate
the entanglement of these phase-based SSs using the negativity measure. We
show that the SG order parameter can be utilized to determine the entanglement
of magnetically ordered (disordered) phases, or vice versa, with negativity
signifying magnetic order. Our findings provide further insight into the
nature of quantum SSs and their relevance to SGs and quantum magnets. They
have implications for a range of fields, including condensed matter physics,
where SGs are a prototypical example of disordered systems. They are also
relevant for other fields, such as neural networks, optimization problems, and
information storage, where complex systems with random disorder behavior are
greatly interested. Overall, our study provides a deeper understanding of the
behavior of spin glasses and the nature of quantum SSs, with potential
applications in a variety of fields.

quantum superposition states, spin glasses, quantum magnets, entanglement

##  I Introduction

Spin glasses are a fascinating phenomenon in condensed matter physics due to
their unique microscopic properties. However, these systems contain random
disorder, resulting in many possible states occurring with similar
probabilities [1, 2, 3] and being unable to arrange in a particular spin
state, which satisfies the energy minimum for each interaction [4, 5]. Such a
situation is called frustration [6]. Even if a system is unfrustrated
classically, it may exhibit frustration in the quantum case [7, 8, 9, 10, 11]
due to non-commutativity and entanglement [9, 12]. Interestingly, even with
just a few entangled elements, novel phenomena can occur in the quantum domain
[9, 12, 13, 14]. Quantum fluctuations and entanglement can also play essential
roles in the behavior of spin glasses since the spin glass order occurs at low
temperatures [13], and thermal fluctuations do not dominate the feature of
spin-glass order. Quantum interference may also lead to unexpected effects,
such as the suppression of tunneling [15] or the formation of localized states
[16, 17]. Spin glasses, on the other hand, should have frustrated spin(s).
When considered from the quantum perspective, the complex behavior of spin
glasses is understandable as arising from quantum interference and
entanglement of formation.

The frustration results in a complex and disordered arrangement of the
magnetic spins, which can be described by a distribution of spin
configurations rather than a well-defined pattern. Since frustration leads to
many local minima in their free energy landscapes, making it difficult to
choose any configuration due to their equiprobable nature. In contrast to this
approach, we investigate the existence of spin glasses in distinct quantum
superposition states of possible electronic configurations without needing any
ensemble of spin configurations. As a result, it can be thought that spin
glasses become frozen in any of these configurations. We directly measured the
local magnetizations of the spins and the Edwards-Anderson SG order parameter
to describe the corresponding magnetic phases, which include all-to-all
interactions and randomly distributed antiferromagnetic (AFM) impurities. The
paper is organized in Section II we introduce our model and describe the
procedure for identifying the superposition states that contributing to the SG
phase. We also expand our results to well-known magnetic orders (disorder) and
classify these superposition states (SSs) concerning their phase
contributions, such as paramagnetic (PM), ferromagnetic (FM), and
antiferromagnetic magnetic phases in Section III. Once we identify the phase-
based superposition states, we discuss the role of entanglement and the
relationship between the SG-order parameter and entanglement in Section IV.
Finally, we conclude the paper in Section V with an outlook of our results and
the impact on future theoretical investigations and experimental
implementations of current quantum technologies.

##  II Model

We consider $N$ Ising spins interacting through infinite-ranged exchange
interaction with the Hamiltonian,

$H=-\Sigma_{(i,j)}J_{ij}\sigma_{i}^{z}\sigma_{j}^{z}.$ (1)

Here $\sigma_{i}^{z}$ is Pauli z-matrices with $i,j=1,\dots,N$ and the
interaction couplings are quenched variables governed by a Gaussian
distribution with a variance $J^{2}/N$ and zero mean $<J_{ij}>=0$,
$P(J_{ij})\propto\exp{\frac{1}{2}(\frac{NJ_{ij}^{2}}{J^{2}}))}$. The randomly
distributed antiferromagnetic interaction is the source of frustration in case
the system’s Hamiltonian can not be minimized, at least for one spin or bound.
Although there is no direct analogy between the geometric frustration in
classical systems and its quantum counterpart, it has been defined in quantum
systems related to entanglement and coherence effects [18]. In this study, we
will concentrate mainly on $N$-atom system with all-to-all interactions. Since
each spin has two states, these Ising spin systems exhibit an exponentially
large phase space of $2^{N}$ configurations.

We started from the simplest model with interacting three-qubit system may
have frustration, see Figure 1. In the classical case, to see the phase
transition, the system should go to the thermodynamic limit, so it would be
impossible to see the phase transition on three-spin model. In addition, the
thermal or quantum fluctuations drive the system to transition, but we do not
consider the thermal fluctuations in this work.

To inject the quantum effects into the classical version of the Ising model
so-called Edward-Anderson spin-glass Hamiltonian (1), one of the well-known
ways is to add a transverse field. The quantum fluctuations arises from a
competition between the spin-spin interactions and such an applied external
field. In contrast to this approach, the present study assumes that quantum
fluctuations and frustration are introduced into the system via direct
injection of quantum superposition states. Through measurement of
corresponding order parameters, such as the local magnetization of the
$i^{th}$ spin for a given realization $\alpha$, with
$m_{i}^{\alpha}=<\sigma_{i}>_{\alpha}$, we were able to determine the specific
superposition states that contribute to various magnetic phases. The EA spin-
glass order parameter, which corresponds to overlaps of the local
magnetization [19] and is provided in (2), was also utilized in our analysis.

Figure 1: Top panel: The graphical representation of SG-superposition state
for $N=3$ qubits. The interactions (lines) between the qubits (blue spheres)
are illustrated for FM $(J>0)$ and AFM $(J<0)$ couplings are yellow and light
blue edges, respectively. Bottom left: The possible SS is found by matching
the dashed lines. Bottom right: One of the $|\psi_{SG}\rangle$ state
contributes to the SG-order. The numbers below the levels correspond to the
labels of the excited atoms of the state, and dots represent the placement of
the ground-level atoms. The circled numbers next to the levels show the
corresponding computational basis states. In the smaller box, the
corresponding SG-contributed superposition states of the three-spin system
with vanishing magnetization and non-zero SG-order parameters are shown in
green color.

$q_{EA}^{\alpha}=\frac{1}{N}\sum_{i=1}^{N}(m_{i}^{\alpha})^{2}.$ (2)

As we modified these definitions to our SS concept by taking the averages over
our superposition states, the average magnetization is

$m=\frac{1}{N}\sum_{i}^{N}\langle\psi_{suppos.}|\sigma_{i}^{z}|\psi_{suppos.}\rangle,$
(3)

and the spin-glass order parameter includes the overlapping between the
discrete states of the entities of the SS by definition. In this way, we have
found some contributions to SG order from the equally weighted superposition
state in both energy and computational basis with the non-zero $q_{EA}$ and
$m=0$. Besides obtaining the SSs contribute to the SG phase, we obtained the
PM and (anti)ferromagnetic SSs in both vanishing $q_{EA}=0$ and $m=0$, and
both are non-zero cases, respectively. All these different order and disorder
SSs are given in Section III and we explained that explicit classification and
association with their entanglement in Sections IV.

The state of a system consisting of $N$ spins can be considered as a product
state, and the initial state is set to be a superposition of all possible
configurations, $|\psi\rangle=\otimes_{i}^{N}|\rightarrow\rangle$ with
$|\rightarrow\rangle=\frac{1}{\sqrt{2}}(|\uparrow\rangle+|\downarrow\rangle)$,
where $|\uparrow\rangle$ and $|\downarrow\rangle$ are the eigenbasis of the
Pauli-$z$ operator. Each spin has two possible orientations, up or down, in
this representation. However, the superposition states that we have created by
taking the sum of these product states will no longer be product states with
the quantum correlations they contain. While the random disorder interactions
between spins force a fixed orientation to minimize the energy, some of the
spins may remain in the $|\rightarrow\rangle$ state even if there is no
external field due to frustration.

In Figure 1, the antiferromagnetic $(J<0)$ interactions may cause geometric
frustration in the first triangle, as shown by the two-side-aligned arrows
denoting the frustrated spin. The qubit state can be in any superposition of
the form $|\psi\rangle=a_{1}|0\rangle+a_{2}|1\rangle$ as long as
$|a_{1}|^{2}+|a_{2}|^{2}=1$. However, this is not the case for classical
spins. We illustrate such a frustrated configuration state of a three-body
system separated into two states that do not have frustration in the
$\sigma^{z}$ basis:

$\displaystyle|\psi>$
$\displaystyle=|0\rangle\otimes|1\rangle\otimes\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right),$
(4)
$\displaystyle=\frac{1}{\sqrt{2}}\left(|0\rangle\otimes|1\rangle\otimes|0\rangle+|0\rangle\otimes|1\rangle\otimes|1\rangle\right).$

The corresponding phases can be obtained from the relative order parameters.
Therefore, although many different superposition states could be considered
via the energy eigen states or computational basis vectors, we will only
consider the equally weighted two-state superposition in the computational
basis. We will continue with the standard basis of energy-state products from
now on. This standard basis is ${|e\rangle,|g\rangle}$ for one atom,
${|ee\rangle,|eg\rangle,|ge\rangle,|gg\rangle}$ for two, and
${|eee\rangle,|eeg\rangle,|ege\rangle,|gee\rangle,|egg\rangle,|geg\rangle,|gge\rangle,|ggg\rangle}$
for three atoms. Figure 1 shows the three-atom standard basis on the left
bottom. Corresponding positions in the natural basis of the levels are given
in the circles next to levels and the numbers with the green dots below the
levels denotes the placement of the excited atoms and ground state,
respectively.

All our superposition states contributes to the spin-glass order should
satisfy the two simple rules:

  * (i)

The SG-contibuted SSs must have at least one co-excited spin,

  * (ii)

The total number of excited spin labels should not exceed the total number of
spins in the system.

The first rule denotes the overlapping between the states, and the second one
corresponds to the SS should have at least one frustrated spin an equally-
weighted qubit-state such as called cat state denoted by C. Once we address
the excited spins, we can write the spin-glass SSs quickly in each system
size. However, in ferromagnetic (antiferromagnetic) SSs, the number of labels
can be greater than the number of spins in the system. Understandably, the
ferromagnetic order does not have to include any frustrated spin, and all the
spins can be in the same (up or down) direction. It can be classified as that
one excited and a set of cat states {C,C,…} pair will contribute to the FM/AFM
orders. To fix a spin on a state can be thought of as making a local
measurement on it, and this causes a loss of quantumness. We examined this
loss in terms of negativity, a measure of quantum entanglement defined as
[20],

$\mathcal{N}=\frac{\lVert\rho^{\mathrm{T}}\rVert_{1}-1}{2}.$ (5)

Here, the trace norm of the quantum state
$\rho=|\psi_{suppos}\rangle\langle\psi_{suppos}|$ is denoted by
$\lVert\rho^{\mathrm{T}}\rVert_{1}$. The detailed about negativity
calculations and results are explained in Section IV.

##  III Quantum Superposition States for Magnetic Orders and Disorder

The magnetic phases of interest can be classified in terms of magnetization
and the EA spin-glass order parameter, $q_{EA}$ [19].

(a) Order parameters for equally weighted SSs.

(b) Order parameter for all superposition states.

Figure 2: (Color online.) The magnetization vs. EA spin-glass order parameter,
$q_{EA}$, is shown for (a) all equally-weighted superposition states in
different sizes $N=3,4,5,6,7,$ and $8$. The red horizontal line indicates
$q_{EA}\neq 0$ with $m=0$, corresponds to the spin-glass regime, (b) not only
the equally weighted SSs but also expanded superposition states at $N=3$. We
obtained expanded superposition states by giving different weights to
superposed ones. In both figures, the paramagnetic phase is observed at the
point $m=0$ and $q_{EA}=0$. These findings provide valuable insights into the
nature of quantum SSs and their relevance to SG and quantum magnets.

All corresponding magnetization and $q_{EA}$ parameter values of the equally
weighted and expanded superposition state spaces are displayed in Figure 2(a)
and Figure 2(b), respectively. The parameter values of equally weighted
superposition states, a special case of the expanded ones, are obtained at
N=3,4,5,6 system sizes.

Figure 3: (Color online.) Schematic representation of SSs contributes to
(a)SG, (b)FM, (c)AFM and (d)PM phases. Arrows depict the equally weighted
summation of the states. This figure provides a clear and comprehensive
visualization of the various superposition states and their relation to spin
glasses, quantum magnets, and quantum superposition states.

The triangular parameter domain can be seen in all cases; moreover, the
maximum value of the $q_{EA}$ remains the same. In each system size, it is
possible to see all the magnetic phases in interest.

In both figures, having various numbers of $m$ values against the same
$q_{EA}$ value indicates spontaneous symmetry breaking [21]. While this
symmetry breaking signifies the FM (AFM) order, the PM phase corresponds to
the point of $m=0$ and $q_{EA}=0$. The red-dashed line starts with the PM
regime, and along the line, we can obtain the SSs corresponding to the SG
regime. For simplicity, we will continue with the particular case of these SS
space, such as equally weighted superposition states. However, even if the
system size enlarges and extra SSs arise, the triangular structure of the
diagram remains the same. In other words, the symmetry breaking can be
observed for $N\to\infty$ in terms of the different $q_{EA}$ values.

Let’s return to the SSs that are equally weighted. Figure 3 shows how binary
superpositions in a system of dimension $N=3$ correspond to different quantum
magnets, including SG, FM, AFM, and PM-phases. As shown in Figure 4(a), we
have derived the matrix representation of the binary states that contribute
exclusively to the SG phase in systems comprising $N=3,4,5,$ and $6$ atoms. In
order to maintain clarity, we have elected to exclusively represent the SG-
SSs, omitting the explicit depiction of the superposition states that would
pertain to other magnetic phases. However, it is pertinent to note that the
off-diagonal elements do indeed play a role in the PM phase, as they are
composed of non-overlapping product spin states. Furthermore, the upper and
lower triangular regions of the non-diagonal elements in the matrix are
associated with the FM or AFM phase, depending on the specific binary
superpositions involved. Consequently, this superposition matrix can be
regarded as an evenly distributed superposition state space that pertains to
the configuration space. The matrix is divided into distinct quantum magnetic
phases, thereby serving as a phase diagram. Additionally, we have noted that
the phase partition pattern remains consistent and scalable even as the system
size is expanded.

(a) The non-zero SG order parameter $q_{EA}$ of equally weighted SSs.

(b) First line: The Entanglement of equally weighted SSs contribute to SG
order. Second line: Entanglement of all magnetic orders.

Figure 4: (Color online.) (a) The matrix representation of all spin-glass
order contributed equally-weighted superposition states is given for
$N=3,4,5$, and $6$ spins from left to right with non-zero Edward-Anderson
order parameter and zero magnetization. As the system size increases, the
number of distinct values of $q_{EA}$ increases, indicating a signal of
replica symmetry breaking. The various colors denote different values of
$q_{EA}$ (or $\mathcal{N}$), and this pattern repeats itself in subsequent
generations from left to right. Diagonal elements correspond to the single
states and they are equal to $q_{EA}=0.25$ fixed value. However, they
contribution to spin-glass or FM/AFM order may alter by the system size. One
another fixed part of the matrix representation is off diagonal elements have
only $q_{EA}=0$ values and they contributes to the PM order for all system
sizes. (b) The same pattern of $q_{EA}$ can be obtained for average negativity
$\mathcal{N}$ with different numerical values. It should be noted that there
is a reciprocal relationship between the $\mathcal{N}$ average negativity and
the $q_{EA}$ order parameter.

The differentiation of the $q_{EA}$ order parameter at each even value of
system size, $N$, can be associated with replica symmetry breaking in spin-
glass systems [13]. For example, while there is a unique $q_{EA}$ value for
$N=3$, sizes $N=4$ and $N=5$ have two different values of $q_{EA}$. Figure 4
illustrates a recursive pattern, wherein taking a partial trace over the most
recently added qubit leads the system state space to the previous state space.
Co-excited atoms in SSs can also be defined as overlapping between two states.
This overlap scales with the system size, similar to the differentiation of
$q_{EA}$. The number of possible overlapped atoms increases with each even
number of $N$. However, unlike the SG-SSs, the PM-phase SSs have neither co-
excited spins nor any overlap. All PM-phase SSs are maximally entangled,
similar to Greenberger-Horne-Zeilinger (GHZ) states [22]. We illustrated that
entanglement of spin-glass SSs in the first line of the Figure 4(b) and
entanglement of SSs corresponds to the other magnetic phases in the second
line of the Figure 4(b), respectively.

##  IV The New Entanglement Witness of the Magnetic Structures

The presence or absence of overlap between states in their superposed states
corresponds to the ordered/disordered states of the system. Moreover, the
overlapping superposition states can exhibit different magnetic orders, such
as spin-glass, ferromagnetic, and antiferromagnetic orders. Firstly, after
defining the order/disorder distinction based on the presence or absence of
overlap, we observe that paramagnetic (disordered) systems corresponding zero
overlaps also possess maximum entanglement. From this perspective, we
calculated the entanglement of the superposition states using logarithmic
negativity to define the relationship between the amount of overlap and
entanglement. Considering that the Edward-Anderson spin glass order parameter
measures the degree of overlap between two different system configurations
(superposed states), we investigated the direct relationship between
negativity $\mathcal{N}$ and $q_{EA}$ order parameter. The numerical results
illustrate the relationship between these two quantities, as shown in Figure
5. We obtained that the order parameter $q_{EA}$ decreases linearly with
$\mathcal{N}$,

$q_{EA}=q_{max}-\frac{1}{4}\mathcal{N}.$ (6)

Here $q_{max}=1$ is the maximum value of the normalized EA spin-glass order
parameter. According to the figure, the state starts from the fully entangled
state (PM state) with $\mathcal{N}=1$ and $q_{EA}=0$. Then, its maximal-
entangled portion becomes smaller and smaller until it reaches the separable
state with $\mathcal{N}=0$ and $q_{EA}=q_{max}=0.25$. Each distinct $q_{EA}$
value corresponds to a different entangled cluster size. We separated regions
corresponding to $m$-partite entanglement with $m=N,N-1,\dots,1$ by dashed
lines. However, as the system size approaches infinity ($N\to\infty$), the
classification mentioned above is no longer discernible, and the different
$q_{EA}$ values on the fitting line be indistinguishable. This is due to the
loss of quantumness in the system, as it becomes classical and the separations
between distinct $q_{EA}$ values vanish.

In this analysis, we present both numerical results and a discussion of
superposition states, including the multi-partite entangled component,
concerning the recursive growing pattern of the sg-order parameter $q_{EA}$
and negativity $\mathcal{N}$, illustrated in Figure 4. Specifically, we
consider a three-particle system where each particle can exist in one of the
three configurations from the set
$E_{N=3}(SG)=\\{\textbf{C},\textbf{e},\textbf{g}\\}$, where $E_{N=3}(SG)$
denotes the ensemble including the probable spin configurations. We identify
six possible configuration states for the SG contribution with vanishing
magnetization and non-zero $q_{EA}$.

Suppose one more qubit is added to the system. The system state has two
possible configuration ensembles:

$E_{N=4}(SG)\\\
=\begin{cases}\\{\textbf{C},\textbf{C},\textbf{e},\textbf{g}\\},&q_{EA}=0.125,\\\
\\{\textbf{e},\textbf{g},\textbf{e},\textbf{g}\\},&q_{EA}=0.25.\end{cases}$
(7)

which correspond to SG-contributed superposition.

Figure 5: (Color online.) The left panel shows the variation of the negativity
with the Edward-Anderson spin-glass order parameter $q_{EA}$ for particle
systems with $N=4,5,6,7$, and $8$. The distinct regions in the plot correspond
to different values of $q_{EA}$ that indicate the extent of particle
entanglement. Initially, all systems are fully entangled with $\mathcal{N}=1$,
and as $q_{EA}$ decreases, the number of entangled particles decreases,
ultimately leading to a separable state with $\mathcal{N}=0$. In the right
panel, the phase-contributed superposition states are classified based on the
number of entangled particles in the $N$-particle system.

In this case, we observe two distinct values of $q_{EA}$ corresponding to the
two different configuration sets. The permutation group of the first set
yields 24 different SSs that have $q_{EA}=0.125$, while the second set yields
six SSs with $q_{EA}=0.25$ appropriate to Figure 4. As we increase the system
size to $N=5$ spins, the number of possible sets remains the same as for
$N=4$, and we observe two additional sets, namely
$\\{\textbf{C},\textbf{C},\textbf{C},\textbf{e},\textbf{g}\\}$ and
$\\{\textbf{C},\textbf{e},\textbf{g},\textbf{e},\textbf{g}\\}$.

Notably, the $q_{EA}$ parameter differs between distinct sets and within a
set, depending on the number of entangled particles in a superposition state.
For instance, the set
$\\{\textbf{C},\textbf{C},\textbf{C},\textbf{e},\textbf{g}\\}$ can be
considered as

$\\{\textbf{C},\textbf{C},\textbf{C},\textbf{e},\textbf{g}\\}\\\
=\begin{cases}\\{|GHZ\rangle_{3},\textbf{e},\textbf{g}\\}\\\
\\{|GHZ\rangle_{2},\textbf{C},\textbf{e},\textbf{g}\\},\end{cases}$ (8)

here, the sub set $|GHZ\rangle_{3}:\\{\textbf{C},\textbf{C},\textbf{C}\\}$ and
$|GHZ\rangle_{2}:\\{\textbf{C},\textbf{C}\\}$ gives the maximally entangled
(GHZ) states, and the subscript denotes the number of entangled particles. In
general definition, $n$-particle GHZ state can be written as

$|GHZ\rangle_{n}=\alpha(|g\rangle^{\otimes n}+|e\rangle^{\otimes n}),$ (9)

where $\alpha$ is a constant [22, 23], the source of these maximally entangled
states is related to the number of cat state $C$ in the permutation sets.

If the possible configuration sets lack cat state C, the resulting state will
be deemed separable. The superposition state may also be partially entangled,
in which the number of cat states is less than $N-1$. Defining the entangled
portion of the state, particularly for larger systems, presents a challenge.
While our focus centers on SG superposition states, analogous conditions arise
in FM and AFM cases.

We developed a metric to quantify the entanglement partition of a state in
terms of the spin-glass order parameter, $q_{EA}$, which allowed us to achieve
our objective. Figure 5 illustrates the entanglement partitions for various
system sizes, along with the corresponding inverse linear relationship between
the negativity and $q_{EA}$. As $q_{EA}$ decreases from its maximum value
corresponding to separable states, the number of entangled particles increases
until the system reaches a state of maximum entanglement.

Based on the presence of entangled particle ensembles, Figure 5 provides a
classification of magnetic phases.

##  V Conclusions

This research demonstrates that spin glasses can exist in equiprobable
superposition states of potential electronic configurations in a quantum
framework. We propose using cat states to define frustrated spins and link the
frustration to quantum interference. By employing the Edward-Anderson spin-
glass order parameter and magnetization, we classify the superposition states
based on their contribution to distinguishing magnetic order (or disorder) in
various phases, such as SG, (anti)FM, and PM. Our results provide valuable
insights into the nature of spin glasses in quantum systems and have
implications for developing quantum technologies such as quantum cryptography
[24], quantum simulation [25, 26, 27], quantum computation [28, 29, 30, 31],
quantum sensing [32] and metrology [33].

We establish a direct correlation between the Edward-Anderson spin glass order
parameter, $q_{EA}$, and a measure of entanglement, negativity represented by
$\mathcal{N}$. We demonstrate that the spin glass order parameter can also
function as an indicator of entanglement, while conversely, the negativity of
entanglement can serve as the order parameter to distinguish between phases of
order and disorder, specifically the ferromagnetic (FM) and paramagnetic (PM)
phases. This result is due to the fact that entanglement is the ability of
qubits to correlate their state with other qubits. Quantum phase transitions
(QPTs) are an established finding in condensed matter physics, characterized
by significant changes in the ground state properties of a quantum system
induced by small variations in an external parameter. For example, QPTs can be
induced in spin systems by variations in the magnetic field [34, 35], while in
cold atom simulators of Hubbard-like models, changes in the intensity of a
laser beam can trigger QPTs [14]. While our study does not address QPTs
directly, several methods for driving quantum states to a target state have
been studied extensively in the literature. These include quantum
entanglement, state transfer [36, 37, 38, 39, 40, 41], and quantum adiabatic
evolution [42, 43]. Once we obtain the corresponding quantum states to the
different quantum phases, phase transition can be studied in this
contextuality.

This study reveals that the structural similarities between entanglement and
spin glass order parameter persist across systems of varying sizes, as
indicated by the consistent patterns shown in Figure 4. Furthermore, our study
highlights the potential use of superposition states in defining magnetic
order (disorder) [33] in condensed matter physics, which has broader
implications for quantum information processing and quantum computing [28, 29,
30, 31]. These findings offer new insights into the nature of quantum
superposition states and their relevance to spin glasses and quantum magnets.
The categorization of states according to their magnetic properties, utilizing
physical order parameters and entanglement, is a critical prerequisite for the
effective manipulation of entangled states that are necessary for quantum
information processing and transfer via qubits [44]. We offer that these
superposition states are candidates to be new phase-based-bits in usage of the
quantum computing [23, 45]. We are currently investigating their possible use
in other physical systems.

## Acknowledgements

The authors would like to acknowledge the financial support from the
Scientific and Technological Research Council of Türkiye (TÜBİTAK), grant No.
120F100. We would also like to express our gratitude to Ö. E. Müstecaplıoğlu
and M. Paternostro for their insightful discussions.

## References

  * Fischer and Hertz [1991] K. H. Fischer and J. A. Hertz,  _Spin Glasses_, Cambridge Studies in Magnetism (Cambridge University Press, 1991).
  * Mydosh [1993] J. A. Mydosh,  _Spin Glasses: An Experimental Introduction (1st ed.)_ (CRC Press., 1993).
  * Nishimori [2001] H. Nishimori,  _Statistical Physics of Spin Glasses and Information Processing: an Introduction_ (Oxford University Press, 2001).
  * Vannimenus and Toulouse [1977] J. Vannimenus and G. Toulouse, Theory of the frustration effect. ii. ising spins on a square lattice, Journal of Physics C: Solid State Physics 10, L537 (1977).
  * Harary [1970] F. Harary,  _Graph Theory and Its Applications._ , 1st ed. (Academic Press, 1970).
  * Binder and Young [1986] K. Binder and A. P. Young, Spin glasses: Experimental facts, theoretical concepts, and open questions, Rev. Mod. Phys. 58, 801 (1986).
  * Giampaolo  _et al._ [2011] S. M. Giampaolo, G. Gualdi, A. Monras, and F. Illuminati, Characterizing and quantifying frustration in quantum many-body systems., Physical Review Letters 107, 10.1103/PHYSREVLETT.107.260602. (2011).
  * Wolf  _et al._ [2003] M. M. Wolf, F. Verstraete, and J. I. Cirac, Entanglement and frustration in ordered systems, International Journal of Quantum Information 01, 465 (2003).
  * Dawson and Nielsen [2004] C. M. Dawson and M. A. Nielsen, Frustration, interaction strength, and ground-state entanglement in complex quantum systems, Physical Review A 69, 052316 (2004).
  * Giampaolo  _et al._ [2010] S. M. Giampaolo, G. Adesso, and F. Illuminati, Probing quantum frustrated systems via factorization of the ground state, Phys. Rev. Lett. 104, 207202 (2010).
  * de Beaudrap  _et al._ [2010] N. de Beaudrap, M. Ohliger, T. J. Osborne, and J. Eisert, Solving frustration-free spin systems, Phys. Rev. Lett. 105, 060504 (2010).
  * Adhikari  _et al._ [2009] S. Adhikari, B. Chakraborty, A. S. Majumdar, and S. Vaidya, Quantum entanglement in a noncommutative system, Phys. Rev. A 79, 042109 (2009).
  * Mezard  _et al._ [1986] M. Mezard, G. Parisi, and M. Virasoro,  _Spin Glass Theory and Beyond_, 2nd ed. (WORLD SCIENTIFIC, 1986) https://www.worldscientific.com/doi/pdf/10.1142/0271 .
  * Sen  _et al._ [2008] A. S. U. Sen, J. Dziarmaga, A. Sanpera, and M. Lewenstein, Frustration, area law, and interference in quantum spin models, Phys. Rev. Lett. 101, 10.1103/PhysRevLett.101.187202 (2008).
  * Razavy [2003] M. Razavy,  _Quantum theory of tunneling_ (River Edge, NJ ; Singapore : World Scientific, 2003).
  * Anderson [1958] P. W. Anderson, Absence of diffusion in certain random lattices, Phys. Rev. 109, 1492 (1958).
  * Moro  _et al._ [2018] G. J. Moro, G. Dall’Osto, and B. Fresch, Signatures of anderson localization and delocalized random quantum states, Chemical Physics 514, 141 (2018), energy and Entropy of Change: From Elementary Processes to Biology.
  * Marzolino  _et al._ [2013] U. Marzolino, S. M. Giampaolo, and F. Illuminati, Frustration, entanglement, and correlations in quantum many-body systems, Physical Review A 88 (2013).
  * Edwards and Anderson [1975] S. F. Edwards and P. W. Anderson, The order parameter in a spin glass, Journal of Physics F: Metal Physics 5, 965 (1975).
  * Vidal and Werner [2002] G. Vidal and R. F. Werner, Computable measure of entanglement, Phys. Rev. A 65, 032314 (2002).
  * Arodz  _et al._ [2003] H. Arodz, J. Dziarmaga, and W. H. Zurek, eds.,  _Patterns of Symmetry Breaking_ , 1568-2609 No. 1 (Springer Dordrecht, 2003).
  * Greenberger  _et al._ [1990] D. M. Greenberger, M. A. Horne, A. Shimony, and A. Zeilinger, Bell’s theorem without inequalities, American Journal of Physics 58, 10.1119/1.16243 (1990).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information. 10Th anniversary ed._, Cambridge Studies in Magnetism (Cambridge University Press, 2010).
  * Pirandola  _et al._ [2020] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J. L. Pereira, M. Razavi, J. S. Shaari, M. Tomamichel, V. C. Usenko, G. Vallone, P. Villoresi, and P. Wallden, Advances in quantum cryptography, Adv. Opt. Photon. 12, 1012 (2020).
  * Georgescu  _et al._ [2014] I. M. Georgescu, S. Ashhab, and F. Nori, Quantum simulation, Reviews of Modern Physics 86, 153 (2014).
  * Daley  _et al._ [2022] A. J. Daley, I. Bloch, C. Kokail, S. Flannigan, N. Pearson, M. Troyer, and P. Zoller, Practical quantum advantage in quantum simulation, Nature 607, 667 (2022).
  * Brown  _et al._ [2010] K. L. Brown, W. J. Munro, and V. M. Kendon, Using quantum computers for quantum simulation, Entropy 12, 2268 (2010).
  * Bennett and DiVincenzo [2000] C. Bennett and D. DiVincenzo, Quantum information and computation., Nature 404, 247 (2000).
  * Valiev [2005] K. A. Valiev, Quantum computers and quantum computations, Physics-Uspekhi 48, 10.1070/PU2005v048n01ABEH002024 (2005).
  * K. Kim  _et al._ [2010] M.-S. C. K. Kim, S. Korenblit, R. Islam, E. E. Edwards, J. K. Freericks, G.-D. Lin, L.-M. Duan, and C. Monroe, Quantum simulation of frustrated ising spins with trapped ions, Nature 465, 10.1038/nature09071 (2010).
  * Normand and Oleś [2008] B. Normand and A. M. Oleś, Frustration and entanglement in the ${t}_{2g}$ spin-orbital model on a triangular lattice: Valence-bond and generalized liquid states, Phys. Rev. B 78, 094427 (2008).
  * Degen  _et al._ [2017] C. L. Degen, F. Reinhard, and P. Cappellaro, Quantum sensing, Rev. Mod. Phys. 89, 035002 (2017).
  * Friedenauer  _et al._ [2008] A. Friedenauer, H. Schmitz, J. T. Glueckert, D. Porras, and T. Schaetz, Simulating a quantum magnet with trapped-ions, Nature Physics 4, 757–761 (2008).
  * Sachdev [2011] S. Sachdev,  _Quantum Phase Transitions_ , 2nd ed., Cambridge Studies in Magnetism:Second Edition (Cambridge University Press, 2011).
  * Rams and Damski [2012] M. Rams, M.and Zwolak and B. Damski, A quantum phase transition in a quantum external field: Superposing two magnetic phases., Sci Rep 2 (2012).
  * Miková  _et al._ [2016] M. Miková, I. Straka, M. Mičuda, V. Krcmarsky, M. Dušek, M. Jezek, J. Fiurásek, and R. Filip, Faithful conditional quantum state transfer between weakly coupled qubits, Scientific Reports 6, 32125 (2016).
  * Hammerer  _et al._ [2010] K. Hammerer, A. S. Sørensen, and E. S. Polzik, Quantum interface between light and atomic ensembles., Rev. Mod. Phys. 82 (2010).
  * Daniilidis and Häffner [2013] N. Daniilidis and H. Häffner, Quantum interface between light and atomic ensembles., Annu. Rev. Condens. Matter Phys. 4, 83 (2013).
  * Majer [2007] J. e. a. Majer, Coupling superconducting qubits via a cavity bus., Nature 449, 443–447 (2007).
  * Reiserer  _et al._ [2014] A. Reiserer, N. Kalb, G. Rempe, and S. Ritter, A quantum gate between a flying optical photon and a single trapped atom., Nature 508, 237–240 (2014).
  * Matsukevich and Kuzmich [2004] D. N. Matsukevich and A. Kuzmich, Quantum state transfer between matter and light., Science 306, 663 (2004).
  * Joye and Pfister [1994] A. Joye and C.-E. Pfister, Quantum adiabatic evolution, in  _On Three Levels: Micro-, Meso-, and Macro-Approaches in Physics_, edited by M. Fannes, C. Maes, and A. Verbeure (Springer US, Boston, MA, 1994) pp. 139–148.
  * Kandel  _et al._ [2021] Y. P. Kandel, H. Qiao, S. Fallahi, G. C. Gardner, M. J. Manfra, and J. M. Nichol, Quantum state transfer between matter and light., Nat. Commun. 12, 10.1038/s41467-021-22416-5 (2021).
  * Bennett  _et al._ [1993] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels, Phys. Rev. Lett. 70, 1895 (1993).
  * Feynman [1982] R. P. Feynman, Simulating physics with computers., International Journal of Theoretical Physics 21, 467 (1982).