# Hyperbolic motions in the $N$-body problem with homogeneous potentials

Guowei Yu  Chern Institute of Mathematics and LPMC, Nankai University,
Tianjin, China<EMAIL_ADDRESS>
###### Abstract.

In the $N$-body problem, a motion is called hyperbolic, when the mutual
distances between the bodies go to infinity with non-zero limiting velocities
as time goes to infinity. For Newtonian potential, in [9] Maderna and
Venturelli proved that starting from any initial position there is a
hyperbolic motion with any prescribed limiting velocities at infinity.

Recently based on a different approach, Liu, Yan and Zhou [7] generalized this
result to a larger class of $N$-body problem. As the proof in [7] is quite
long and technical, we give a simplified proof for homogeneous potentials
following the approach given in the latter paper.

This work is supported by the National Key R&D Program of China
(2020YFA0713303), NSFC (No. 12171253), the Fundamental Research Funds for the
Central Universities and Nankai Zhide Fundation.

##  1\. Introduction

Consider the $N$-body problem in $\mathbb{R}^{d}$ ($d\geq 2$) with
$\alpha$-homogeneous potential as below

(1) $U(q)=\sum_{1\leq i<j\leq
N}\frac{m_{i}m_{j}}{|q_{i}-q_{j}|^{\alpha}},\;\;\alpha\in(0,2).$

With $m_{i}$ and $q_{i}$ representing the mass and position of the $i$-th
body, motion of the bodies can be described by the following equation

(2) $m_{i}\ddot{q}_{i}=-\alpha\sum_{j=1,j\neq
i}^{N}\frac{m_{i}m_{j}(q_{i}-q_{j})}{|q_{i}-q_{j}|^{\alpha+2}},\;\;i=1,\dots,N.$

When $\alpha=1$, it is the Newtonian $N$-body problem.

Define the mass weighted inner product and norm on the configuration space
$\mathbb{E}=\mathbb{R}^{dN}$ as

$\ll x,y\gg=\sum_{i=1}^{N}m_{i}\langle x_{i},y_{i}\rangle,\;\|x\|=\sqrt{\ll
x,x\gg}.$

$\mathbb{S}=\\{x\in\mathbb{E}:\;\|x\|=1\\}$ represents the set of normalized
configurations.

Since the potential function $U$ is not well-define on the collision set

(3) $\Delta=\\{q\in\mathbb{E}:\;q_{i}=q_{j}\text{ for some }1\leq i\neq j\leq
N\\}.$

Given an initial condition, the corresponding solution of (2) may not exist
after a finite time. However it is believed (see [10] and [6]), these initial
conditions should form a set with measure zero in the phase space. Now a
fundamental question is what are the possible final motions of the bodies as
time goes to infinity. This was first studied by Chazy in [1]. Among all
possible final motions, one is called _hyperbolic_ , which can be defined as
below according to Chazy.

######  Definition 1.1.

A solution $q(t)$, $t\in[t_{0},\infty)$, of (2) is a hyperbolic motion, if
there is a limiting velocity
$\xi\in\hat{\mathbb{E}}=\mathbb{E}\setminus\Delta$ as $t\to\infty$, i.e.,

(4) $\lim_{t\to\infty}\dot{q}(t)=\xi\text{ or }q(t)=\xi t+o(t),\;\text{ as
}t\to\infty.$

Recall that energy $E(q(t))$ is conserved along a solution

(5) $E(q(t))=\frac{1}{2}\|\dot{q}(t)\|^{2}-U(q(t)).$

If $h$ is the energy of a hyperbolic motion $q(t)$, then it must be positive,
as

