# Maximizing Entanglement Routing Rate in Quantum Networks: Approximation
Algorithms

Tu N. Nguyen, , Dung H. P. Nguyen, Dang H. Pham, Bing-Hong Liu, and Hoa N.
Nguyen  T. N. Nguyen is with the Department of Computer Science, Kennesaw
State University, Marietta, GA 30060, USA (e-mail: tu.nguyen@kennesaw.edu). D.
H. P. Nguyen and B.-H. Liu are with the Department of Electronic Engineering,
National Kaohsiung University of Science and Technology, Kaohsiung 80778,
Taiwan (e-mail<EMAIL_ADDRESS>and bhliu@nkust.edu.tw). D. H. Pham
and H. N. Nguyen are with the Department of Information Systems, VNU
University of Engineering and Technology, Hanoi 10000, Vietnam (e-mail:
<EMAIL_ADDRESS>and hoa.nguyen@vnu.edu.vn). Corresponding author: Tu N.
Nguyen

###### Abstract

There will be a fast-paced shift from conventional network systems to novel
quantum networks that are supported by the quantum entanglement and
teleportation, key technologies of the quantum era, to enable secured data
transmissions in the next-generation of the Internet. Despite this prospect,
migration to quantum networks cannot be done at once, especially on the aspect
of quantum routing. In this paper, we study the maximizing entangled routing
rate (MERR) problem. In particular, given a set of demands, we try to
determine entangled routing paths for the maximum number of demands in the
quantum network while meeting the network’s fidelity. We first formulate the
MERR problem using an integer linear programming (ILP) model to capture the
traffic patent for all demands in the network. We then leverage the theory of
relaxation of ILP to devise two efficient algorithms including HBRA and RRA
with provable approximation ratios for the objective function. To deal with
the challenge of the combinatorial optimization problem in big scale networks,
we also propose the path-length-based approach (PLBA) to solve the MERR
problem. Using both simulations and an open quantum network simulator platform
to conduct experiments with real-world topologies and traffic matrices, we
evaluate the performance of our algorithms and show up the success of
maximizing entangled routing rate.

###### Index Terms:

demand, entanglement, entangled pair, quantum networks, qubit.

##  I Introduction

The quantum mechanic appears as a promising technology to enable the secured
quantum key distribution [Bennett_2014], distributed quantum computation
[10.1145/1412700.1412718, 10.1145/3233188.3233224], clock synchronization
[komar2014quantum], and many other applications [singh2021quantum]. The common
characteristic of such applications is the requirement of entangled pairs or
EPR pairs [PhysRevLett.70.1895] between two distant quantum computers
[PhysRevLett.86.5188]. This is the reason that results in the emerging of
quantum networks. The stages of the quantum network development were indicated
together with several applications in [doi:10.1126/science.aam9288], and study
[10.1145/3341302.3342070] initially proposed a protocol for the link layer of
the network. Furthermore, some networks have been constructed in several
countries in practice [10.1145/3387514.3405853, 10.1145/3465481.3470056],
demonstrating the feasibility of the quantum network.

However, like other state-of-the-art technologies, the quantum network must
cope with many challenges in the first growth stage [8910635]. Two of them
come from entanglement and swapping [PhysRevLett.70.1895], which are the
fundamental steps to create an EPR pair between two end nodes
[doi:10.1126/science.aam9288], the stations where we run applications.
Entanglement is the first step in the process of generating EPR pairs, where
two quantum bits [10.1145/3341302.3342070] (or qubits in short) in adjacent
nodes establish entanglement states over quantum channels to create quantum
links, also called the external links. Each quantum link is generated
successfully with a specific probability depending on many factors. One of
which is the distance between two nodes; due to the inherent characteristic of
signal amplitude decay along the transmission line, which is the optical fiber
or free space in this situation, the longer distance, the lower the success
probability. Fortunately, we can enhance the probability by attempting many
photon pairs with different frequencies simultaneously; the external link will
be generated when one out of the pairs establishes entanglement successfully
[9210823]. In addition, to overcome the difficulty of distance, one utilizes
intermediate nodes, also called the quantum repeaters
[10.1145/3341302.3342070, pirandola2017fundamental] (or repeaters in short).
In the second step, based on the end-to-end paths obtained from the routing,
every two qubits inside the intermediate nodes swap together to create
internal links, which combines with the external links to form end-to-end
entanglement. But as we will see in the next part, using too many repeaters
will significantly affect the quality of entanglement. Both entanglement and
swapping are probability processes. Therefore, the network is only determined
after entanglement, and even when the network is identified, we still cannot
guarantee the success of creating entangled pairs between two end nodes. In
this paper, one node in the network can imply either an end node or a
repeater. Due to the limitation of fabrication technology, quantum nodes are
currently equipped with only a few qubits [10.1145/3341302.3342070], hence
confining the capacity of the network. In addition, the network deployment
challenges [8910635] also affect the scalability of quantum network
infrastructures such as quantum nodes and channels.