$h=\lim_{t\to\infty}E(q(t))=\lim_{t\to\infty}\left(\frac{1}{2}\|\dot{q}(t)\|^{2}-U(q(t)\right)=\frac{1}{2}\|\xi\|^{2}>0.$

Then we can rewrite the asymptotic expression in (4) as below, if
$v=\xi/\sqrt{2h}\in\hat{\mathbb{S}}=\mathbb{S}\setminus\Delta$,

(6) $q(t)=\sqrt{2h}vt+o(t),\;\text{ as }t\to\infty.$

This means $v$ is also the limiting shape of the normalized configuration of
$q(t)$, as

$\lim_{t\to\infty}q(t)/\|q(t)\|=v.$

For the Newtonian $N$-body problem, in [9] Maderna and Venturilli showed that
starting from any initial configuration, there are hyperbolic motions with any
asymptotic limiting velocities from $\hat{\mathbb{E}}$ at infinity, as stated
in Theorem 1.1. The motions were found as free-time minimizers based on the
weak KAM theory. A crucial part of the proof is to establish the asymptotic
expression (6). In [9], this was done indirectly using the continuous property
of the limiting shape of hyperbolic motions at infinity, which were given by
Chazy.

Recently in [7], Liu, Yan and Zhou gave a different proof of this result. In
particular, they found a way to show the asymptotic expression directly.
Moreover their approach works for a much larger class of $N$-body problem, as
long as $U(q)$ satisfies certain conditions (including the
$\alpha$-homogeneous potential), for the details see [7, Theorem 1.4 ]. To
obtained such a general result, the details in [7] are quite long and
technical.

Since the $\alpha$-homogeneous potential is most interesting to us and using
the Lagrange-Jacobi identity (Lemma 2.5), one can significantly simplify the
proof in Section 5 of [7] (see Lemma 2.8). We feel it is worth to write down
this short note. However it must be emphasized that the main idea of our proof
is from [7].

######  Theorem 1.1.

Given arbitrarily a positive energy $h$ and asymptotic configuration
$v\in\hat{\mathbb{S}}$. For any $x\in\mathbb{E}$, there is a hyperbolic motion
$\gamma:[t_{0},\infty)\to\mathbb{E}$, which is collision-free of (2) for all
$t\neq 0$ and satisfies

$\gamma(t_{0})=x,\;\;\gamma(t)=\sqrt{2h}tv+o(t),\;\text{ as }t\to\infty.$

In a recently preprint by Polimeni and Terracini [4], another approach to
prove the above theorem when $\alpha=1$ was given. Their idea is to look for
minimizer of a normalized Lagrangian action with the desired asymptotic
behavior. The advantage of such an approach is it can also be used to prove a
similar result for hyperbolic-parabolic motion.

##  2\. Preliminary

For any $x,y\in\mathbb{E}$ and $T>0$, let $\mathcal{C}(x,y;T)$ denote the set
of absolute continuous paths defined on $[0,T]$, which go from $x$ to $y$, and
$\mathcal{C}(x,y)=\cup_{T>0}\mathcal{C}(x,y;T)$. For any
$\gamma\in\mathcal{C}(x,y;T)$, we define its length and $h$-modified
Lagrangian action value as

(7) $\ell(\gamma|_{[0,T]})=\int_{0}^{T}\|\dot{\gamma}\|\,dt\;\text{ and
}\;\mathcal{A}_{h}(\gamma;0,T)=\int_{0}^{T}\left(\frac{1}{2}\|\dot{\gamma}\|^{2}+U(\gamma)+h\right)\,dt.$

######  Lemma 2.1.

For any $\gamma\in\mathcal{C}(x,y;T)$,
$\|y-x\|\leq\ell(\gamma|_{[0,T]})\leq\frac{1}{\sqrt{2h}}\mathcal{A}_{h}(\gamma;0,T)$.

###### Proof.

While the first inequality is obvious, the second one follows from

$\mathcal{A}_{h}(\gamma;0,T)\geq\int_{0}^{T}\left(\frac{1}{2}\|\dot{\gamma}\|^{2}+h\right)\,dt\geq\sqrt{2h}\int_{0}^{T}\|\dot{\gamma}\|\,dt.$

∎

######  Definition 2.1.

We say $\gamma\in\mathcal{C}(x,y;T)$ is a minimizer, if
$\mathcal{A}_{h}(\gamma;0,T)=\phi_{h}(x,y;T)$, and an $h$-free-time minimizer,
if $\mathcal{A}_{h}(\gamma;0,T)=\phi_{h}(x,y)$, where

$\phi_{h}(x,y;T)=\inf\\{\mathcal{A}_{h}(\gamma;0,T):\;\gamma\in\mathcal{C}(x,y;T);$
$\phi_{h}(x,y)=\inf\\{\phi_{h}(x,y;T):\;T>0\\}.$

######  Proposition 2.1.

If $\gamma\in\mathcal{C}(x,y;T)$ is a minimizer, $\gamma|_{(0,T)}$ is a
collision-free solution of (2).

######  Remark 2.1.

This is the well-known _Machal’s Lemma_. A proof can be found in [2] for
$\alpha=1$ and in [5] for $\alpha\in(0,2)$. Notice that $\gamma(0)$ or
$\gamma(T)$ may contain collision, if we choose $x$ or $y\in\Delta$.

######  Lemma 2.2.

When $h>0$ and $x\neq y\in\mathbb{E}$, the following properties hold.

  1. (a).

There exists a $\gamma\in\mathcal{C}(x,y;T)$ satisfying
$\mathcal{A}_{h}(\gamma;0,T)=\phi_{h}(x,y)$.

  2. (b).

$\gamma|_{(0,T)}$ is collision-free solution of (2) with energy
$E(\gamma(t))\equiv h$.

  3. (c).

For any $z\in\mathbb{E}$, $\phi_{h}(x,y)\leq\phi_{h}(x,z)+\phi_{h}(z,y)$.

###### Proof.

(a). By a standard argument in the direct method of calculus of variation,
there exists a $\gamma_{\tau}\in\mathcal{C}(x,y;\tau)$ for some $\tau>0$, such
that $\mathcal{A}(\gamma_{\tau};0,\tau)=\phi_{h}(x,y;\tau)$. The Cauchy-
Schwartz inequality then implies

$\ell(\gamma_{\tau}|_{[0,\tau]})=\int_{0}^{\tau}\|\dot{\gamma}_{\tau}\|\,dt\leq\sqrt{\tau}\left(\int_{0}^{\tau}\|\dot{\gamma}_{\tau}\|^{2}\,dt\right)^{\frac{1}{2}}.$

As $x\neq y$, if $\tau\to 0$,

$\phi_{h}(x,y;\tau)\geq\frac{1}{2}\int_{0}^{\tau}\|\dot{\gamma}_{\tau}\|^{2}\,dt\geq\frac{1}{2\tau}\left(\ell(\gamma_{\tau}|_{[0,\tau]})\right)^{2}\geq\frac{\|x-y\|^{2}}{2\tau}\to\infty.$

Meanwhile $\phi_{h}(x,y;\tau)\geq h\tau\to\infty$, when $\tau\to\infty$.

As a result, there must exist a $T>0$ and $\gamma\in\mathcal{C}(x,y;T)$
satisfying

$\mathcal{A}_{h}(\gamma;0,T)=\phi_{h}(x,y;T)=\inf_{\tau>0}\phi_{h}(x,y;\tau)=\phi_{h}(x,y).$

(b). By Proposition 2.1, $\gamma|_{(0,T)}$ is a collision-free solution. Since
$\gamma$ is an $h$-free-time minimizer, it is well-known its energy must be
$h$. For a detailed proof see [3, 3.3].

(c). The result is trivial, when $z=x$, $\phi_{h}(x,x)=0$. The same argument
holds for $z=y$.

When $z\neq x$ and $z\neq y$, there exist $\gamma_{x}\in\mathcal{C}(x,z)$ and
$\gamma_{y}\in\mathcal{C}(z,y)$ satisfying

$\int L(\gamma_{x},\dot{\gamma}_{x})+h\,dt=\phi_{h}(x,z),\;\;\int
L(\gamma_{y},\dot{\gamma}_{y})+h\,dt=\phi_{h}(z,y).$

As the concatenation of $\gamma_{x}$ and $\gamma_{y}$ belongs to
$\mathcal{C}(x,y)$, we have

$\phi_{h}(x,y)\leq\phi_{h}(x,z)+\phi_{h}(z,y).$

∎

######  Lemma 2.3.

There are two positive constants $\beta_{1}$ and $\beta_{2}$, such that for
any $x,y\in\mathbb{E}$ and $h>0$,

$\phi_{h}(x,y)\leq\left(\beta_{1}\|x-y\|^{2}+\beta_{2}\|x-y\|^{2-\alpha}\right)^{\frac{1}{2}}.$

###### Proof.

When $x=y$, $\phi_{h}(x,y)=0$ and the result holds. Let’s assume $x\neq y$
from now on.

For any $r>\|x-y\|>0$, by [8, Theorem 1], there two positive constants
$\eta_{1}$ and $\eta_{2}$ independent of $x$ and $y$, such that for any $T>0$,

$\phi_{h}(x,y;T)\leq\eta_{1}\frac{r^{2}}{T}+\eta_{2}\frac{T}{r^{\alpha}}+hT.$

The right hand side of the above inequality as a function of $T$ has a global
minimum in $(0,\infty)$ at
$T=(\eta_{1}r^{2}/(h+\eta_{2}/r^{\alpha}))^{\frac{1}{2}}$, so

$\phi_{h}(x,y)\leq\left(4h\eta_{1}r^{2}+4\eta_{1}\eta_{2}r^{2-\alpha}\right)^{\frac{1}{2}}.$

Letting $r$ go to $\|x-y\|$, the desired result follows from continuity with
$\beta_{1}=2h\eta_{1}$ and $\beta_{2}=4\eta_{1}\eta_{2}$. ∎

This lemma further implies continuity of $\phi_{h}$.

######  Lemma 2.4.

$\phi_{h}(x,y)$ is continuous with respect to both $x$ and $y$.

###### Proof.

Choose an arbitrary $y^{\prime}$ close to $y$, by Lemma 2.3, there is a $C>0$,
such that

$\phi_{h}(x,y)-\phi_{h}(x,y^{\prime})\leq\phi_{h}(y^{\prime},y)\leq
C\|y-y^{\prime}\|^{\frac{2-\alpha}{2}};$
$\phi_{h}(x,y^{\prime})-\phi_{h}(x,y)\leq\phi_{h}(y,y^{\prime})\leq
C\|y-y^{\prime}\|^{\frac{2-\alpha}{2}}.$

This shows $\phi_{h}(x,y)$ is continuous with respect to $y$. The proof for
$x$ is similar. ∎

######  Lemma 2.5.

If $\gamma(t)$ is collision-free solution of (2) with energy $h>0$, then
$d^{2}\|\gamma(t)\|/dt^{2}>0$.

###### Proof.

Since $\gamma(t)$ is collision-free, $\|\gamma(t)\|$ is always positive. Let
$I(t)=\|\gamma(t)\|^{2}$. It is enough to prove $\ddot{I}(t)>0$, which follows
from

$\displaystyle\frac{1}{2}\ddot{I}$
$\displaystyle=\ll\dot{\gamma},\dot{\gamma}\gg^{2}+\ll\gamma,\ddot{\gamma}\gg=\|\dot{\gamma}\|^{2}-\alpha
U(\gamma)$
$\displaystyle=\frac{2-\alpha}{2}\|\dot{\gamma}\|^{2}+\alpha\left(\frac{1}{2}\|\dot{\gamma}\|^{2}-U(\gamma)\right)=\frac{2-\alpha}{2}\|\dot{\gamma}\|^{2}+\alpha
h>0.$

∎

For any $v\in\hat{\mathbb{S}}$, define
$\underline{v}:=\min\\{|v_{ij}|=|v_{i}-v_{j}|:\;1\leq i\neq j\leq N\\}$ and

$\mathbb{B}_{\delta\underline{v}}(v):=\\{u\in\mathbb{S}:\|u-v\|\leq\delta\underline{v}\\},$

where $\delta:=\frac{\sqrt{m_{0}}}{4}$ and
$m_{0}:=\min\\{m_{i}:\;i=1,\dots,N\\}.$

######  Lemma 2.6.

If $u\in\mathbb{B}_{\delta\underline{v}}(v)$, then
$|u_{ij}|\geq\frac{1}{2}|v_{ij}|$, $\forall 1\leq i\neq j\leq N,$ and
$U(u)\leq 2^{\alpha}U(v).$

###### Proof.

Notice that $m_{0}|u-v|^{2}\leq\|u-v\|^{2}$. Then

$\displaystyle|u_{ij}|$
$\displaystyle=|u_{i}-v_{i}+v_{i}-v_{j}+v_{j}-u_{j}|\geq|v_{ij}|-|u_{i}-v_{i}|-|u_{j}-v_{j}|$
$\displaystyle\geq|v_{ij}|-2|u-v|\geq|v_{ij}|-\frac{2}{\sqrt{m_{0}}}\|u-v\|\geq|v_{ij}|-\frac{1}{2}\underline{v}$
$\displaystyle\geq|v_{ij}|-\frac{1}{2}|v_{ij}|=\frac{1}{2}|v_{ij}|.$

By the above inequality,

$U(u)=\sum_{1\leq i<j\leq
N}\frac{m_{i}m_{j}}{|u_{ij}|^{\alpha}}\leq\sum_{1\leq i<j\leq
N}2^{\alpha}\frac{m_{i}m_{j}}{|v_{ij}|^{\alpha}}\leq 2^{\alpha}U(v).$

∎

######  Lemma 2.7.

If $u\in\mathbb{B}_{\delta\underline{v}}(v)$ and $r_{2}>r_{1}>0$,
$\frac{1}{\sqrt{2h}}\phi_{h}(r_{1}u,r_{2}u)\leq
r_{2}-r_{1}+W_{\alpha,v}(r_{1},r_{2})$ with

(8)
$W_{\alpha,v}(r_{1},r_{2})=\begin{cases}\frac{2^{\alpha}U(v)}{2h(\alpha-1)}\left(\frac{1}{r_{1}^{\alpha-1}}-\frac{1}{r_{2}^{\alpha-1}}\right),&\text{
if }\alpha>1;\\\ \frac{2^{\alpha}U(v)}{2h}(\log r_{2}-\log r_{1}),&\text{ if
}\alpha=1;\\\
\frac{2^{\alpha}U(v)}{2h(1-\alpha)}(r_{2}^{1-\alpha}-r_{1}^{1-\alpha}),&\text{
if }\alpha\in(0,1).\end{cases}$

###### Proof.

Let $\xi(t)=r_{1}u+\sqrt{2h}tu$, $t\in[0,\frac{r_{2}-r_{1}}{\sqrt{2h}}]$. Then
$\rho(t)=\|\xi(t)\|=r_{1}+\sqrt{2h}t$ and

$\frac{1}{\sqrt{2h}}\mathcal{A}_{h}(\xi;0,\frac{r_{2}-r_{1}}{\sqrt{2h}})\leq
r_{2}-r_{1}+\frac{2^{\alpha}U(v)}{2h}\int_{r_{1}}^{r_{2}}\rho^{-\alpha}\,d\rho=r_{2}-r_{1}+W_{\alpha,v}(r_{1},r_{2}).$

∎

######  Lemma 2.8.

Given an arbitrary $x$ and $v\in\hat{\mathbb{S}}$. There is an $R>2\|x\|$
large enough, such that for any $y$ with $\|y\|\geq R$ and
$u=y/\|y\|\in\mathbb{B}_{\delta\underline{v}}(v)$, if
$\gamma\in\mathcal{C}(x,y;T)$ is an $h$-free-time minimizer, there is a
constant $C_{\alpha,v}$ independent of $\gamma$, such that

$\left\|\frac{\gamma(t)}{\|\gamma(t)\|}-u\right\|\leq
C_{\alpha,v}f_{\alpha}(\|\gamma(t)\|),\;\forall t\in[T^{\prime},T],$

where $T^{\prime}=\inf\\{t\in[0,T];\;\|\gamma(t)\|=\frac{1}{2}\|y\|\\}$ and
$f_{\alpha}$ is decreasing function as below

(9) $f_{\alpha}(r)=\begin{cases}(2r)^{-\frac{1}{2}},\;&\text{ if }\alpha>1;\\\
\left(\frac{\log 2r}{2r}\right)^{\frac{1}{2}},\;&\text{ if }\alpha=1;\\\
(2r)^{-\frac{\alpha}{2}},\;&\text{ if }\alpha\in(0,1).\\\ \end{cases}$

###### Proof.

Since $\frac{1}{2}\|y\|>\|x\|$, $T^{\prime}$ is well-defined with
$\frac{d\|\gamma(t)\|}{dt}|_{t=T^{\prime}}>0$. By Lemma 2.5, $\|\gamma(t)\|$
is strictly increasing, when $t\in[T^{\prime},T]$.

By Lemma 2.3, there is a constant $C_{1}$ depending on $x$ and $v$, such that

$\sup\\{\phi_{h}(x,\|x\|u);\;u\in\mathbb{B}_{\delta\underline{v}}(v)\\}\leq\sqrt{2h}C_{1}.$

Then Lemma 2.2 and 2.7 imply

(10)
$\phi_{h}(x,y)\leq\phi_{h}(x,\|x\|u)+\phi_{h}(\|x\|u,y)\leq\sqrt{2h}\big{(}C_{1}+\|y\|-\|x\|+W_{\alpha,v}(\|x\|,\|y\|)\big{)}.$

With this, Lemma 2.1 implies

(11)
$\ell(\gamma|_{[0,T]})\leq\frac{1}{\sqrt{2h}}\phi_{h}(x,y)\leq\|y\|+W_{\alpha,v}(\|x\|,\|y\|)+C_{1}-\|x\|.$

Fix an arbitrary $t\in[T^{\prime},T)$ (the result is trivial, when $t=T$), set
$r=\|\gamma(t)\|$ and $z=ru$, then $\Sigma=\\{q\in\mathbb{E}:\;\ll
q-z,u\gg=0\\}$ is the hyperplane perpendicular to the line
$\overrightarrow{0z}$ at $z$. If $\gamma(t)=z$, set $t^{\prime}=t$. If not,
$\gamma(t)$ and $y$ must be separated by $\Sigma$, as $\|\gamma(t)\|<\|y\|$.
Then we can always find a $t^{\prime}\in(t,T)$ with
$\gamma(t^{\prime})\in\Sigma$(see Figure 1). As a result,

(12)
$\begin{cases}\|\gamma(t^{\prime})-z\|^{2}=\|\gamma(t^{\prime})\|^{2}-\|z\|^{2},&\|\gamma(t^{\prime})\|\geq\|z\|\\\
\|\gamma(t^{\prime})-z\|^{2}=\|y-\gamma(t^{\prime})\|^{2}-\|y-z\|^{2},&\|y-\gamma(t^{\prime})\|\geq\|y-z\|\end{cases}$

Figure 1.

Combining these with (11), we get

(13) $\displaystyle
2\|\gamma(t^{\prime})-z\|^{2}=\|\gamma(t^{\prime})\|^{2}+\|\gamma(t^{\prime})-y\|^{2}-(\|z\|^{2}+\|y-z\|^{2})$
$\displaystyle=(\|\gamma(t^{\prime})\|+\|\gamma(t^{\prime})-y\|)^{2}-2\|\gamma(t^{\prime})\|\cdot\|\gamma(t^{\prime})-y\|-(\|y-z\|+\|z\|)^{2}+2\|z\|\cdot\|y-z\|$
$\displaystyle\leq(\|\gamma(t^{\prime})\|+\|\gamma(t^{\prime})-y\|)^{2}-\|y\|^{2}$
$\displaystyle\leq(\|x\|+\|x-\gamma(t^{\prime})\|+\|\gamma(t^{\prime})-y\|)^{2}-\|y\|^{2}$
$\displaystyle\leq(\|x\|+\ell(\gamma|_{[0,T]}))^{2}-\|y\|^{2}$
$\displaystyle\leq(\|y\|+W_{\alpha,v}(\|x\|,\|y\|)+C_{1})^{2}-\|y\|^{2}$

For simplicity let’s write $W_{\alpha,v}(\|x\|,\|y\|)$ as $W_{\alpha,v}$. Then

(14)
$\|\gamma(t^{\prime})-z\|\leq\left(\|y\|W_{\alpha,v}+\frac{1}{2}W^{2}_{\alpha,v}+C_{1}(\|y\|+W_{\alpha,v}+\frac{1}{2}C_{1})\right)^{\frac{1}{2}}.$

Meanwhile notice that

$\ell(\gamma|_{[0,t]})\geq\|\gamma(t)-x\|\geq r-\|x\|;$
$\ell(\gamma|_{[t^{\prime},T]})\geq\|y-\gamma(t^{\prime})\|\geq\|y-z\|\geq\|y\|-r.$

Then together with (11), they imply

$\|\gamma(t)-\gamma(t^{\prime})\|\leq\ell(\gamma|_{[t,t^{\prime}]})=\ell(\gamma|_{[0,T]})-\ell(\gamma|_{[0,t]})-\ell(\gamma|_{[t^{\prime},T]})\leq
W_{\alpha,v}+C_{1}.$

Combining this with (14), we get

(15) $\displaystyle\|\gamma(t)-z\|$
$\displaystyle\leq\|\gamma(t)-\gamma(t^{\prime})\|+\|\gamma(t^{\prime})-z\|$
$\displaystyle\leq\left(\|y\|W_{\alpha,v}+\frac{1}{2}W^{2}_{\alpha,v}+C_{1}\Big{(}\|y\|+W_{\alpha,v}+\frac{1}{2}C_{1}\Big{)}\right)^{\frac{1}{2}}+W_{\alpha,v}+C_{1}.$

Dividing the above inequality by $r=\|\gamma(t)\|$, and using the fact that
$\|y\|\leq 2r$, we get

$\displaystyle\left\|\frac{\gamma(t)}{\|\gamma(t)\|}-u\right\|$
$\displaystyle\leq\left(\frac{2W_{\alpha,v}}{r}+\frac{1}{2}\left(\frac{W_{\alpha,v}}{r}\right)^{2}+\frac{C_{1}(2r+W_{\alpha,v}+\frac{1}{2}C_{1})}{r^{2}}\right)^{\frac{1}{2}}+\frac{W_{\alpha,v}}{r}+\frac{C_{1}}{r}$

From now on we use $W_{\alpha,v}$ to represent $W_{\alpha,v}(\|x\|,2r)$. As
$\|y\|\leq 2r$ implies $W_{\alpha,v}(\|x\|,\|y\|)\leq W_{\alpha,v}(\|x\|,2r)$,
the above inequality still holds. Hence we may rewrite is as,

$\left\|\frac{\gamma(t)}{\|\gamma(t)\|}-u\right\|\leq\left(4\frac{W_{\alpha,v}}{2r}+2\left(\frac{W_{\alpha,v}}{2r}\right)^{2}+\frac{C_{1}(2r+W_{\alpha,v}+\frac{1}{2}C_{1})}{r^{2}}\right)^{\frac{1}{2}}+2\frac{W_{\alpha,v}}{2r}+\frac{C_{1}}{r}.$

When $r\to\infty$, by (8), $\frac{W_{\alpha,v}}{2r}\to\infty$. While

$2\frac{W_{\alpha,v}}{2r}+\frac{C_{1}}{r}\simeq
o\left(\sqrt{\frac{W_{\alpha,v}}{2r}}\right),$

and

$\frac{C_{1}(2r+W_{\alpha,v}+\frac{1}{2}C_{1})}{r^{2}}\simeq\begin{cases}o(\frac{W_{\alpha,v}}{2r}),&\text{
when }\alpha\in(0,1];\\\ O(\frac{W_{\alpha,v}}{2r}),&\text{ when
}\alpha\in(1,2).\end{cases}$

As a result, when $R$ is large enough, there is a constant $C_{2}$ independent
of $\gamma$ with

$\left\|\frac{\gamma(t)}{\|\gamma(t)\|}-u\right\|\leq
C_{2}\left(\frac{W_{\alpha,v}(\|x\|,2r)}{2r}\right)^{\frac{1}{2}}.$

The rest then follows from Lemma 2.7 and direct computations.

For the case $x=0$, again by Lemma 2.3, there is a constant $C_{2}$, such that

$\sup\\{\phi_{h}(0,u);\;u\in\mathbb{B}_{\delta\underline{v}}(v)\\}\leq\sqrt{2h}C_{2}.$

Using Lemma 2.2 and 2.7 again, we get

(16)
$\phi_{h}(0,y)\leq\phi_{h}(0,u)+\phi_{h}(u,y)\leq\sqrt{2h}\big{(}C_{2}+\|y\|-1+W_{\alpha,v}(1,\|y\|)\big{)}.$

With this, we get the desired result by repeating the exact same argument as
above. ∎

######  Lemma 2.9.

$\lim_{n_{0}\to\infty}\sum_{k=n_{0}}^{\infty}f_{\alpha}(2^{k})=0$.

###### Proof.

First let’s assume $\alpha\in(0,1)$, then

$\frac{f_{\alpha}(2^{k+1})}{f_{\alpha}(2^{k})}=\frac{(2^{k+1})^{\frac{\alpha}{2}}}{(2^{k+2})^{\frac{\alpha}{2}}}=\frac{1}{2^{\frac{\alpha}{2}}}<1.$

By the summation formula of geometric series,

$\sum_{k=n_{0}}^{\infty}f_{\alpha}(2^{k})=\frac{f_{\alpha}(2^{n_{0}})}{1-2^{-\frac{\alpha}{2}}}=\frac{1}{(2^{\frac{\alpha}{2}}-1)}\frac{1}{2^{\frac{\alpha}{2}n_{0}}}\to
0,\;\text{ as }n_{0}\to\infty,$

The proof is the same for $\alpha>1$, as in this case

$\frac{f_{\alpha}(2^{k+1})}{f_{\alpha}(2^{k})}=\frac{(2^{k+1})^{\frac{1}{2}}}{(2^{k+2})^{\frac{1}{2}}}=\frac{1}{2^{\frac{1}{2}}}<1,$

and

$\sum_{k=n_{0}}f_{\alpha}(2^{k})=\frac{f_{\alpha}(2^{n_{0}})}{1-2^{\frac{1}{2}}}=\frac{1}{\sqrt{2}-1}\frac{1}{2^{\frac{n_{0}}{2}}}\to
0,\text{ as }n_{0}\to\infty.$

Now assume $\alpha=1$. Since there is an $n_{0}$ large enough, such that $\log
2^{k+1}\leq 2^{\frac{k+1}{2}}$, $\forall k\geq n_{0}$,

$\sum_{k=n_{0}}^{\infty}f_{\alpha}(2^{k})\leq\sum_{k=n_{0}}^{\infty}2^{-\frac{k+1}{4}}=\frac{1}{2^{\frac{1}{4}}-1}\frac{1}{2^{\frac{n_{0}}{4}}}\to
0,\text{ as }n_{0}\to\infty.$

∎

##  3\. Proof of Theorem 1.1

By Lemma 2.9, we can find an $n_{0}$ large enough, such that

(17)
$C_{\alpha,v}\sum_{k=n_{0}}^{\infty}f_{\alpha}(2^{k})\leq\delta\underline{v}.$

For each $n\geq n_{0}$, set $y_{n}=2^{n}v$, there is a
$\gamma_{n}\in\mathcal{C}(x,y_{n};T_{n})$ satisfying
$\mathcal{A}_{h}(\gamma_{n};0,T_{n})=\phi_{h}(x,y_{n}).$

Let $R$ be the constant given in Lemma 2.8, we will further assume
$2^{n_{0}}\geq R$. By the strictly increasing property of $\|\gamma_{n}(t)\|$
obtained in the proof of the same lemma, for each $n\geq n_{0}$, there is a
unique sequence of moments $\\{t_{n,k}\\}_{k=n_{0}}^{n}$, such that

$\|\gamma_{n}(t_{n,k})\|=2^{k}\;\text{ for each }\;k=n_{0},n_{0}+1,\dots,n.$

######  Lemma 3.1.

For each $n\geq n_{0}$ and $t\in[t_{n,n_{0}},t_{n,n}]$, let
$[\|\gamma_{n}(t)\|]$ be the integer part of $\|\gamma_{n}(t)\|$,

(18) $\left\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}-v\right\|\leq
C_{\alpha,v}\sum_{i=[\log\|\gamma_{n}(t)\|]}^{\infty}f_{\alpha}(2^{i})\leq\delta\underline{v},$

###### Proof.

As $\|\gamma_{n}(t)\|\geq 2^{n_{0}}$, $\forall t\in[t_{n,n_{0}},t_{n,n}]$, the
second inequality in (18) follows directly from (17).

Notice that $2^{n-1}\leq\|\gamma_{n}(t)\|<2^{n}$, when
$t\in[t_{n,n-1},t_{n,n})$. By Lemma 2.8,

$\left\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}-\frac{\gamma_{n}(t_{n,n})}{\|\gamma_{n}(t_{n,n})\|}\right\|\leq
C_{\alpha,v}f_{\alpha}(\|\gamma_{n}(t)\|)\leq
C_{\alpha,v}f_{\alpha}(2^{n-1})\leq
C_{\alpha,v}\sum_{i=[\log\|\gamma(t)\|]}^{\infty}f_{\alpha}(2^{i}).$

This proves (18), when $t\in[t_{n,n-1},t_{n,n})$.

Now let’s assume there is an integer $k\in(n_{0},n)$, such that (18) holds for
all $t\in[t_{n,k+1},t_{n,n})$. With this we can apply Lemma 2.8 to
$\gamma|_{[0,t_{n,k+1}]}$, and as a result, for any $t\in[t_{n,k},t_{n,k+1})$,

$\left\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}-\frac{\gamma_{n}(t_{n,k+1})}{\|\gamma_{n}(t_{n,k+1})\|}\right\|\leq
C_{\alpha,v}f_{\alpha}(\|\gamma(t)\|)\leq
C_{\alpha,v}f_{\alpha}([\log\|\gamma(t)\|])=C_{\alpha,v}f_{\alpha}(2^{k}).$

As a result, for any $t\in[t_{n,k},t_{n,k+1})$,

$\displaystyle\left\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}-v\right\|$
$\displaystyle\leq\left\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}-\frac{\gamma_{n}(t_{n,k+1})}{\|\gamma_{n}(t_{n,k+1})\|}\right\|+\left\|\frac{\gamma_{n}(t_{n,k+1})}{\|\gamma_{n}(t_{n,k+1})\|}-v\right\|$
$\displaystyle\leq C_{\alpha,v}\sum_{i=k}^{\infty}f_{\alpha}(2^{i})\leq
C_{\alpha,v}\sum_{i=[\log\|\gamma_{n}(t)\|]}^{\infty}f_{\alpha}(2^{i}).$

The desired result then follows from induction. ∎

By the above lemma,
$\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}\in\mathbb{B}_{\delta\underline{v}}(v)$,
for any $t\in[t_{n,n_{0}},t_{n,n}]$. From the proof of Lemma 2.8, in
particular (10) and (16), we know there is a constant $C_{0}>0$, such that

(19) $\displaystyle\phi_{h}(x,\gamma_{n}(t))$
$\displaystyle\leq\phi_{h}\left(x,\|x\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}\right)+\phi_{h}\left(\|x\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|},\gamma_{n}(t)\right)$
$\displaystyle\leq\sqrt{2h}\big{(}C_{0}+\|\gamma_{n}(t)\|+W_{\alpha,v}(\|x\|,\|\gamma_{n}(t)\|)\big{)}.$

Here and in the below, when $x=0$, $W_{\alpha,v}(\|x\|,\cdot)$ should be seen
as $W_{\alpha,v}(1,\cdot)$.

As the energy identity can be written as
$\|\dot{\gamma}_{n}\|^{2}=L(\gamma_{n},\dot{\gamma}_{n})+h$, we get

(20)
$\int_{0}^{t}\|\dot{\gamma}_{n}(s)\|^{2}\,ds=\phi_{h}(x,\gamma_{n}(t))\leq\sqrt{2h}\big{(}C_{0}+\|\gamma_{n}(t)\|+W_{\alpha,v}(\|x\|,\|\gamma_{n}(t)\|)\big{)};$

Meanwhile the energy identity also implies
$\|\dot{\gamma}_{n}\|\geq\sqrt{2h}$. Therefore

(21)
$\sqrt{2h}t\leq\int_{0}^{t}\|\dot{\gamma}_{n}\|\,ds\leq\sqrt{t}\left(\int_{0}^{t}\|\dot{\gamma}_{n}\|^{2}\,ds\right)^{\frac{1}{2}}\leq(\sqrt{2h}t)^{\frac{1}{2}}\big{(}\|\gamma_{n}(t)\|+W_{\alpha,v}+C_{0}\big{)}^{\frac{1}{2}}.$

As a result,

(22) $\frac{\sqrt{2h}t}{\|\gamma_{n}(t)\|}\leq
1+\frac{W_{\alpha,v}+\beta_{x,v}}{\|\gamma_{n}(t)\|}\Rightarrow\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}-1\geq-\frac{W_{\alpha,v}+C_{0}}{\|\gamma_{n}(t)\|+W_{\alpha,v}+C_{0}}.$

On the other hand, (20) also implies

$\frac{1}{t}\|\gamma_{n}(t)-x\|^{2}\leq\frac{1}{t}\left(\int_{0}^{t}\|\dot{\gamma}_{n}\|\,ds\right)^{2}\leq\int_{0}^{t}\|\dot{\gamma}_{n}\|^{2}\,ds\leq\sqrt{2h}(\|\gamma_{n}(t)\|+W_{\alpha,v}+C_{0}).$

Multiplying the above inequality by
$\|\gamma_{n}(t)\|/(\sqrt{2h}\|\gamma_{n}(t)-x\|^{2})$, we get

$\displaystyle\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}$
$\displaystyle\leq\frac{\|\gamma_{n}(t)\|(\|\gamma_{n}(t)\|+W_{\alpha,v}+C_{0})}{\|\gamma_{n}(t)-x\|^{2}}$
$\displaystyle\leq\frac{(\|\gamma_{n}(t)-x\|+\|x\|)(\|\gamma_{n}(t)-x\|+\|x\|+W_{\alpha,v}+C_{0})}{\|\gamma_{n}(t)-x\|^{2}}.$

As a result,

(23)
$\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}-1\leq\frac{W_{\alpha,v}+C_{0}+2\|x\|}{\|\gamma_{n}(t)-x\|}+\frac{\|x\|(W_{\alpha,v}+C_{0}+\|x\|)}{\|\gamma_{n}(t)-x\|^{2}}.$

By (22) and (23), when $n_{0}$ is large enough, we can find a continuous
function $g_{\alpha}:[2^{n_{0}},\infty)$,