One way to increase the probability of success is to find multiple connections
between two end nodes [10.1145/3387514.3405853, li2021effective,
pant2019routing]. Nevertheless, owing to the limitation of network resources,
such as network infrastructure and the number of qubits inside a quantum node,
this approach is not feasible in the case of multiple requests for generating
entangled pairs at the same time. Because looking for multiple paths to meet
one request may rapidly exhaust the network resources, which results in
reducing network responsiveness. Instead, we are interested in leveraging the
available resources to satisfy as many requests simultaneously as possible.

The fidelity of an EPR pair is a vital metric that indicates the quality of
entanglement. A higher fidelity, which means higher quality, results in a
lower qubit error rate. The fidelity can alter from $0$ to $1$, but the
desirable threshold is $0.5$. Error detection can work effectively with
greater fidelity than this threshold [10.1145/3341302.3342070,
van2014quantum]. One factor influencing end-to-end fidelity is the length of
the connection path between the two end nodes due to the degrading fidelity
after each swapping [9210823]. Therefore, to guarantee EPR pair quality to
perform quantum applications, we need to confine the path length connecting
two end nodes in terms of the number of hops. In fact, we can improve fidelity
by entanglement purification [doi:10.1126/science.aan0070], but some types of
quantum repeaters do not support this method. Moreover, this technique
consumes network resources, where we have to sacrifice one or more quantum
links.

On these bases, this study investigates the optimal techniques to meet as many
demands of generating entangled pairs as possible while confining the length
of the connecting path to guarantee the fidelity of the pairs.

Motivation: Quantum networks face with the problem of forming entangled
routing paths to connect demands (source-destination pairs) in the network. A
routing path in the conventional network can be constructed easily based on
the topology of the network [8556039, 8422617]. However, it is not the case in
quantum networks since the routing paths must be entangled paths, so that we
have to consider not only the conventional network resources (i.e., nodes and
links) but also qubits and their entanglement relations
[10.1145/3387514.3405853, 9210823]. As the number of demands increases, the
more number of entangled paths is needed as well. Hence, it is critical to
perform dynamic traffic engineering. To enhance the traffic engineering, it is
important to enable maximum number of demands connected by entangled routing
paths. In other worlds, we try to maximize the entangled routing rate for
quantum networks.

Challenges: In summary, the maximizing entangled routing rate (MERR) problem
has to address the following questions and aspects.

  * •

How to design a fast algorithm to respond to the degradation of entangled
links between qubits. In particular, the designed algorithm is expected to
perform not only close optimal but also fast in terms of computation time.

  * •

How many demands to connect in each period? Should their entangled routing
paths are enabled at once?, and which specific qubits to be included in the
paths? In addition, we have to ensure that each entangled routing path is
short enough to meet the fidelity condition.

  * •

Another challenge is that how to set up the real-world quantum network
environment and then actually implement the proposed algorithm with
appropriate metrics to evaluate its performance.

Methodology and Contributions: We develop a methodology to address the above
question posed by the next-generation network systems regarding entanglement
routing. We introduce a model of qubit entanglement general enough to
determine routing paths to connect demands. We then utilize this model to
derive the optimal scheduling for qubit entanglement using the integer
programming and different rounding techniques. The objective is mainly to
maximize the entangled routing rate for the network. We show that the
investigated problem is NP-hard and present the detailed algorithm with the
best possible approximation ratio. We evaluate the performance of the proposed
algorithms using both simulations and experiments that are implemented using
the quantum network simulator, NetSquid [netsquid].

  * •

Maximizing Entangled Routing Rate Problem. We introduce the problem of qubit
entanglement scheduling, using general models of shared resources in quantum
networks. Moreover, we also study the hardness of the MERR problem.

  * •