(24) $g_{\alpha}(r)=\begin{cases}O(\frac{1}{r}),&\text{ if }\alpha>1;\\\
O(\frac{\log r}{r}),&\text{ if }\alpha=1;\\\ O(\frac{1}{r^{\alpha}}),&\text{
if }\alpha\in(0,1),\end{cases}\text{ as }r\to\infty$

such that, for any $t\in[t_{n,n_{0}},t_{n,n}]$,

(25) $\left|\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}-1\right|\leq
g_{\alpha}(\|\gamma_{n}(t)\|).$

By (24) and (26), we can assume the following holds

(26) $\frac{1}{2}\leq\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}\leq 2,\;\;\forall
t\in[t_{n,n_{0}},t_{n,n}]\text{ and }n\geq n_{0}.$

The second inequality in (26) then implies

$T_{n}=t_{n,n}\geq\frac{\|\gamma_{n}(t_{n,n})\|}{2\sqrt{2h}}=\frac{2^{n}}{2\sqrt{2h}}\to\infty,\;\text{
as }n\to\infty.$

On the other hand, the first inequality in (26) implies

$t_{n,n_{0}}\leq\frac{2}{\sqrt{2h}}\|\gamma_{n}(t_{n,n_{0}})\|=\frac{2^{n_{0}+1}}{\sqrt{2h}},\;\;\forall
n\geq n_{0}.$

Hence $\tilde{t}_{n_{0}}=\sup\\{t_{n,n_{0}}:\;n\geq n_{0}\\}$ is a finite
number.

Now fix an arbitary $t\geq\tilde{t}_{n_{0}}$, by Lemma 3.1
$\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}\in\mathbb{B}_{\delta\underline{v}}(v)$.
Then (26) implies

(27) $2^{n_{0}}\leq\|\gamma_{n}(t)\|\leq 2\sqrt{2h}t,\;\;\forall n\geq n_{0}.$

Combining the second inequality above with (19) gives us

$\phi_{h}(x,\gamma_{n}(t))\leq
4ht+\sqrt{2h}\big{(}W_{\alpha,v}(\|x\|,\sqrt{2h}t)+C_{0}\big{)}.$

We may further assume $n_{0}$ large enough, such that

$W_{\alpha,v}(\|x\|,\sqrt{2h}t)+C_{0}\leq 2\sqrt{2h}t,\;\text{ when
}\sqrt{2h}t\geq 2^{n_{0}}.$

Hence $\mathcal{A}_{h}(\gamma_{n};0,t)=\phi_{h}(x,\gamma_{n}(t))\leq 8ht$,
$\forall n\geq n_{0}$. Then for any $0\leq\tau<\tau^{\prime}\leq t$,

$\displaystyle\|\gamma_{n}(\tau^{\prime})-\gamma_{n}(\tau)\|$
$\displaystyle\leq\int_{\tau}^{\tau^{\prime}}\|\dot{\gamma}_{n}\|\,ds\leq(\tau^{\prime}-\tau)^{\frac{1}{2}}\left(\int_{\tau}^{\tau^{\prime}}\|\dot{\gamma}_{n}\|^{2}\,ds\right)^{\frac{1}{2}}$
$\displaystyle\leq(\tau^{\prime}-\tau)^{\frac{1}{2}}\big{(}\mathcal{A}_{h}(\gamma;0,t)\big{)}^{\frac{1}{2}}\leq
2\sqrt{2h}(\tau^{\prime}-\tau)^{\frac{1}{2}}t^{\frac{1}{2}}.$

This shows $\\{\gamma_{n}|_{[0,t]}:n\geq n_{0}\\}$ is equicontinuous. Since
$\gamma_{n}(0)=x$, $\forall n\geq n_{0}$, it is also equibounded. By the
Ascoli-Arzela theorem (after passing to a proper subsequence)
$\\{\gamma_{n}|_{[0,t]};n\geq n_{0}\\}$ will converge uniformly to an absolute
continuous path $\xi:[0,t]\to\mathbb{E}$.

Since the above argument can be repeated for any
$\tau_{k}\geq\tilde{t}_{n_{0}}$ with $\lim_{k\to\infty}\tau_{k}=\infty$, by a
diagonal argument there exists an absolute continuous path
$\gamma:[0,\infty)\to\mathbb{E}$, such that $\gamma_{n}$ converges to $\gamma$
uniformly on any compact sub-interval of $[0,\infty)$.

For any $T>0$, by the lower semi-continuity of $\mathcal{A}_{h}$ and the
continuity of $\phi_{h}$ (Lemma 2.4),

$\phi_{h}(x,\gamma(T))\leq\mathcal{A}_{h}(\gamma;0,T)\leq\liminf_{n\to\infty}\mathcal{A}_{h}(\gamma_{n};0,T)=\liminf_{n\to\infty}\phi_{h}(x,\gamma_{n}(T))=\phi_{h}(x,\gamma(T)).$

Hence $\gamma|_{[0,T]}$ is an $h$-free-time minimizer, and then a collision-
free $h$-energy solution of (2).

The above results show that for any $t\geq\tilde{t}_{n_{0}}$,

$\frac{1}{2}\leq\frac{\|\gamma(t)\|}{\sqrt{2h}t}=\lim_{n\to\infty}\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}\leq
2;$
$\left\|\frac{\gamma(t)}{\|\gamma(t)\|}-v\right\|=\lim_{n\to\infty}\left\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}-v\right\|\leq\delta\underline{v};$
$\left|\frac{\gamma(t)}{\sqrt{2h}t}-1\right|=\lim_{n\to\infty}\left|\frac{\gamma_{n}(t)}{\sqrt{2h}t}-1\right|\leq\lim_{n\to\infty}g_{\alpha}(\|\gamma_{n}(t)\|)\leq
g_{\alpha}(\|\gamma(t)\|).$

With these estimates, we get

$\displaystyle\lim_{t\to\infty}\frac{\|\gamma(t)-\sqrt{2h}tv\|}{\sqrt{2h}t}$
$\displaystyle=\lim_{t\to\infty}\lim_{n\to\infty}\frac{\|\gamma_{n}(t)-\sqrt{2h}tv\|}{\sqrt{2h}t}$
$\displaystyle\leq\lim_{t\to\infty}\lim_{n\to\infty}\left(\frac{\big{\|}\gamma_{n}(t)-\|\gamma_{n}(t)\|v\big{\|}}{\sqrt{2h}t}+\frac{\big{\|}\|\gamma_{n}(t)\|v-\sqrt{2h}tv\big{\|}}{\sqrt{2h}t}\right)$
$\displaystyle\leq\lim_{t\to\infty}\lim_{n\to\infty}\left(\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}\left\|\frac{\gamma_{n}(t)}{\|\gamma_{n}(t)\|}-v\right\|+\left|\frac{\|\gamma_{n}(t)\|}{\sqrt{2h}t}-1\right|\right)$
$\displaystyle=\lim_{t\to\infty}\left(\frac{\|\gamma(t)\|}{\sqrt{2h}t}\left\|\frac{\gamma(t)}{\|\gamma(t)\|}-v\right\|+\left|\frac{\|\gamma(t)\|}{\sqrt{2h}t}-1\right|\right)$
$\displaystyle\leq\lim_{t\to\infty}\left(2\cal\sum_{i=[\log\|\gamma(t)\|]}^{\infty}f_{\alpha}(2^{i})+g_{\alpha}(\|\gamma(t)\|)\right)=0.$

This means $\gamma(t)=\sqrt{2h}tv+o(t)$, when $t\to\infty$, which finishes our
proof of Theorem 1.1.

Acknowledgement. The author thanks Duokui Yan and Yuan Zhou for their
encouragement and helpful comments, and the anonymous referees for their value
comments and suggestions.

## References

  * [1] J. Chazy.  Sur l’allure du mouvement dans le problème des trois corps quand le temps croît indéfiniment.  Ann. Sci. École Norm. Sup. (3), 39:29–130, 1922.
  * [2] A. Chenciner.  Action minimizing solutions of the Newtonian $n$-body problem: from homology to symmetry.  In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), pages 279–294. Higher Ed. Press, Beijing, 2002.
  * [3] G. Contreras and R. Iturriaga.  Global minimizers of autonomous lagrangians.  https://www.cimat.mx/~gonzalo/libro/lagrangians.pdf, 2000.
  * [4] P. Davide and S. Terracini.  On the existence of minimal expansive solutions to the n-body problem.  https://arxiv.org/abs/2310.06360, 2023.
  * [5] D. L. Ferrario and S. Terracini.  On the existence of collisionless equivariant minimizers for the classical $n$-body problem.  Invent. Math., 155(2):305–362, 2004.
  * [6] S. Fleischer and A. Knauf.  Improbability of collisions in $n$-body systems.  Arch. Ration. Mech. Anal., 234(3):1007–1039, 2019.
  * [7] J. Liu, D. Yan, and Y. Zhou.  Existence of hyperbolic motions to a class of Hamiltonians and generalized $N$-body system via a geometric approach.  Arch. Ration. Mech. Anal., 247(4):Paper No. 64, 54, 2023.
  * [8] E. Maderna.  On weak KAM theory for $N$-body problems.  Ergodic Theory Dynam. Systems, 32(3):1019–1041, 2012.
  * [9] E. Maderna and A. Venturelli.  Viscosity solutions and hyperbolic motions: a new PDE method for the $N$-body problem.  Ann. of Math. (2), 192(2):499–550, 2020.
  * [10] D. G. Saari.  Improbability of collisions in Newtonian gravitational systems.  Trans. Amer. Math. Soc., 162:267–271; erratum, ibid. 168 (1972), 521, 1971.


# Walter Talbot’s thesis

Thomas Hales

(Date: May 16, 2018)

Walter Richard Talbot was the fourth African American to earn a PhD in
Mathematics. His doctoral degree is from the University of Pittsburgh in 1934
in geometric group theory. As far as I know, research in Pittsburgh on
geometric group theory seems to have started with Professors J. S. Taylor and
M. M. Culver at the University of Pittsburgh, who were both academic
descendents of Felix Klein. They were both members of Talbot’s thesis
committee.

Talbot’s research grew out of Klein’s work on fundamental domains [3] [2]. A
contemporary research program was the determination of fundamental domains of
finite group actions on complex vector spaces [5],[8],[4]. His thesis is not
widely available, and this note gives a brief synopsis of the main results of
his thesis, expressed using modern mathematical methods and language, and
placed in general context [7], [6].

##  1\. A fundamental domain for the symmetric group

Let $W$ be a finite group acting on a a finite-dimensional complex vector
space $V$. The general research problem is to give an explicit description of
a fundamental domain.

Let $\text{Herm}(V)$ be the space of hermitian forms on $V$; that is, the real
vector space of space sesquilinear forms $h:V\times V\to{\mathbb{C}}$ such
that

$\overline{h(u,v)}=h(v,u),\quad h(u,\mu v)=\mu\,h(u,v),\quad u,v\in
V,\quad\mu\in{\mathbb{C}}.$

The general linear group $GL(V)$ of $V$ acts on $\text{Herm}(V)$ by

$(g\cdot h)(u,v)=h(g^{-1}u,g^{-1}v),\quad g\in GL(V)$

and restricts to a representation of $W$ on $\text{Herm}(V)$.

Consider the following special context. Let $W=S_{n}$, the symmetric group on
$n$ letters. Take $V\subset{\mathbb{C}}^{n}$ to be the standard (irreducible)
$n-1$-dimensional representation of $W$ on

$V=\\{(z_{1},\ldots,z_{n})\mid z_{1}+\cdots+z_{n}=0\\}$

occuring in the permutation representation of $W$ on ${\mathbb{C}}^{n}$. Each
irreducible representation of $S_{n}$ can be realized over ${\mathbb{R}}$.
Pick a real form $V_{{\mathbb{R}}}$ of $V$. The group $W=S_{n}$ acts on
$\text{Herm}(V)$ as above. Its decomposition into irreducibles is given as
follows, with conventional notation:

######  Lemma 1.

$\text{Herm}(V)={1}\oplus V_{{\mathbb{R}}}\oplus V_{n-2,2}\oplus V_{n-2,1,1}.$

###### Proof.

By breaking $\text{Herm}(V)$ into real and imaginary parts, the representation
splits as

$\text{Sym}^{2}(V_{{\mathbb{R}}})\oplus
i\Lambda^{2}(V_{{\mathbb{R}}})\cong\text{Sym}^{2}(V_{{\mathbb{R}}})\oplus\Lambda^{2}(V_{{\mathbb{R}}})\cong({1}\oplus
V_{{\mathbb{R}}}\oplus V_{n-2,2})\oplus(V_{n-2,1,1})\cong
V_{{\mathbb{R}}}\otimes V_{{\mathbb{R}}},$

as given in Exercise 4.19 in [1]. ∎

If $h$ is a hermitian form, then its zero set

$Z(h)=\\{u\in V\mid h(u,u)=0\\}$

partitions $V$ into positive $h\geq 0$ and negative $h\leq 0$ regions. Given
hermitian forms $h_{i}$, we write $h_{i}\geq h_{j}$ to indicate the positive
region of $V$ bounded by the zero-set $Z(h_{i}-h_{j})$.

Select Hermitian forms

$h_{1},h_{2},\ldots,h_{n}$

giving the permutation basis of $1\oplus
V_{{\mathbb{R}}}\subset\text{Herm}(V)$. Define chambers $T(g)$ in $V$, for
$g\in S_{n}$, by inequalities

(1) $h_{g1}\geq\cdots\geq h_{gn}.$

These chambers partition $V$ and have walls given by hypersurfaces
$Z(h_{i}-h_{j})$, where $h_{i}-h_{j}$ span the standard representation
$V_{{\mathbb{R}}}$ of $S_{n}$, realized in the space of Hermitian matrices.
Explicitly, the representation $1\oplus V_{{\mathbb{R}}}$ has permutation
basis

$h_{i}(z,z^{\prime})=\bar{z}_{i}z^{\prime}_{i},\quad z,z^{\prime}\in
V\subset{\mathbb{C}}^{n},\quad i=1,\ldots,n.$

Thus, Talbot’s chambers (1) of $V$ are given by

$|z_{g1}|^{2}\geq\cdots\geq|z_{gn}|^{2}.$

There is an obvious correspondence with the Weyl chambers of the action of
$S_{n}$ on $V_{{\mathbb{R}}}$. (For a point of historical comparison, Weyl
gave lectures on the structure and representation of continuous groups in
Princeton in 1933-34.) More to the point, as B. Ion has observed, the proper
setting for Talbot’s thesis is the Cartan decomposition for
$GL(n,{\mathbb{C}})/U(n)$, where the space of Hermitian matrices is the Lie
algebra complement of the Lie algebra of $U(n)$, and $1\oplus
V_{\mathbb{R}}\subset\text{Herm}(V)$ is the maximal abelian with an action of
the Weyl group $W=S_{n}$.

##  2\. End notes

Talbot works projectively in ${\mathbb{P}}V$ rather than $V$, but this does
not play any role in the results.

Talbot only works with $n=5$ and in fact with the alternating group $A_{5}$.
When $n=5$, there is another subspace $1\oplus V_{3,2}\subset\text{Herm}(V)$
that is (up to the sign character) the permutation representation $1\oplus
V_{2,2,1}$ of $S_{5}$ on six letters (equivalent to the the action of $S_{5}$
on its six Sylow-$5$ subgroups). Talbot also considers regions of $V$ cut out
by a permutation basis of hermitian forms in this representation. He also
analyzes the boundary of chambers.

## References

  * [1] William Fulton and Joe Harris.  Representation theory: a first course, volume 129.  Springer Science & Business Media, 2013.
  * [2] Felix Klein.  Vorlesungen über die Theorie der elliptischen Modulfunktionen. Band I: Grundlegung der Theorie.  Ausgearbeitet und vervollständigt von Robert Fricke. Nachdruck der ersten Auflage. Bibliotheca Mathematica Teubneriana, Band 10. Johnson Reprint Corp., New York; B. G. Teubner Verlagsgesellschaft, Stuttgart, 1966.
  * [3] Felix Klein.  Vorlesungen über die Theorie der elliptischen Modulfunktionen. Band II: Fortbildung und Anwendung der Theorie.  Ausgearbeitet und vervollständigt von Robert Fricke. Nachdruck der ersten Auflage. Bibliotheca Mathematica Teubneriana, Band 11. Johnson Reprint Corp., New York; B. G. Teubner Verlagsgesellschaft, Stuttgart, 1966.
  * [4] W.I. Miller.  Fundamental Regions for the Simple Group of Order 168 in $S_{4}$.  PhD thesis, University of Pittsburgh, 1933.
  * [5] Henry F. Price.  Fundamental Regions for Certain Finite Groups in $S_{4}$.  Amer. J. Math., 40(1):108–112, 1918.
  * [6] Walter Talbot.  Fundamental regions in $S_{6}$ for the simple quaternary $G_{60}$, Type I.  PhD thesis, University of Pittsburgh, 1934.
  * [7] Walter R. Talbot.  Fundamental regions in $S_{6}$ for the simple quaternary $G_{60}$.  In Black mathematicians and their works, pages 225–239. Dorrance, Ardmore, Pa., 1980.
  * [8] J. W. Young.  Fundamental regions for cyclical groups of linear fractional transformations on two complex variables.  Bull. Amer. Math. Soc., 17(7):340–344, 1911.


# A Representation Transformation of Parametric Feynman Integrals

Wen<EMAIL_ADDRESS>School of Physics, Zhejiang University,
Hangzhou, Zhejiang 310027, China

###### Abstract

A transformation is applied to the parametric representation of Feynman
integrals. The obtained representation and the original parametric
representation are dual to each other. For integrals with momentum-space
correspondences, the “new” representation is just the Baikov’s representation.

##  1 Introduction

Calculation of Feynman integrals is essential in high-energy physics. There
are several representations of Feynman integrals. The most famous one is the
Feynman-parameter representation [1, 2, 3, 4]. Some variants of the Feynman-
parameter representation are the Lee-Pomeransky representation [5, 6] and the
one used by the author in refs. [7, 8, 9]. Another now widely used
representation is the Baikov’s representation [10, 11]. Obviously these two
representations should be equivalent, since both of them are derived from the
momentum representation. But it was not clear how to directly derive one
representation from another. The first step towards solving this problem is
made in this article. The representation used in refs. [7, 8, 9] and the
Baikov’s representation are characterized by two polynomials respectively. It
is shown that these two polynomials are related to each other through a
transformation. The transformation is described in section 2, and the
equivalence of the obtained representation with the Baikov’s representation is
proved in section 3.

##  2 Representation transformation

As was shown in refs. [7, 8, 9], a Feynman integral can be parametrized by an
integral of the following form.

$\begin{split}I(\lambda_{0},\lambda_{1},\ldots,\lambda_{n})=&\frac{\Gamma(-\lambda_{0})}{\prod_{i=m+1}^{n+1}\Gamma(\lambda_{i}+1)}\int\mathrm{d}\Pi^{(n+1)}\mathcal{F}^{\lambda_{0}}\prod_{i=1}^{m}x_{i}^{-\lambda_{i}-1}\prod_{i=m+1}^{n+1}x_{i}^{\lambda_{i}}\\\
\equiv&\int\mathrm{d}\Pi^{(n+1)}\mathcal{I}^{(-n-1)}.\end{split}$ (2.1)

Here $\mathcal{F}$ is a homogeneous polynomial of the Feynman parameters
$x_{i}$. The integration measure $\mathrm{d}\Pi^{(n+1)}$ is defined by
$\mathrm{d}\Pi^{(n+1)}=\prod_{i=1}^{n+1}\mathrm{d}x_{i}~{}\delta(1-\mathcal{E}^{(1)}(x))$,
with $\mathcal{E}^{(i)}(x)$ a positive definite homogeneous function of $x$ of
degree $i$. The parametric integrals satisfy the following identities.

$\displaystyle 0=$
$\displaystyle\int\mathrm{d}\Pi^{(n+1)}\frac{\partial}{\partial
x_{i}}\mathcal{I}^{(-n-1)},$ $\displaystyle i=1,2,\ldots,m,$ (2.2a)
$\displaystyle 0=$
$\displaystyle\int\mathrm{d}\Pi^{(n+1)}\frac{\partial}{\partial
x_{i}}\mathcal{I}^{(-n-1)}+\delta_{\lambda_{i}0}\int\mathrm{d}\Pi^{(n)}\left.\mathcal{I}^{(-n)}\right|_{x_{i}=0},$
$\displaystyle i=m+1,m+2,\ldots,n+1.$ (2.2b)

We apply the following transformation to the $\mathcal{F}$ polynomial.

$\displaystyle
u_{i}\equiv\frac{1}{\mathcal{F}}\frac{\partial\mathcal{F}}{\partial x_{i}},$
(2.3a)
$\displaystyle\mathcal{G}(u)\equiv\left.\frac{1}{\mathcal{F}}\right|_{x=x(u)}.$
(2.3b)

$\mathcal{F}$ is homogeneous in $x_{i}$. We assume that the degree of
$\mathcal{F}$ is $L+1$. Then obviously

$\sum_{i=1}^{n+1}u_{i}x_{i}=L+1.$ (2.4)

Taking the derivative of both sides with respect to $u_{i}$, we get

$x_{i}+\sum_{j=1}^{n+1}u_{j}\frac{\partial x_{j}}{\partial u_{i}}=0.$

On the other hand,

$\begin{split}\frac{1}{\mathcal{G}}\frac{\partial\mathcal{G}}{\partial
u_{i}}=\mathcal{F}\frac{\partial}{\partial
u_{i}}\left(\frac{1}{\mathcal{F}}\right)=-\frac{1}{\mathcal{F}}\sum_{j=1}^{n+1}\frac{\partial\mathcal{F}}{\partial
x_{j}}\frac{\partial x_{j}}{\partial
u_{i}}=-\sum_{j=1}^{n+1}u_{j}\frac{\partial x_{j}}{\partial
u_{i}}.\end{split}$

A combination of the above two equations leads to

$x_{i}=\frac{1}{\mathcal{G}}\frac{\partial\mathcal{G}}{\partial u_{i}}.$ (2.5)

Thus we see that the transformation defined by eq. 2.3 is reciprocal.

Generally speaking, the transformation defined by eq. 2.3a may not be
invertible. Even if it is, the obtained function $\mathcal{G}(u)$ may not be a
rational function. However, for a loop integral with a complete set of
propagators, $\mathcal{G}$ is indeed a rational function, as will be clear in
the next section.

##  3 Baikov’s representation

We consider a loop integral with a complete set of propagators

$v_{i}=\sum_{j,k}A_{i,jk}l_{j}\cdot l_{k}+2\sum_{j,k}B_{i,jk}l_{j}\cdot
p_{k}+C_{i},\quad i=1,~{}2,\dots,n,$ (3.1)

where $l$ are the loop momenta and $p$ are the external momenta. For
simplicity, I assume that all the propagators are linearly independent and the
Gram determinant of the external momenta $p$ does not vanish. For future
convenience, we collectively denote $l$ and $p$ by $q$. Scalar integrals can
be parametrized by integrals of the form [10, 11]

$J(\lambda_{0},\lambda_{1},\ldots,\lambda_{n})=\int\prod_{i=1}^{n}\mathrm{d}v_{n}~{}P^{-\lambda_{0}-\frac{1}{2}(L+E+1)}\prod_{i=1}^{n}u^{-\lambda_{i}-1},$
(3.2)

where $E$ is the number of the external momenta $p$. Here I have omitted some
irrelevant prefactors for brevity. The polynomial $P(v)$ is the Gram
determinant of the momenta $q$. That is

$P(v)\equiv\det(q_{i}\cdot q_{j}).$ (3.3)

In this section, I will prove that

$P(v_{1},v_{2},\dots,v_{n})=-\det(p_{i}\cdot
p_{j})\mathcal{G}(v_{1},v_{2},\dots,v_{n},-1),$ (3.4)

where $\mathcal{G}$ is the one defined in eq. 2.3b. The proof of eq. 3.4 is as
follows.

We define

$\displaystyle A_{ij}\equiv$ $\displaystyle\sum_{k=1}^{n}A_{k,ij}x_{k},$
$\displaystyle B_{ij}\equiv$ $\displaystyle\sum_{k=1}^{n}B_{k,ij}x_{k},$
$\displaystyle C\equiv$ $\displaystyle\sum_{i=1}^{n}C_{i}x_{i}.$

Then we have [7]

$\mathcal{F}=\sum_{i,j,k,l}p_{k}\cdot
p_{l}\tilde{A}_{ij}B_{ik}B_{jl}+(x_{n+1}-C)U,$ (3.5)

where

$\displaystyle U\equiv$ $\displaystyle\det(A_{ij}),$
$\displaystyle\tilde{A}_{ij}\equiv$ $\displaystyle\left(A^{-1}\right)_{ij}U.$

Let $a_{ij}$, $b_{ij}$, $\alpha_{ij,k}$, and $\beta_{ij}$ be those defined in
ref. [8]. That is, they are solutions to the following equations.

$\displaystyle\sum_{l}a_{il}B_{l,jk}=0,$
$\displaystyle\sum_{l}b_{il}A_{l,jk}=0,$
$\displaystyle\sum_{kl}\alpha_{ij,k}a_{kl}A_{l,mn}=\frac{1}{2}\left(\delta^{im}\delta^{jn}+\delta^{in}\delta^{jm}\right),$
$\displaystyle\sum_{kl}\beta_{ij,k}b_{kl}B_{l,mn}=\delta^{im}\delta^{jn}.$

Then it can be proven that (see appendix A)

$\mathcal{G}=u_{n+1}\det\left[\alpha_{ij,k}a_{kl}(u_{l}+u_{n+1}C_{l})+u_{n+1}g_{mn}B^{\prime}_{im}B^{\prime}_{jn}\right],$
(3.6)