Technique. For the objective of maximizing entangled routing rate through the
availability of qubit-enabled routing paths, we show that the optimization
problem can be approached using the integer programming. We then present an
approximation algorithm by using different rounding techniques.

  * •

Real-world-based Evaluation. We evaluate the proposed algorithms using real-
world network topologies and traffic matrices. Evaluation results show that
our approach can significantly increase the entangled routing rate for the
network. Analyses of the proposed algorithms are also provided to verify their
performance.

Organization: The rest of the paper is organized as follows. In $\S$II, we
present the related studies on quantum network routing. In $\S$III, we
illustrates the system model and formally states the research problem. We
describe our methods and provide the analysis of the algorithms in $\S$IV and
$\S$V, respectively. The experiment results are expressed in
$\S$LABEL:sec:sim. We discuss the appropriation of the proposed techniques
with a realistic network in $\S$LABEL:sec:discussion. Finally, in
$\S$LABEL:sec:conclusion, we presents the conclusion and future works.

##  II Related Works

Quantum applications have laid the foundation for the development of quantum
networks. The emergence of the first quantum networks was intended for quantum
key distribution (QKD) [Bennett_2014], a secure application in information
exchange. These networks are presented in studies [elliott2002building,
Peev_2009, Sasaki:11]. This is inherently the beginning of the revolution.
With the development of science and technology, quantum computers are
gradually being realized [8910635], promising to exploit more quantum
applications. This is also the basis for the strong development of quantum
networks in the future.

Similar to the traditional network, the routing problem is one of the serious
problems in the quantum network. Several works have initially studied this
issue in different approaches. The first concern is the solution for
increasing the success probability of entanglement and swapping, as well as
ensuring the quality of entanglement. This problem can be addressed by finding
the shortest path from the source node to the destination node of a demand.
Research [van2013path] is one of the first works to study the path selection
in quantum networks using the traditional Dijkstra’s algorithm. They define a
link cost metric for the first time in quantum networks. They also present a
deep analysis of the complexity of quantum networks compared with conventional
networks. Study [8068178] proposes a more complicated routing metric taking
into account some physical factors, such as decoherence time and imperfect
Bell state measurement. Both [van2013path] and [8068178] assume that there is
only one request for generating the EPR pair at a specific time. This is basic
but not practical because, along with the growth of the quantum network, the
number of concurrent requests at a particular time will also increase
significantly. Following the same approach of employing Dijkstra’s algorithm,
Pant et al. [pant2019routing] propose a greedy algorithm for multi-path
routing, applying for grid networks after the entanglement. Distributing
multi-path entanglement has also been investigated in [li2021effective], in
which they propose three methods and evaluate the results according to such
criteria as the traffic of the entire network, the degree of fairness between
demands, and the traffic per edge in the network. They also carry out the
routing after the entanglement and assess the results in a grid network.
Vardoyan et al. [10.1145/3374888.3374899] study a star network to satisfy
multiple users at the same time. They also propose a method to model the
effect of decoherence in the network. Based on this model, the authors have
evaluated the influence of the decoherence process on the performance of the
system. In addition, Schoute et al. [schoute2016shortcuts] have investigated
the routing problem of quantum networks but limited for ring and sphere
topologies. Omar et al. [9259957] consider the routing in a grid network,
taking into account trusted repeaters. Das et al. [PhysRevA.97.012335] assess
entanglement routing in different particular topologies. These above studies
can be classified based on the following characteristics:

  * •

Some of them only looked at some networks with specific shapes. This is not
consistent with the fact that the quantum network will have arbitrary shapes.

  * •

The remaining works analyze many aspects of quantum networks without
interesting in optimizing the network responsiveness.

In [10.1145/3387514.3405853], the authors suggest the technique of routing
with two stages. The first stage happens before the entanglement, called the
offline stage. In this stage, they predetermine some paths to serve the
requests, including recovery paths for the case of failed entanglement. The
second stage, named the online stage, happens after the entanglement. Based on
the result of the entanglement and the predetermined paths in the offline
stage, they determine the paths for the requests. In the situation that they
cannot discover the paths for a request due to failed entanglement, they try
to route through the recovery paths. Based on this direction, they presented
an efficient method to distribute multiple entanglements simultaneously.
Nevertheless, with this approach, they have to perform the routing twice; one
is before the entanglement, and the other is after the entanglement. Moreover,
this approach also cannot optimize the capacity of the network.