where $u_{i}$ are those appeared in eq. 2.3, $g_{ij}$ is the inverse of the
Gram matrix $p_{i}\cdot p_{j}$, and

$B^{\prime}_{ij}(u)\equiv\frac{1}{2u_{n+1}}\sum_{k,l}\beta_{ij,k}b_{kl}\left(u_{l}+C_{l}u_{n+1}\right).$

On the other hand, $q_{i}\cdot q_{j}$ can be understood as a block matrix.
Then we have

$\displaystyle P=$ $\displaystyle\det\begin{pmatrix}l_{i}\cdot
l_{j}&l_{i}\cdot p_{j}\\\ l_{i}\cdot p_{j}&p_{i}\cdot p_{j}\end{pmatrix}$
$\displaystyle=$ $\displaystyle\det(p_{i}\cdot p_{j})\det\left(l_{i}\cdot
l_{j}-\sum_{mn}g_{mn}l_{i}\cdot p_{m}l_{j}\cdot p_{n}\right).$

It is easy to get

$\displaystyle l_{i}\cdot p_{j}=$
$\displaystyle\frac{1}{2}\sum_{k,l}\beta_{ij,k}b_{kl}(v_{l}-C_{l})\equiv-B^{\prime\prime}_{ij},$
$\displaystyle l_{i}\cdot l_{j}=$
$\displaystyle\alpha_{ij,k}a_{kl}(v_{l}-C_{l}).$

Thus

$P=\det(p_{i}\cdot
p_{j})\det\left(\alpha_{ij,k}a_{kl}(v_{l}-C_{l})-\sum_{mn}g_{mn}B^{\prime\prime}_{im}B^{\prime\prime}_{jn}\right).$
(3.7)

Comparing eq. 3.6 with eq. 3.7, we get eq. 3.4.

##  4 Discussion

The parametric representation is characterized by a polynomial
$\mathcal{F}(x)$. A transformation is applied to $\mathcal{F}$ and we get a
function $\mathcal{G}(u)$ (cf. eq. 2.3). This transformation is reciprocal.
Thus $\mathcal{F}$ and $\mathcal{G}$ are dual to each other. Similarly, the
Baikov’s representation is characterized by a polynomial $P$. It is shown that
$P$ equals $G|_{u_{n+1}=-1}$ up to a constant (cf. eq. 3.4).

In order to fully prove the equivalence of the parametric representation in
eq. 2.1 with the Baikov’s representation in eq. 3.2, it remains to express
$x^{\lambda}$ in terms of $u^{-\lambda-1}$. I believe that this should be a
consequence of eq. 2.2, but currently I can not figure out the details. So I
prefer to leave it for the future.

## Acknowledgments

This work is supported by the Natural Science Foundation of China (NSFC) under
the contract No. 11975200.

##  Appendix A Derivation of eq. (3.6)

By virtue of eq. 3.5, we have (In this section, summations over repeated
indices are always implied.)

$\displaystyle\beta_{ij,k}b_{kl}u_{l}\mathcal{F}=$
$\displaystyle\beta_{ij,k}b_{kl}\frac{\partial\mathcal{F}}{\partial x_{l}}$
$\displaystyle=$ $\displaystyle 2\tilde{A}_{ik}B_{kl}p_{l}\cdot
p_{j}-\beta_{ij,k}b_{kl}C_{l}U$ $\displaystyle=$ $\displaystyle
2\left(A^{-1}\right)_{ik}B_{kl}p_{l}\cdot
p_{j}u_{n+1}\mathcal{F}-\beta_{ij,k}b_{kl}C_{l}u_{n+1}\mathcal{F}.$

Thus we have

$B_{ij}=A_{ik}g_{jl}B^{\prime}_{kl}.$

Similarly,

$\displaystyle\alpha_{ij,k}a_{kl}u_{l}\mathcal{F}=$
$\displaystyle\alpha_{ij,k}a_{kl}\frac{\partial\mathcal{F}}{\partial x_{l}}$
$\displaystyle=$ $\displaystyle-U\left[p_{m}\cdot
p_{n}\left(A^{-1}\right)_{ik}\left(A^{-1}\right)_{jl}B_{km}B_{ln}+\alpha_{ij,k}a_{kl}C_{l}\right]$
$\displaystyle+\tilde{A}_{ij}\left[p_{k}\cdot
p_{l}\left(A^{-1}\right)_{mn}B_{mk}B_{nl}+x_{n+1}-C\right]$ $\displaystyle=$
$\displaystyle-\mathcal{F}u_{n+1}\left(g_{mn}B^{\prime}_{im}B^{\prime}_{jn}+\alpha_{ij,k}a_{kl}C_{l}\right)+\left(A^{-1}\right)_{ij}\mathcal{F}.$

That is

$\left(A^{-1}\right)_{ij}=\alpha_{ij,k}a_{kl}(u_{l}+u_{n+1}C_{l})+u_{n+1}g_{mn}B^{\prime}_{im}B^{\prime}_{jn}.$

Taking the determinant of both sides, we get

$\mathcal{G}=\mathcal{F}^{-1}=u_{n+1}U^{-1}=u_{n+1}\det\left[\alpha_{ij,k}a_{kl}(u_{l}+u_{n+1}C_{l})+u_{n+1}g_{mn}B^{\prime}_{im}B^{\prime}_{jn}\right].$

## References

  * [1] R.P. Feynman, _Space - time approach to quantum electrodynamics_ , _Phys. Rev._ 76 (1949) 769.
  * [2] Y. Nambu, _Parametric representations of general Green’s functions_ , _Nuovo Cim. C_ 6 (1957) 1064.
  * [3] N. Nakanishi, _General integral formula of perturbation term in the quantized field theory_ , _Progress of Theoretical Physics_ 17 (1957) 401.
  * [4] K. Symanzik, _Dispersion relations and vertex properties in perturbation theory_ , _Progress of Theoretical Physics_ 20 (1958) 690.
  * [5] R.N. Lee and A.A. Pomeransky, _Critical points and number of master integrals_ , _JHEP_ 11 (2013) 165 [1308.6676].
  * [6] R.N. Lee, _Modern techniques of multiloop calculations_ , in _49th Rencontres de Moriond on QCD and High Energy Interactions_ , pp. 297–300, 2014 [1405.5616].
  * [7] W. Chen, _Reduction of Feynman Integrals in the Parametric Representation_ , _JHEP_ 02 (2020) 115 [1902.10387].
  * [8] W. Chen, _Reduction of Feynman Integrals in the Parametric Representation II: Reduction of Tensor Integrals_ , _Eur. Phys. J. C_ 81 (2021) 244 [1912.08606].
  * [9] W. Chen, _Reduction of Feynman integrals in the parametric representation III: integrals with cuts_ , _Eur. Phys. J. C_ 80 (2020) 1173 [2007.00507].
  * [10] P.A. Baikov, _Explicit solutions of the three loop vacuum integral recurrence relations_ , _Phys. Lett. B_ 385 (1996) 404 [hep-ph/9603267].
  * [11] P.A. Baikov, _Explicit solutions of the multiloop integral recurrence relations and its application_ , _Nucl. Instrum. Meth. A_ 389 (1997) 347 [hep-ph/9611449].


# Optimized Generation of Entanglement by Real-Time Ordering of Swapping
Operations

Ranjani G. Sundaram  Stony Brook University, NY Himanshu Gupta  Stony Brook
University, NY

###### Abstract

Long-distance quantum communication in quantum networks faces significant
challenges due to the constraints imposed by the no-cloning theorem. Most
existing quantum communication protocols rely on the a priori distribution of
entanglement pairs (EPs), a process known to incur considerable latency due to
its stochastic nature. In this work, we consider the problem of minimizing the
latency of establishing an EP across a pair of nodes in a quantum network.
While prior research has primarily focused on minimizing the expected
generation latency by selecting static entanglement routes and/or swapping
trees in advance, our approach considers a real-time adaptive strategy—wherein
the order of entanglement-swapping operations (hence, the swapping tree used)
is progressively determined at runtime based on the runtime success/failure of
the stochastic events. In this context, we present a greedy algorithm that
iteratively determines the best route and/or entanglement-swapping operation
to perform at each stage based on the current network. We evaluate our schemes
on randomly generated networks and observe a reduction in latency of up to 40%
from the optimal offline approach.

##  I Introduction

Quantum networks enable the construction of large, robust, and more capable
quantum computing platforms by connecting smaller QCs. Quantum networks [17]
also enable various important applications [9, 13]. Quantum network
communication is challenging, as the physical transmission of quantum states
across nodes can incur irreparable communication errors due to quantum no-
cloning [7]. Thus, quantum protocols such as teleportation [1] or telegates
[6] are used to facilitate quantum communication or computation across nodes
in a quantum network; these protocols, however, require an a priori entangled
pair (EPs) shared across the end nodes. Our work focuses on efficiently
generating EPs in a quantum network.

Generating EPs over long distances in a quantum network is challenging. In
particular, coordinated entanglement swapping (e.g., DLCZ protocol [8]) using
quantum repeaters can be used to establish long-distance entanglements from
short-distance entanglements. However, due to the low probability of success
of the underlying physical processes, EP generation can incur significant
latency [15]; high generation latency of EPs can lead to high circuit
execution times and even defeat their purpose due to decoherence. Thus, this
paper considers the problem of generating EPs across remote nodes in a quantum
network with minimal latency.

Adaptive Generation of EPs. Prior work on efficient EP generation [3, 16, 14,
4, 11, 10] almost exclusively consists of offline approaches that select
static entanglement routes or swapping trees to minimize _expected_ generation
latency. These structures are constructed based on expected latencies and,
thus, may incur high latency at runtime depending on the actual outcomes of
the underlying stochastic events, as illustrated later (Example 2). In
contrast, a runtime-adaptive approach that selects the entanglement route
and/or the order of entanglement-swapping operations based on the outcomes of
the stochastic events during the generation process can potentially minimize
the runtime generation latency. Moreover, such adaptive approaches can also be
very effective in incorporating decoherence constraints due to the runtime
availability of actual ages of the qubits. Based on the above insights, in
this paper, we develop effective adaptive generation approaches to generate
EPs with minimal latency in quantum networks. To the best of our knowledge,
the only prior work that develops an adaptive EP generation approach is
[12]—but they assume a given entanglement path, and the time and space
complexity of their approach is exponential in the network size and thus
feasibly only for very small (at most 5-10 nodes) networks and low decoherence
times (see §VI).

Our Contributions. In the above context, we make the following contributions.

  * •

We first consider a simplified version of the problem where entanglement-
swapping operations can be performed along exactly one selected (entanglement)
path in the network. In this setting, we design an adaptive algorithm that, at
each stage, selects the best entanglement-swapping operation to be performed
based on the current network state (available EPs and their ages).

  * •

We also consider a generalized setting wherein the designed adaptive approach
selects, at each stage, the best route and the entanglement-swapping operation
to be performed based on the current network state.

  * •

We conduct extensive evaluations of our algorithms on a wide array of quantum
networks and observe a reduction in latency of up to $40\%$ compared to prior
static approaches.

##  II Background

This section presents the relevant background related to the generation of EPs
over remote nodes in a quantum network.

Quantum Network (QN). We consider a quantum network (QN) as a graph over the
set of quantum computers as network nodes. Each edge in the graph represents a
(quantum and classical) communication link. We refer to these network edges as
network links or just links. Our network model is similar to the one used in
some of the recent works [11, 10] on efficient generation of EPs and graph
states. In particular, each node has an atom-photon EP generator with latency
($t_{g}$) and probability of success ($p_{g}$). A node’s atom-photon
generation capacity/rate is its aggregate capacity and may be split across its
incident links. Each network link generates EPs (called link-EPs) shared over
the adjacent nodes using the nodes’ atom-photon generators and an optical-BSM
device located in the middle of the link. The optical-BSM has a certain
probability of success ($p_{ob}$), and each half-link (from either end-node)
to the device has a probability of transmission success ($p_{e}$). We
implicitly assume the atom-photon generation latency to include the times for
photon transmission, optical-BSM latency, and classical acknowledgment; thus,
the the generation latency of a link-EP is
$\mbox{$t_{g}$}/(\mbox{$p_{g}$}^{2}\mbox{$p_{e}$}^{2}\mbox{$p_{ob}$})$ between
two nodes. To facilitate atom-atom ES operations, each network node is also
equipped with an atomic-BSM device with appropriate operation latency $t_{b}$
and probability of success $p_{b}$.

Generating EPs over Remote Nodes. To distribute an EP over remote nodes, EPs
are generated over larger and larger distances from shorter-distance EPs using
a sequence of “entanglement-swapping” operations. An entanglement swapping
(ES) operation can be looked up as being performed over three nodes $(A,B,C)$
with two EPs over $(A,B)$ and $(B,C)$; the ES operation results in an EP over
the nodes $(A,C)$, by essentially teleporting the first qubit in node $B$
(i.e., the qubit of the EP over $(A,B$)) to the node $C$ using the second EP
over $(B,C)$. In general, an EP over a pair of remote nodes $A$ and $B$ can be
generated by a sequence of ES operations over the EPs over adjacent nodes
along a path from $A$ to $B$.