Several other studies look at the swapping process at quantum repeaters. By
using the prepare and swap protocol, work [9210823] propose a linear
programming model applied to the multicommodity problem to optimize the
entanglement distribution rate for the entire network with the requirements of
ensuring the fidelity of demands. Study [8967073] presents a more complicated
protocol to optimize the entanglement distribution rate. However, this method
requires a longer entangled state storage time.

Compared with the above studies, our work pays attention to practical and
crucial problems in quantum networks, which is to optimize the ability to
satisfy multiple demands at the same time. This issue stems from a limited
character of the quantum network that is a quantum link that cannot be shared
by many simultaneous demands. Our method can be applied to arbitrary networks.
Indeed, the network that we use to perform the simulation is taken from
traditional networks that have been deployed in practice.

##  III Network Model and Research Problem

###  III-A Quantum Network Model

We consider a centralized quantum network [9351762], in which a quantum node
in the network consists of a traditional computer equipped with quantum
processors and can interact with the other nodes via the quantum entanglement
and teleportation. Each node has a set of qubits (i.e., communication and data
qubits). The scope of this work focuses on discussing challenges of
constructing entangled routing paths for demands and how to overcome these
challenges. Hereafter, let’s imply that the following discussion only refer to
the communication qubits [10.1145/3341302.3342070]. Note that the number of
qubits is limited in each node111It depends on the network infrastructure,
then the number of qubits on each node is decided.. A node associated with
qubits can execute entanglements with the other quantum nodes to form
entangled links. In addition, one qubit can entangle to only one qubit at a
time [10.1145/3387514.3405853]. These two qubits are called
Einstein–Podolsky–Rosen (EPR) pair which are in a maximally entangled state.

Figure 1: Two-stage process.

In this paper, we employ a two-stage process to generate an EPR pair between
two remote nodes, which are establishing entanglement between the qubits in
neighbor nodes and swapping between the qubits at each node like Fig. 1. Both
stages are successful with a specific probability depending on the physical
layer. Because the entanglement may fail, the number of edges in the network
after the entanglement can diminish compared with the original network, thus
also called the reduced network. Take the example from Fig. 2, Fig. 2 displays
the original network, which is the network before the entanglement. Assume
edges $(s_{1},x),(x,v),(d_{1},y)$, and $(y,s_{2})$ cannot establish
entanglement, so we ignore these edges in the reduced network illustrated in
Fig. 2. Based on the reduced network, the controller will determine the route
that connects two end nodes, and then repeaters in the network will perform
the swapping depending on the controller decision. We also call a tuple
consisting of two remote nodes, which require an EPR pair, a demand.

Though the routing can be performed in the original network to mitigate the
timing strictness, we have to reserve some paths for the case of failed
entanglement like study [10.1145/3387514.3405853]. This leads to two computing
times; the first is for the routing in the original network, and the second is
conducted after the entanglement to determine the appropriate recovery paths
in the case of failure entanglement or even routing again in the situation
that cannot find the recovery paths. This method is apparently not effective
with respect to resource utilization and in the scenarios of the low success
entanglement rate. That is the reason why we perform the routing in the
reduced network.

Figure 2: (a) Original network and (b) Reduced network

###  III-B Research Problem

Given a quantum network described by an undirected graph $G=(V,E)$, in which
$V$ and $E$ denote the sets of the vertices and edges, respectively. Each
vertex in the graph is a quantum node (i.e., quantum computers or repeaters),
and each edge is a quantum link. The network traffic consists of a set of
demands $D=\left\\{{{D}_{1}},{{D}_{2}},...,{{D}_{n}}\right\\}$ $\forall
D_{i}=(s_{i},d_{i})$. An entangled routing path is defined as the routing path
connecting the source and destination in which any link connects any two nodes
is entangled link. To form entangled routing paths connecting a source and a
destination for a given demand, $(s_{i},d_{i})$, the network operator may
decide to pair qubits and makes these decisions among all demands.

###### Definition 1

Given a quantum network along with a set of demands (source-destination
pairs). The entangled routing rate is defined as the number of demands that
are connected via at least one entangled routing path over the total demands
in the network.

The entangled routing rate is apparently less than or equal to 1; the equality
is equivalent to the best case once all input demands are met but rarely
occurs owing to the reasons stated above. Thereby, we state the MERR problem
as follows.

INSTANCE: Given a quantum network illustrated by an undirected graph
$G=(V,E)$, where $V$ is the set of quantum nodes, $E$ is the set of quantum
links, and a set of demands
$D=\left\\{{{D}_{1}},{{D}_{2}},...,{{D}_{n}}\right\\}$, where
$D_{i}=(s_{i},d_{i})$, and ${{l}_{\max}}\in{{\mathbb{Z}}^{+}}$, and a constant
$k\in{\mathbb{Z}}^{+}$.

QUESTION: Does there exist a routing algorithm to determine entangled routing
paths connecting demands in the network such as the length of any path is not
greater than $l_{max}$ and the total number demands connected by entangled
routing paths is not less than $k$?

Take the network in Fig. 2 as an example of the MERR problem, suppose we need
to fulfill two demands ($s_{1},d_{1}$) and ($s_{2},d_{2}$) in the reduced
network obtained from Fig. 2 simultaneously. Fig. 3 shows the optimal solution
by choosing path ($s_{1},d_{2},v,d_{1}$) for demand ($s_{1},d_{1}$) and path
($s_{2},u,d_{2}$) for demand ($s_{2},d_{2}$), while Fig. 3 displays the poor
solution, where it chooses path ($s_{1},d_{2},u,d_{1}$) for demand
($s_{1},d_{1}$), hence cannot meet demand ($s_{2},d_{2}$) any more. The
entangled routing rate is $1$ and $0.5$, respectively, in which the former is
the optimal solution.

Figure 3: Two methods to serve two demands ($s_{1},d_{1}$) and
($s_{2},d_{2}$): (a) Optimal solution and (b) Non optimal solution

###  III-C Complexity Analysis of the MERR Problem

In this section, we investigate thoroughly the complexity of the MERR problem.
In order to show the hardness of the MERR in Theorem 1, our idea is to reduce
the edge-disjoint path (EDP) problem to the MERR that is presented as follows.

INSTANCE: Given an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
where $\mathcal{V}$ and $\mathcal{E}$ are the set of vertices and edges,
respectively, and a set of pairs of vertices
$\left\\{(\mathtt{s}_{1},\mathtt{t}_{1}),\,(\mathtt{s}_{2},\mathtt{t}_{2}),\,...,\,(\mathtt{s}_{n},\mathtt{t}_{n})\right\\}$,
where
$\mathtt{s}_{i},\,\mathtt{t}_{i}\in\mathcal{V},\,\forall{i}\,=\,1,\,2,\,...,\,n$,
and a constant $\mathtt{h}\in{\mathbb{Z}}^{+}$.

QUESTION: Does there exist a method that connects each pair of the set with
one path, such that the connected paths do not share their edges with the
others and the number of connected paths is at least $\mathtt{h}$?

###### Theorem 1

The MERR problem is NP-hard.

Proof: Because the EDP problem is NP-hard [1530717], we prove the difficulty
of the MERR problem by showing a reduction from the EDP problem to the MERR
problem. Indeed, the instance of the MERR problem can be constructed from the
instance of the EDP problem as follows: assign $V$ to $\mathcal{V}$, $E$ to
$\mathcal{E}$, and set of demand $D$ to the set of pairs of vertices. This
process is inherently done in polynomial time. To complete the proof, we
demonstrate that the EDP problem is solvable if and only if the MERR problem
is solvable.

Suppose that the EDP is solvable, which means there exists a constant
$\mathtt{h}\in{\mathbb{Z}}^{+}$ such that the number of connected paths is at
least $\mathtt{h}$. Therefore, without taking into account the constraint of
path length, we will also determine at least $\mathtt{h}$ met demands for the
MERR problem. Then, we drop out the demands whose connecting path is greater
than $l_{max}$. Assume that the number of such demands is
$\mathtt{h}^{\prime}$. Hence, we can determine at least
$\mathtt{h}-\mathtt{h}^{\prime}$ met demands for the MERR problem.

Suppose that the MERR is solvable, we assign $l_{max}$ to a large enough value
such as $\left|E\right|$. In this case, the solution to the MERR problem is
also the solution to the EDP problem. This completes the proof.

##  IV Tight Approximation for the MERR Problem

In this section, we design tight approximation algorithms for the MERR problem
by expressing the problem using the integer programming. We begin with the
primary formulation of integer programming conditions in $\S$IV-A and detailed
algorithms and routing techniques are presented in the following.

###  IV-A Primary Formulation