Figure 1: Establish EPs over remote nodes.

Swapping Trees. In recent work, [11] introduces the concept of _swapping
trees_ , which are a characterization of the different orderings of ES
operations that can be used to establish an EP over the endpoints of a network
path. Given a path $P$ with endpoints $s$ and $d$, any complete binary tree
over the ordered links in $P$ gives a way to generate an EP over $(s,d)$. Each
vertex in the tree corresponds to a pair of network nodes in $P$, with each
leaf representing a link (See Fig 1). The latency of a swapping tree is the
_expected_ time taken to establish the EP corresponding to the tree’s root
node.

Decoherence Threshold Time $\tau$. The fidelity of the quantum state decreases
over time due to interaction with the environment; this is called decoherence.
In order to limit the decoherence of qubits in an EP, we enforce an upper
bound on the age (time spent in a quantum memory) of the qubits involved. A
qubit is said to satisfy the decoherence constraint if its age is below a
decoherence threshold of $\tau$.

##  III Problem Formulation and Related Work

We start by formulating the real-time111We use real-time and runtime
interchangeably, in this paper. entanglement generation problem addressed in
this paper. We now consider entanglement generation over a single path in the
network; we will consider the more general multi-path problem later in §V.

SP-SWO Problem (Single-Path Swap Ordering). Given a quantum network and a
source-destination pair $\\{(s,d)\\}$, the SP-SWO problem is to determine a
path $P$ from $s$ to $d$ and a real-time (during EP generation) ordering of
the entanglement-swapping (ES) operations so as to minimize the actual
generation latency of the target EP $(s,d)$ under the below node and
decoherence constraints.

  1. 1.

Node Constraints. For each node, the aggregate resources used (in generating
the link-EPs) are less than the available resources.

  2. 2.

Decoherence Constraints. The age of any qubit is less than the decoherence
threshold $\tau$.

Related Work In recent years, a significant amount of work has been done on
efficiently generating remote EPs in a quantum network. Below, we discuss
these works categorized as follows.

Selection of Entanglement Routes. Most of the work on efficient generation of
EPs in quantum networks focuses on selecting one or more entanglement
paths/routes [3, 16, 14, 4]. These works typically assume that the underlying
processes, including link-EP generation and atomic BSMs, are synchronized; if
all of these processes along the chosen entanglement route succeed, the end-
to-end EP is generated. On failure of any of the underlying processes (atomic
BSM or link-EP generation), all the generated link/subpath-EPs are discarded,
and the whole process starts again from scratch. Such approaches require no
quantum memories or require only memories with minimal storage time. In
particular, [16] designs a Dijkstra-like algorithm to construct an optimal
path between a pair of nodes when there are multiple channels between adjacent
nodes; they generalize their techniques to also select multiple paths over
multiple pairs of nodes. In addition, [3] designs a linear programming (LP)
formulation based on multi-commodity flow to select routing paths for a given
set of source-destination pairs; they map the operation-based fidelity
constraint to the path length and use copies of nodes to model the fidelity
constraint in the LP. Among earlier works, [14] proposes a greedy solution for
grid networks, and [5] proposes virtual-path-based routing in ring/grid
networks.

Constructing Swapping Trees. In networks with memories at nodes, a qubit of an
EP may wait (in a quantum memory) for its counterpart to become available so
that an ES operation can be performed. In such approaches, as mentioned in the
previous section, the goal is to determine a swapping tree that essentially
represents the order in which ES operations must be performed along the
selected entanglement path. In particular, [2] formulated the entanglement
generation rate on a given path between two nodes and then used the formulated
path metric to select the optimal path exhaustively; their path metric is
based on balanced swapping trees. In more recent work, [11] develops a dynamic
programming approach to determine the swapping tree with minimum expected
generation latency, under node and decoherence constraints, for generating an
EP over a given source-destination pair.

Real-Time Determination of Swapping Order. The above works seek to minimize
the expected latency of generating the target EP by selecting one or more
static swapping trees up front. However, as discussed in the previous section,
an optimal entanglement route or swapping tree may incur high generation
latency at runtime depending on the outcome of the link-EP generation attempts
and/or ES operations. Thus, an adaptive strategy that determines the (order
of) ES operations in runtime can outperform fixed swapping trees (see Example
2). With the above insight, a recent work [12] considers the problem of
minimizing the runtime latency of generating an EP over a pair of nodes using
a given path. They formulate the problem as a Markov Decision Process wherein
each state corresponds to each possible network state (available EPs with
ages), and develop an optimal state transition policy. However, their
algorithm takes exponential time and space—and is feasible only for very small
networks (at most 5-10 nodes) and low decoherence times (see §VI). Our work is
inspired by the above work.

##  IV Greedy-SP Algorithm

We describe our proposed Greedy-SP algorithm for the SP-SWO problem. We start
by describing a high-level idea of the algorithm.

Figure 2: (a). Path $(x_{1},\ldots,x_{4})$ with expected (green) and actual
(at runtime, in red) generation latencies of the link-EPs. (b) Optimal
swapping tree that minimizes the expected generation latency of the EP over
$(x_{1},x_{4})$. Here, the green values are the expected generation latencies
of the EP at each vertex, and the red values are the actual generation
latencies. (c) Alternate swapping tree with sub-optimal expected generation
latency but with lower runtime generation latency compared to the swapping
tree in (b).

Basic Idea. The basic idea behind Greedy-SP is to first select a path of
minimum expected generation latency over the $(s,d)$ pair, and, then, at each
event (as defined below), pick the ES $X$ that minimizes the expected latency
(after performing $X$) of generating an EP across $(s,d)$. More elaborately,
we first use the optimal dynamic programming algorithm of [11] to determine
the swapping tree with the lowest expected latency of establishing an EP
across $(s,d).$ We select the path $P$ corresponding to the leaf nodes of this
optimal swapping tree, as the entanglement path to generate the EP over
$(s,d)$. Initially, we start generating link-EPs over network links on $P$.
Then, whenever a (link or subpath) EP over this path $P$ is generated or
destroyed or a sufficient amount of time has passed, we make a determination
to either perform an ES operation or wait. This determination is made by
considering all possible ES operations available at the given point of time,
and for each potential ES $X$, estimating the minimum latency of generating
the target EP over $(s,d)$ if the ES $X$ is performed. Before presenting the
pseudo-code, we discuss two concepts.

Active Links and Trigger Events. A link may be _active_ or inactive; an active
link continuously attempts to generate a link-EP over it. Our motivation for
inactivating links, as needed, is two-fold: (i) Inactivating a link limits the
memory requirements at each network node to at most two; (ii) Allowing a link
to continue to generate link-EPs while a derived EP exists—leads to existence
of multiple EPs over a pair of nodes with potentially different ages; handling
such a generalized network state in our algorithm above is very challenging,
and is deferred to our future work.

In our context, the _trigger events_ are: (i) Generation of a new EP, (ii)
Destruction of an EP (due to decoherence or ES failure), (iii) Passage of
“sufficient” time after a trigger event. The motivation behind the last
trigger event is to re-determine, based on the updated ages of available EPs,
if some pair of available EPs should be swapped. We thus pick the “sufficient
time” to be $50\mu s$, which is equal to half of the time it takes to attempt
a link-EP generation. Thus, if $50\mu s$ passes without an event being
triggered, then we trigger the passage of sufficient time event.

Greedy-SP Algorithm Pseudo Code.

Inputs: (i) A quantum network, a pair of network nodes $(s,d)$.

Output: An EP over $(s,d)$ with minimum generation latency.

Algorithm.

  1. 1.

Determine the routing path $P$ from the optimal swapping tree over $(s,d)$
obtained using DP from [11] (see §IV-A).

  2. 2.

Turn all links on $P$ active.

  3. 3.

Continuously (try to) generate a link-EP across all active links in $P$.

     * •

Once a link-EP $E$ is generated over a link $e$, make $e$ inactive. The link
$e$ is activated again when either $E$ or an EP derived from $E$ (via ESs) is
destroyed (due to decoherence or ES failure).

  4. 4.

On one of the trigger events (as defined above), do:

    1. (a)

Call swap-or-wait (see below) to determine which of the available pair of EPs
to swap or wait (for the next trigger event).

    2. (b)

Perform the ES operation or wait based on (a).

swap-or-wait Subroutine.

Inputs: (i) Set of available EPs (with ages of their qubits), and (ii) Set of
active links and the duration for which they have been generating EPs.

Outputs: Either a pair of available EPs that should be ES-ed next, or wait.

Algorithm.

  1. 1.

Let $\mathcal{E}\leftarrow$ {Set of available EPs } $\cup$ {EPs corresponding
to active links}

  2. 2.

For each pair of EPs $(E_{1},E_{2})$ from $\mathcal{E}$ that can be swapped,
do:

    1. (a)

Using DP-with-ages (§IV-A), determine the minimum expected latency
$L_{E_{1},E_{2}}$ of generating the final EP over $(s,d)$, if $(E_{1},E_{2})$
EPs are swapped.

  3. 3.

Pick $(E_{1},E_{2})$ corresponding to the lowest $L_{E_{1},E_{2}}$. If both
$E_{1}$ and $E_{2}$ are available, return $(E_{1},E_{2})$, else return wait.

###  IV-A DP-with-ages: Estimating Minimum Latency

In [11], the authors develop a dynamic programming (DP) algorithm to determine
an optimal (i..e, with minimum expected generation latency) swapping tree to
generate an EP over a given source-destination pair in a quantum network. For
our purposes of estimating the minimum latency, given a set of available EPs
and the next ES operation, we need to modify the DP algorithm of [11]
appropriately. We briefly describe the original DP algorithm of [11] and then
discuss its modification.

DP Algorithm [11]. Consider a quantum network with nodes
$V=\\{1,2,\ldots,n\\}$, and a pair $(s,d)$ of source-destination nodes over
which we want to generate an EP with minimum expected latency. The work in
[11] develops a dynamic programming (DP) algorithm (referred to as DP, here)
that constructs a swapping tree $X$ over a path connecting $s$ and $d$ such
that $X$ incurs minimum generation latency. The DP algorithm is based on a
recursive formula governing the generation latency of swapping trees under
certain reasonable assumptions. In particular, let $T[i,j,h]$ represent the
optimal expected latency of generating EP pairs over $(i,j)$ using a swapping
tree of height at most $h$. Then, we have:

$\displaystyle T[i,j,0]$
$\displaystyle=\frac{\mbox{$t_{g}$}}{\mbox{$p_{g}$}^{2}\mbox{$p_{ob}$}}\text{
for adjacent nodes }(i,j).$ $\displaystyle T[i,j,h]$
$\displaystyle=\min(T[i,j,h-1],(\frac{3}{2}B+\mbox{$t_{b}$})/\mbox{$p_{b}$}),\text{
where}$ $\displaystyle B$ $\displaystyle=\min\limits_{k\in
V}\max(T[i,k,h-1],T[k,j,h-1])$

The above equations can be used to compute the optimal generation latency as
well as the corresponding optimal swapping tree. The authors in [11] also
incorporate decoherence and other constraints in the above algorithm. In
particular, to incorporate decoherence constraints, [11] introduces four
additional parameters to the above function $T[]$, corresponding to the depths
of the four grandchildren of a swapping tree’s root. We refer the reader to
[11] for more details.

DP-with-ages: Incorporating Ages of Available EPs. The above-described DP
starts with a “base state” wherein the network links have not yet started
generating the corresponding link-EPs. In contrast, in our context, we need to
estimate the minimum generation latency of the target EP (see Line 2(a) of
Algorithm swap-or-wait) when some of the EPs are already available—and more
importantly, may be of non-zero ages. To estimate the optimal generation
latency for such a generic network state (i.e., with already available EPs),
we divide the entire possible age-range $[0,\tau]$ of a qubit into
sufficiently many (we use 100) subranges and estimate the minimum generation
latency of the target EP for each age-range recursively (using dynamic
programming) as described below. In particular, let $T[i,j,h,a]$ represent the
minimum expected latency of generating an EP pair over $(i,j)$ using a
swapping tree of height at most $h$ such that the age of the target EP is
within the age-interval $a$. Then, we have:

$\displaystyle T[i,j,0,a]=0,\text{if}\ (i,j)\ \text{is an available {\tt EP}
of age in interval $a$}.$ $\displaystyle
T[i,j,0,[0,x]]=\frac{\mbox{$t_{g}$}}{\mbox{$p_{g}$}^{2}\mbox{$p_{ob}$}}-t\text{
for adjacent nodes (i,j)\ \text{where $t$}}$ is the time already spent
generating a link-EP over $(i,j)$ and $[0,x]$ is the first subrange of
$[0,\tau]$. $\displaystyle
T[i,j,h,a]=\min(T[i,j,h-1,a],(\frac{3}{2}B+\mbox{$t_{b}$})/\mbox{$p_{b}$}),\text{
where}$ $\displaystyle B=\min\limits_{k\in V,a_{i}\leq a,a_{j}\leq
a}\max(T[i,k,h-1,a_{i}],T[k,j,h-1,a_{j}])$