Theoretically, a quantum network is undirected, and thus, we could divide one
undirected edge into two directed edges with opposite directions. On that
basis, we convert the quantum network after the entanglement to a flow
network, hence obeying the constraints of the flow network. Those are the flow
conservation at the nodes and capacity limitation on the edges. Next, we
consider each of the constraints in turn, in which symbol ${f_{uv}^{i}}$
indicates the flow of $i^{th}$ demand on directed edge $(u,v)$.

This paper only considers the single-channel networks, which implies each edge
of the network possesses only one quantum channel. Because one quantum link
cannot be shared between multiple paths of different demands at the same time,
the edge’s capacity is only one. Hence, the first constraint is:

$\displaystyle\sum\limits_{i=1}^{k}{f_{uv}^{i}}+\sum\limits_{i=1}^{k}{f_{vu}^{i}}\leq
1$ $\displaystyle\,\,\,\,\,for\,each\,(u,v)\in E$ (1)

At one node in the network, swapping between two internal qubits, with respect
to the quantum, establishes entanglement between two qubits at two remote
nodes that were being in the entanglement state with the internal qubits
before. In terms of the flow network, the swapping at one node, but the source
and destination, generates an internal link that connects the flow into the
node and the flow out of that node. Hence, for each node in the network, but
the source and destination, the total flow into the node must equal the total
flow out of that node. Thus, we express the constraint following:

$\displaystyle\sum\limits_{\begin{smallmatrix}(u,v)\in
E\end{smallmatrix}}{f_{uv}^{i}}-\sum\limits_{\begin{smallmatrix}(u,v)\in
E\end{smallmatrix}}{f_{vu}^{i}}=0$ $\displaystyle\,\,\,for\,each\,u\in
V-\\{{{s}_{i}},{{d}_{i}}\\}$ (2)
$\displaystyle\,\,\,and\,for\,each\,i=1,2,...,k$

To avoid the situation where we can find a solution, but one out of the paths
is too long, which results in unusable due to low fidelity and probability of
success swapping, we pose the following constraint to limit the path length.

$\sum\limits_{(u,v)\in
E}{\left(f_{uv}^{i}+f_{vu}^{i}\right)}\leq{{l}_{\max}}\,\,\,for\,each\,i=1,2,...,k$
(3)

where $l_{\max}$ is the upper bound of the path length.

A demand is met when we can find a path to establish entanglement between two
qubits in the source and destination, which means, concerning the flow
network, there exists a flow from the source to the destination. Moreover, to
save resources of the network to satisfy as many demands as possible, we
consider only one path for each demand. Therefore, the total flow of $i^{th}$
demand out of $s_{i}$ is at most one, and the equality occurs only when the
demand is met. This also implies the flows of $i^{th}$ demand into $s_{i}$ is
equal to zero.

$\sum\limits_{\begin{smallmatrix}({{s}_{i}},v)\in
E\end{smallmatrix}}{f_{{{s}_{i}}v}^{i}}\leq 1\,\,\,for\,each\,i=1,...,k$ (4)
$\displaystyle f_{v{{s}_{i}}}^{i}=0$
$\displaystyle\,\,\,for\,each\,({{s}_{i}},v)\in E\,and$ (5)
$\displaystyle\,\,\,for\,each\,i=1,2,...,k$

Finally, the flow of $i^{th}$ demand across directed edge $(u,v)$ in the
network is a binary variable, in which one is equivalent to employing the
corresponding edge to establish entanglement between the source and
destination, and zero is vice versa.

$\displaystyle f_{vu}^{i},\,f_{uv}^{i}\in\\{0,1\\}$
$\displaystyle\,\,\,\,\,for\,each\,(u,v)\in E\,and$ (6)
$\displaystyle\,\,\,\,\,for\,each\,i=1,2,...,k$

The goal of the MERR problem is to satisfy as many demands as possible at the
same time. Because each met demand corresponds to a flow out of its source,
the problem is equivalent to maximizing the total flows of all demands out of
their corresponding source nodes. Therefore, the objective function of the
problem is described as follows.

$\displaystyle\textbf{P1}:\,maximize\,\,\,\,\,\,\sum\limits_{i=1}^{k}{\sum\limits_{\begin{smallmatrix}({{s}_{i}},v)\in
E\end{smallmatrix}}{f_{{{s}_{i}}v}^{i}}}$ (7) $\displaystyle
s.t.\,\,\,(\ref{equ:cap_con})-(\ref{equ:bin_con})$

In the following, we propose four approaches to address the MERR problem.

###  IV-B Integer Linear Programming

The first is to employ the integer linear programming (ILP) technique, in
which the number of decision variables is $2\left|D\right|\left|E\right|$.
Though this approach supplies the optimal solution, the running time will
proliferate when the scale of the network increases. Therefore, this method is
not applicable to large-scale networks because the quantum networks inherently
require a short computation time to guarantee the coherence of qubits.
Instead, it provides the upper bound reference with respect to the large
networks. In the following, we propose three approximation algorithms to
address the MERR problem in polynomial time.

###  IV-C Half-Based Rounding

To reduce the complexity of the problem, we replace constrain (6) with
constraint (8), thus changing the model from integer linear programming to
linear programming, which is inherently solved within polynomial time. But
most solutions obtained from this approach are not integers, thus not feasible
because we cannot make decisions based on fractional values. Therefore, these
values need to be rounded up to 1 or down to 0. Suppose the solution got from
the linear program is $\overline{f_{uv}^{i}}$. If $\overline{f_{uv}^{i}}\geq
0.5$ then $f_{uv}^{i}=1$, else $f_{uv}^{i}=0$ if otherwise. Based on the
rounding results, we choose the proper paths such that they satisfy all the
constraints. Algorithm 1 describes our method.

$\displaystyle f_{vu}^{i},\,f_{uv}^{i}\in\left[0,1\right]$
$\displaystyle\,\,\,\,\,for\,each\,(u,v)\in E\,and$ (8)
$\displaystyle\,\,\,\,\,for\,each\,i=1,2,...,k$

In Algorithm 1, the linear program is constructed and solved in Lines $1$–$2$.
Then rounding stage and determining the satisfied demands are carried out over
Lines $3$–$31$. After solving the linear program, some demands are satisfied
immediately, which means some flow variables of these demands are equal to
$1$, while the others are equal to $0$. Because these solutions met all
constraints and are integers, we are certain to indicate the path from the
source to the destination of these demands. They are then added into $S$,
which is the set of met demands, and the remainder demands are put into set
$R$. These steps are performed over Lines $3$-$10$. Afterward, in Lines
$11$-$14$, the edges belonging to the paths of the met demands in set S are
removed from the graph to guarantee the capacity constraint. Lines $15$-$23$
show the rounding stage for the remainder demands. The final solution
($f_{uv}^{i}$) will be rounded up to $1$, if the solution from the linear
program ($\overline{f_{uv}^{i}}$) is greater than or equal to $0.5$, and down
to $0$ if otherwise. The solutions from the rounding are employed to determine
which demands are satisfied among the remaining demands in set $R$ (Lines
$24$-$31$). The rounding strategy of this approach is based on the value of a
half, thus called the Half-based Rounding Algorithm (HBRA).

Algorithm 1 Half-based Rounding Algorithm

Input: Network $G=(V,E)$, a set of demand $D=\\{D_{1},D_{2},...,D_{n}\\}$ with
$D_{i}=(s_{i},d_{i})$, ${{s}_{i}},{{d}_{i}}\in V$, a constraint of length
$l_{\max}$
Output: A set of satisfied demands $S$

1:Build the linear program with objective function (7) and constraints (1) -
(5) and (8)

2:Solve the program, the solution is expressed by $\overline{f_{uv}^{i}}$

3:$S\leftarrow\emptyset$, $R\leftarrow\emptyset$

4:for $D_{i}\in D$ do

5: if $D_{i}$ is satisfied then $\triangleright$ Some demands can be satisfied
after solving the linear program

6: $S\leftarrow S\cup{{D}_{i}}$

7: else

8: $R\leftarrow R\cup{{D}_{i}}$

9: end if

10:end for

11:for $D_{i}\in S$ do

12: Determine the path $P_{i}$ from $s_{i}$ to $d_{i}$

13: $E\leftarrow E\backslash\\{e\in{{P}_{i}}\\}$

14:end for

15:for $D_{i}\in R$ do $\triangleright$ Rounding Stage

16: for $(u,v)\in E$ do

17: if $\overline{f_{uv}^{i}}\geq 0.5$ then

18: $f_{uv}^{i}$ = 1

19: else

20: $f_{uv}^{i}$ = 0

21: end if

22: end for

23:end for

24:for $D_{i}\in R$ do