##  V Multi-Path Generalization

In this section, we consider the generalization of the SP-SWO problem wherein
we allow for multiple entanglement paths for generating EPs over a given
$(s,d)$ pair.

Motivation. In a large quantum network, there may be multiple paths available
for independent generation of the desired remote EP, and the stochasticity of
the processes imply that using multiple paths can result in lower expected
latency (any one of the paths needs to succeed). Thus, many works have
considered multi-paths [11, 10] for entanglement generation. In our context,
we generalize the SP-SWO problem for multi-paths, i.e., for real-time
determination of entanglement path and ES operations during the course of EP
generation.

MP-SWO Problem (Multi-Path Swapping Order). Given a quantum network and a
source-destination pair $\\{(s,d)\\}$, the MP-SWO problem is to determine the
choice of entanglement path and ordering of ES operations (in real-time as the
EPs are generated) so as to minimize the actual/real-time generation latency
of an EP $(s,d)$ under the decoherence and node constraints (as defined in SP-
SWO problem formulation).

Multi-Path Optimal Static Approach. In recent work, [11] presents a linear
programming (LP) based algorithm (referred to as LP, here) for constructing an
“aggregated” structure of multiple swapping trees that yields an optimal
generation rate of EP over a given source-destination pair. Their technique is
based on constructing an appropriate hypergraph that has embedded in it all
possible swapping trees in the given quantum network, and then developing a
linear program to determine the optimal hyperflow in the constructed
hypergraph; the optimal hyperflow essentially represents the optimal
“aggregated” tree structure for the generation of EPs over the given source-
destination pair. We use the above approach as a baseline and develop a real-
time ES-ordering approach as described below.

Greedy-MP Algorithm for MP-SWO. We utilize the LP algorithm above first to
obtain multiple paths (not necessarily disjoint) from $s$ to $d$ that
can/should be used to establish EPs $(s,d)$; these paths can be obtained by
extracting a sufficient number of swapping trees from the LP “aggregated tree”
solution. Then, we proceed similarly to the previous Greedy-SP algorithm for
the single path. In particular, as in Greedy-SP, we activate all the links and
continuously attempt to generate link-EPs over them. Then, on any trigger
event (as defined before), we call the swap-or-wait procedure on each of the
paths independently to determine the best pair of EPs to swap (or wait) on
each path. Since the paths may not be disjoint, the best pair of EPs chosen
for a path may involve EPs that are part of multiple paths. Thus, we sort
these best pairs from the paths based on the expected generation latencies of
the corresponding paths and perform the swaps in that order (as long as the
required EPs haven’t been consumed by a previous swap). We describe this
formally in the below pseudo code. The algorithm terminates when an EP has
been established across $(s,d)$.

Greedy-MP Psuedo-Code.

Inputs: (i) A quantum network, and a source-destination pair $(s,d)$.

Output: An EP over the nodes $(s,d)$ in minimum latency.

Algorithm.

  1. 1.

Select a set of routing paths $\\{P_{i}\\}_{[k]}$ using LP, as described
above.

  2. 2.

Turn on all links in each $P_{i}$ as active.

  3. 3.

Continuously (try to) generate a link-EP across all active links in each
$P_{i}.$

     * •

Once a link EP $E$ is generated over a link $e$, make $e$ inactive. The link
$e$ is activated again when either $E$ or an EP derived from it (via ESs) is
destroyed (due to decoherence or ES failure).

  4. 4.

On one of the trigger events, do

    1. (a)

For each path $P_{i}$ independently, use swap-or-wait (§IV) to determine the
pair of EPs $D_{i}$ to be swapped next. Let $L_{i}$ be the expected generation
latency of the target EP over path $P_{i}$ after performing $D_{i}$. If
$D_{i}$ is null (i.e., when wait is returned), then let $L_{i}$ be infinity.

    2. (b)

Traverse the $D_{i}$’s in ascending order of $L_{i}$’s, and perform the ES
corresponding to each $D_{i}$ only if neither of the EPs in $D_{i}$ have been
consumed by a $D_{j}$.

##  VI Evaluation

This section evaluates our algorithm on different network graphs with varying
parameters.

Algorithms Compared. For the SP-SWO problem, we compare four algorithms: (i)
Greedy-SP from §IV; (ii) Optimal dynamic programming algorithm (DP) from [11]
which returns an optimal static swapping tree; (iii) Swap-ASAP from [12],
which performs an ES operation over EPs as soon as any are available; (iv)
Markov Decision Process based (MDP) algorithm from [12]. For the multi-path
MP-SWO problem, we compare two algorithms: (v) Greedy-MP from §V; (vi) LP from
[11] (see §V).

Figure 3: SP-SWO (single-path) Problem. EP generation latency of various
algorithms, for small networks (5 nodes) and small decoherence times
($1.5\text{\times}{10}^{-4}$ (left) and $3\text{\times}{10}^{-4}$ (right)
seconds), for varying node EP-generator’s success probabilities.

Figure 4: SP-SWO (single-path) Problem. EP generation latency of various
algorithms, Swap-ASAP, DP, and Greedy-SP, for varying parameters. MDP is not
shown due to its prohibitive runtime for these parameter values (see text).

Figure 5: MP-SWO (multi-path) Problem. EP generation latencies of Greedy-MP
and LP for varying parameters.

Implementation Details. Given a quantum network and a single $(s,d)$ pair, DP
picks a static swapping tree of minimum expected latency and performs swap
operations in the order given by the tree. MDP maintains a state of all
possible EPs over all possible ages, resulting in a state space of size
$\mathcal{O}(t^{n})$, where $n$ is the number of nodes in the network and
$t=2\tau/3\mbox{$t_{g}$}$ is a discretized representation of the decoherence
threshold. It then pre-computes a policy that, for each state, returns an
action: wait or perform a certain swapping operation. Given a network path and
an objective of establishing an EP across the end nodes, Swap-ASAP
continuously attempts link generation of active links. When a pair of EPs that
can be swapped become available, Swap-ASAP swaps them. Note that both MDP and
Swap-ASAP take a network path rather than a network graph as input; thus, as
for the case of Greedy-SP, they operate on the path corresponding to the
optimal swapping tree of DP. In all approaches, the links become active or
inactive as in our approaches Greedy-SP and Greedy-MP.

Generating Random Networks. We use a quantum network spread over an area of
$100km\times 100km$. We use the Waxman model [18], which has been used to
create Internet topologies. We vary the number of nodes in the network from
$20$ to $60$, with $40$ as the default value. We generate random networks by
varying the following parameters.

  * •

Number of nodes (default = $40$)

  * •

Swapping success probability $p_{ob}$ (default = 0.5)

  * •

Node EP-generator’s success probability $p_{g}$ (default = 0.5)

  * •

Decoherence threshold $\tau$ (default = $1.5s$)

  * •

Physical distance between the source-destination pair $s$ and $d$ (default =
20-50km).

In all graphs, each data point is the average generation latency of $10$ runs
of the corresponding algorithm on a set of input parameters.

Evaluation Results. For the single-path (SP-SWO) problem, we evaluate the four
algorithms on inputs generated by varying the parameters described above. We
note that MDP takes prohibitively long to run on paths with more than $7$
nodes or settings with decoherence time more than $3\text{\times}{10}^{-4}$
sec with paths of more than $5$ nodes. Thus, we evaluate MDP on small networks
with $5$ nodes and two decoherence times, viz., 0.15ms and 0.3ms. See Figs
3-3. For such small networks, we observe that MDP performs the best, as
expected, as it is the optimal algorithm. However, we note that Greedy-SP also
performs very close to the optimal MDP for $\mbox{$p_{g}$}\geq 0.6$ values.
For larger networks (Figs 4-4), we observe that Greedy-SP consistently
performs better than DP and Swap-ASAP for most instances; in particular, it
achieves generation latencies of up to $40\%$ lower than the optimal static
approach (DP) and up to $45\%$ lower than the naive adaptive approach Swap-
ASAP. Finally, for the multi-path (MP-SWO) problem, we compare the adaptive
Greedy-MP and the static-optimal LP approaches. See Figs. 5-5. We observe that
Greedy-MP performs 10-20% better than LP in most cases.

Runtime Overhead. The running time of the selection phase of our Greedy-SP and
Greedy-MP algorithms is 100 $\mu$s and 700 $\mu$s for the default parameter
values on an 8-core Intel Core i7-11700 system. Since the selection phase
involves computing the expected latency for each possible choice
independently—the running time can be easily parallelized and reduced to the
order of a few $\mu$s. Thus, the running overhead of our approaches has
minimal impact on the decoherence of qubits (since realistic values of
decoherence times is of the order of several seconds) and generation latency
(which is of the order of 10s-100s of milliseconds).

##  VII Conclusion

In this work, we have developed an adaptive EP generation algorithm that
chooses the entanglement route and/or swapping operations at EP-generation
time, based on the network state at the time. In our future work, we seek to
extend our work in the following ways: (i) Consider multiple source-
destination pairs; (ii) Continuous generation of EPs with node-memory
constraints; (iii) Consider discarding EPs that are likely to decohere before
the target EP can be generated.

## References

  * [1] Charles H Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K Wootters.  Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels.  Physical review letters, 70(13):1895, 1993.
  * [2] Marcello Caleffi.  Optimal routing for quantum networks.  IEEE Access, 2017.
  * [3] Kaushik Chakraborty, David Elkouss, Bruno Rijsman, and Stephanie Wehner.  Entanglement distribution in a quantum network: A multicommodity flow-based approach.  IEEE Transactions on Quantum Engineering, 1:1–21, 2020.  URL: https://api.semanticscholar.org/CorpusID:219124346.
  * [4] Kaushik Chakraborty, Filip Rozpdek, Axel Dahlberg, and Stephanie Wehner.  Distributed routing in a quantum internet.  ArXiv, abs/1907.11630, 2019.
  * [5] Kaushik Chakraborty, Filip Rozpedek, Axel Dahlberg, and Stephanie Wehner.  Distributed routing in a quantum internet, 2019.
  * [6] Daniele Cuomo, Marcello Caleffi, Kevin Krsulich, Filippo Tramonto, Gabriele Agliardi, Enrico Prati, and Angela Sara Cacciapuoti.  Optimized compiler for distributed quantum computing.  ACM Transactions on Quantum Computing, 4(2), feb 2023.
  * [7] DGBJ Dieks.  Communication by epr devices.  Physics Letters A, 92(6):271–272, 1982.
  * [8] L-M Duan, Mikhail D Lukin, J Ignacio Cirac, and Peter Zoller.  Long-distance quantum communication with atomic ensembles and linear optics.  Nature, 414(6862):413–418, 2001.
  * [9] Zachary Eldredge, Michael Foss-Feig, Jonathan A Gross, Steven L Rolston, and Alexey V Gorshkov.  Optimal and secure measurement protocols for quantum sensor networks.  Physical Review A, 97(4):042337, 2018.
  * [10] Mohammad Ghaderibaneh, Himanshu Gupta, and CR Ramakrishnan.  Generation and distribution of ghz states in quantum networks.  In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 1120–1131. IEEE, 2023.
  * [11] Mohammad Ghaderibaneh, Caitao Zhan, Himanshu Gupta, and C. Ramakrishnan.  Efficient quantum network communication using optimized entanglement-swapping trees.  12 2021.
  * [12] Álvaro G Iñesta, Gayane Vardoyan, Lara Scavuzzo, and Stephanie Wehner.  Optimal entanglement distribution policies in homogeneous repeater chains with cutoffs.  npj Quantum Information, 9(1):46, 2023.
  * [13] Peter Komar, Eric M Kessler, Michael Bishof, Liang Jiang, Anders S Sørensen, Jun Ye, and Mikhail D Lukin.  A quantum network of clocks.  Nature Physics, 10(8):582–587, 2014.
  * [14] Mihir Pant, Hari Krovi, Don Towsley, Leandros Tassiulas, Liang Jiang, Prithwish Basu, Dirk Englund, and Saikat Guha.  Routing entanglement in the quantum internet.  npj Quantum Information, 08 2017.
  * [15] Nicolas Sangouard, Christoph Simon, Hugues De Riedmatten, and Nicolas Gisin.  Quantum repeaters based on atomic ensembles and linear optics.  Reviews of Modern Physics, 83(1):33, 2011.
  * [16] Shouqian Shi and Chen Qian.  Concurrent entanglement routing for quantum networks: Model and designs.  SIGCOMM ’20, New York, NY, USA, 2020. Association for Computing Machinery.  URL: https://doi.org/10.1145/3387514.3405853.
  * [17] Christoph Simon.  Towards a global quantum network.  Nature Photonics, 11(11):678–680, 2017.
  * [18] Bernard M Waxman.  Routing of multipoint connections.  IEEE journal on selected areas in communications, 6(9):1617–1622, 1988.