25: if Exist a path $P_{i}$ from $s_{i}$ to $d_{i}$ then

26: if $length({{P}_{i}})\leq{{l}_{\max}}$ then

27: $S\leftarrow S\cup{{D}_{i}}$

28: $E\leftarrow E\backslash\\{e\in{{P}_{i}}\\}$

29: end if

30: end if

31:end for

32:return $S$

###  IV-D Randomized Rounding

This method is similar to HBRA, except for the rounding stage. Instead of
using the threshold of a half, we utilize the technique proposed in
[raghavan1987randomized] to round the solution. Assume the solution obtained
from the linear program is $\overline{f_{uv}^{i}}$, then the principle of the
rounding is $Pr(f_{uv}^{i}=1)=\overline{f_{uv}^{i}}$, where $Pr(f_{uv}^{i}=1)$
is the probability of rounding $f_{uv}^{i}$ up to 1. The rounding is carried
out only once to satisfy the strict timing of quantum networks. The paths are
selected in the same way with the HBRA method. We call this approach the
Randomized Rounding Algorithm (RRA).

###  IV-E Path-Length-Based Algorithm (PLBA)

In this approach, we apply the GREEDY_PATH algorithm proposed by study
[10.1007/3-540-69346-7_12] to solve the MERR problem. This method is inspired
by the idea that the shorter the path for one demand, the less impact on other
demands. Namely, the algorithm tries to meet the demand owns the shortest path
among the input demands first, hence called the Path-Length-Based Algorithm
(PLBA). By removing the edges along the determined paths for the met demands,
the algorithm guarantees to satisfy all the constraints. The core idea of this
approach is the Dijkstra’s algorithm, so it is a high-speed algorithm. The
detail is presented in Algorithm 2, where we use the Dijkstra’s algorithm to
find the shortest path between two nodes $s_{i}$ and $d_{i}$ of demand $D_{i}$
in Line $11$. Then, we verify whether the algorithm can find the path or not,
as well as the upper bound of the path length in Lines $12$-$15$. At each
iteration in the while loop over Lines $6$-$17$, we fulfill the demand that
has the shortest path. After that, in Lines $21$-$22$, we build the residual
graph of $G$, in which the edges along the selected path are removed. We
repeat this iteration until all demands are considered.

Algorithm 2 Path-Length-Based Algorithm

Input: Network Graph $G=(V,E)$, a set of demand
$D=\\{{D_{1},D_{2},...,D_{n}}\\}$ with $D_{i}=(s_{i},d_{i})$,
$s_{i},\,d_{i}\in V$, a constraint of length $l_{max}$

Output: The number of met demands

1:$FUL\\_D\leftarrow\emptyset$ $\triangleright$ List of fulfilled demands

2:$S\leftarrow\emptyset$ $\triangleright$ List of the shortest paths

3:$SPL\leftarrow\emptyset$ $\triangleright$ List of the shortest path length

4:while $len(FUL\\_D)<len(D)$ do

5: $S\leftarrow\emptyset$

6: while $i<len(D)$ do

7: if $D_{i}\in FUL\\_D$ then

8: $i\leftarrow i+1$

9: continue

10: end if

11: $S_{i}\leftarrow Shortest\\_path(D_{i}=\\{s_{i},d_{i}\\})\>on\>G$

12: if $len(S_{i})>l_{max}$ or $len(S_{i})=0$ then

13: $SPL_{i}\leftarrow 0$

14: $FUL\\_D\leftarrow FUL\\_D\cup D_{i}$

15: end if

16: $i\leftarrow i+1$

17: end while

18: Find $min(S_{j})>0$

19: $SPL_{j}\leftarrow len(S_{j})$

20: $FUL\\_D\leftarrow FUL\\_D\cup D_{j}$

21: $R\leftarrow G-\\{Edges\,on\,the\,selected\,shortest\,path\,S_{i}\\}$
$\triangleright$ Build residual graph

22: $G\leftarrow R$

23:end while

24:return The number of $SPL_{j}>0$

##  V Analyze of the algorithms

In this section, we first present the time complexity of the PLBA method over
Theorem LABEL:thm:plba_cplx. In addition, Theorem LABEL:thm:round_cplx states
the time complexity of the rounding stage of the HBRA and RRA algorithms.
Then, Theorem LABEL:thm:round_appr demonstrates that the RRA technique can
yield a feasible solution with a high probability.