Corresponding author: Scarlett Gauthier (email: s.s.gauthier@tudelft.nl).

# A Control Architecture for Entanglement Generation Switches in Quantum
Networks

SCARLETT GAUTHIER1,3  GAYANE VARDOYAN1,3,4, AND STEPHANIE WEHNER1,2,3  QuTech,
Delft University of Technology  Kavli Institute of Nanoscience, Delft
University of Technology  Quantum Computer Science, Electrical Engineering,
Mathematics and Computer Science, Delft University of Technology  University
of Massachusetts, Amherst

###### Abstract

Entanglement between quantum network nodes is often produced using
intermediary devices - such as heralding stations - as a resource. When
scaling quantum networks to many nodes, requiring a dedicated intermediary
device for every pair of nodes introduces high costs. Here, we propose a cost-
effective architecture to connect many quantum network nodes via a central
quantum network hub called an Entanglement Generation Switch (EGS). The EGS
allows multiple quantum nodes to be connected at a fixed resource cost, by
sharing the resources needed to make entanglement. We propose an algorithm
called the Rate Control Protocol (RCP) which moderates the level of
competition for access to the hub’s resources between sets of users. We
proceed to prove a convergence theorem for rates yielded by the algorithm. To
derive the algorithm we work in the framework of Network Utility Maximization
(NUM) and make use of the theory of Lagrange multipliers and Lagrangian
duality. Our EGS architecture lays the groundwork for developing control
architectures compatible with other types of quantum network hubs as well as
system models of greater complexity.

###### Index Terms:

central quantum network hub, control protocol, entanglement generation,
network utility maximization, resource sharing

=-15pt

##  I Introduction

A quantum network enables radically new capabilities that are provably
impossible to attain in any classical network [1]. Examples include
applications such as secure communication [2, 3], secure quantum computing in
the cloud [4, 5], and clock synchronization [6]. Users utilize the end nodes
of a network to run applications. The key to unlocking widespread roll-out of
these applications is the ability to produce entanglement between these end
nodes.

Prevalent methods for generating entanglement between two quantum nodes that
are directly connected by a quantum communication medium (e.g., optical
fibers) involve an intermediate device. A prime example is heralded
entanglement generation [7, 8] in which the intermediary device is a so-called
heralding station. This method of producing entanglement has successfully been
demonstrated in many experimental platforms including Color Centers [9, 10],
Ion Traps [11, 12], Atomic Ensembles [13, 14] and Neutral Atoms [15]. As
quantum networks continue to scale, it becomes increasingly impractical to
maintain direct fiber connections and dedicated heralding stations for every
pair of end nodes.

To address this challenge, we propose a scalable quantum network architecture
for an Entanglement Generation Switch (EGS), a central hub equipped with a
limited number of intermediate devices called resources, a switch, and a
processor responsible for managing a scheduling algorithm and sending
classical messages to nodes. This central hub enables multiple nodes to share
the intermediate devices, significantly reducing the complexity and total
resources required for large-scale deployment. While our results apply to an
EGS sharing any type of entanglement generation resource, a specific example
illustrates how an EGS can operate: Consider quantum network nodes that
generate entanglement between them using the so-called single-click bipartite
entanglement generation protocol (see e.g [10]). In this case the resource(s)
to be shared are the heralding station(s). Such stations consist of two input
channels connected to a $50/50$ beam splitter, which is then connected by two
output channels to a pair of photon detectors that are each connected to a
device for processing the measurement outcomes, such as a Field Programmable
Gate Array (FPGA). The basic principle of the single-click protocol requires
that each network node of the pair locally generates entanglement between a
qubit in their local memory and a travelling photon. The photon is sent to a
heralding station at which an entanglement swap is attempted on the two
photons received; if the entanglement swap is successful, the qubits of the
two network nodes will have become entangled. An EGS aims to share one or more
heralding stations amongst many connected network nodes. These nodes will
still run the single-click protocol, but be limited to using the heralding
station needed in the time allocated to them by the EGS.

A crucial challenge in implementing such an architecture is the efficient
allocation of the central hub’s resources to different pairs of users in
distinct time slots. Similar to classical networking, the allocation process
should be driven by user demand for network resources. In the context of
quantum networks, this translates to the demand of a user pair $(u_{i},\
u_{j})$ for entanglement generation at a specific rate or fidelity. Given a
set of user demands, the EGS must compose a schedule for the allocation of
resources in order to service those demands. In general, the total demand of
users may exceed the available resources at the central hub, leading to
scheduling and resource allocation challenges.

Here, we introduce the first algorithm for regulating user demand to an EGS,
thereby solving this key challenge. Specifically, the algorithm takes as input
a vector of rates of entanglement generation demanded by pairs of users and
outputs an updated rate vector. The current set of user-originated demands is
a measure of competition for EGS resources. We construct the algorithm within
the Network Utility Maximization (NUM) framework, wherein the problem of
demand regulation is cast as a constrained optimization problem. To solve the
problem, we derive the algorithm by using the theory of Lagrange multipliers
and Lagrangian duality. These tools, respectively, enable including the
constraints together with the objective of the optimization problem and
solving for a parameter vector which is the unknown value of the combined
problem. Regulating competition for the resources by modifying user demand
makes it possible to enforce a notion of fairness in the allocation of
resources and maximize resource utilization. Since the algorithm regulates
competition by calculating the rates demanded by users, we call it the Rate
Control Protocol (RCP).

###  I-A Results Summary

We make the following contributions:

  * •

We characterize (Theorem II.1) the capacity region of the EGS, which is the
maximal set of rates at which users can demand entanglement generation such
that there exists a scheduling policy under which, on average, the demanded
rates do not exceed the delivered rates. The impact of specifying the capacity
region is that it delineates which rates can feasibly be serviced by the EGS.

  * •

We prove (Theorem II.1) that under the Maximum Weight Scheduling policy
(Definition II.6) for resource allocation it is possible for the EGS to
deliver average rates of entanglement generation that match the requested
rates, for any rate vector from within the capacity region. Therefore, an EGS
operated with this scheduling policy can achieve throughput optimality as long
as the rates demanded by users lie withing the capacity region. To prove the
theorem, we use the Lyapunov stability theory of Markov chains.

  * •

We derive the RCP, an algorithm to regulate the rates of bi-partite
entanglement generation which pairs of users demand from an EGS. The RCP
solves the problem of moderating user competition for EGS resources. The
derivation is based on techniques from Network Utility Maximization (NUM) and
its quantum network extension (QNUM), where resource allocation in a (quantum)
network is modelled as an optimization problem that can be solved using
methods from convex optimization theory.

  * •

We prove (Theorem III.1) that the sequence of arrival rate vectors yielded by
the RCP converges over time slots to an optimum value, given any feasible rate
vector as initial condition. The significance of this result is that if the
RCP is used to set the demand rates of entanglement generation over a series
of time-slots, the set of demanded rates will approach an optimal value, as
long as the initial rate vector supplied to the algorithm is feasible. The
proof relies on Lagrange multipliers and Lagrangian duality theory.

  * •

Finally, we supply numerical results that support our analysis.

###  I-B Related Work

A quantum network hub that can store locally at least one qubit per linked
node and distributes entanglement across these links has been studied [16,
17]. We refer to such a hub as an Entanglement Distribution Switch (EDS). This
system differs from our system because the central hub has qubits and/or
quantum memories, whereas our system does not. In [16] the focus is on
assessing the EDS performance in terms of the rate at which it creates
$n-$partite entanglements, and in [17] the possible rate/fidelity combinations
of GHZ states that may be supplied by an EDS [17] are studied.

Maximum Weight scheduling is a type of solution to the problem of resource
allocation which is based on assigning resources to sets of users with the
largest service backlog. A Maximum Weight scheduling policy was originally
presented in [18] for resource allocation in classical communication networks
and was adapted to the analysis of a single switch for classical networking in
[19], where it was shown that under this scheduling policy the set of request
arrival rates matches the request departure rates (or in other words the
policy stabilizes the switch for all feasible arrival rates). In [20] the
capacity region of an EDS, defined as the set of arrival rates of requests for
end-to-end multi-partite entanglements that stabilize the switch, is first
characterized. Using the Lyapunov stability theory of Markov chains, a Maximum
Weight scheduling policy is proposed and shown to stabilize the switch for all
arrival rates within the capacity region. To summarize, in each of the
classical network settings and in the EDS setting a Maximum Weight scheduling
policy has the merit of achieving a specified performance metric. None of
these results are immediately applicable to our system. We demonstrate that
such a policy achieves the performance metric of throughput optimality when
applied to the EGS by first characterizing the capacity region of the EGS,
which has not been done before, and then proving that a Maximum Weight
scheduling policy also achieves throughput optimality in our system.

These results on the analysis of EDS systems constitute the first analytic
approaches to resource allocation by a quantum network hub. However, due to
the assumption that an EDS locally controls some number of qubits per link,
the system has a high technical implementation cost which may not be
compatible with near-term quantum networks. Moreover, although these works
assume that there is competition between multiple sets of users, the focus is
purely on the capacity of the EDS system. Conversely, our analytic
contributions apply to EGS quantum network hubs, which have a low technical
implementation cost because the hub does not require local control of any
qubits or quantum memory. Furthermore, our results extend beyond the analysis
of the capacity of the EGS and we propose the RCP as a solution to the problem
of moderating competition for the EGS resources.

In [21], a quantum network topology is studied where user-controlled nodes are
connected through a hub known as a Qonnector. The Qonnector provides the
necessary hardware for limited end nodes to execute applications in pairs or
small groups. A potential configuration of the Qonnector is as an EGS. While
[21] focuses on assessing the performance of certain applications in this
topology, it does not address control policies for the system. In contrast,
our work examines control policies for an EGS.

NUM was first introduced in [22] and has been widely used to develop and
analyze control policies for classical networks [23]. It is a powerful
framework for designing and analyzing communication protocols in classical
networks wherein the problem of allocating resources amongst competing sets of
users is cast as a constrained optimization problem. This framework was
recently extended to QNUM by [24]. Therein, the authors first develop three
performance metrics and use them to catalogue the utility of resource
allocation in a quantum network model where each link is associated with a
rate and fidelity of entanglement delivery to communicating users. This work
does not immediately extend to control policies, as the resource allocations
investigated are based on static numerical optimization and need to be
recalculated in response to changes in the constraints or sets of users.

In classical networks, probabilistic failures such as loss of a message during
transmission or irreconcilable distortion due to transmission over a noisy
channel may occur. A serious challenge introduced in the analysis of quantum
networks is that in addition to the failure modes of a classical network
several new probabilistic failure modes arise that are independent of the
state of the network but nevertheless affect its ability to satisfy demands.
An example is the probabilistic success in practical realizations of heralded
entanglement generation [9, 10, 11, 12, 13, 14, 15]. Due to this failure mode,
scheduling access to a resource at a certain rate does not guarantee
entanglement generation at that rate, thereby complicating the analysis of
scheduling.

It is important to distinguish between the concept of rates in classical
network control protocols and the notion of rate in the model of a quantum
network hub presented here. In classical networks, users transmit data at some
rate and classical network control protocols, such as the Transmission Control
Protocol (TCP), regulate the rate at which users send their data [23]. In
contrast, in our quantum network hub model, users demand a rate of
entanglement generation. However, a significant challenge in developing a
control protocol for the EGS is the difference between the rate of attempted
entanglement generation and the rate at which entanglement delivery is
demanded and delivered to users. Explicitly, in the RCP it is the desired
rates of entanglement generation that serve as the controllable parameters
moderated by the protocol.

Figure 1: EGS Architecture: a) EGS structure: An EGS with $R=4$ resources
connected to $N=9$ nodes. The EGS is controlled by a classical processor and
consists of a switch, resources, and physical connections. Nodes have quantum
communication channels to the switch and classical communication channels to
the processor. b) Resource Allocation: The switch opens connections to link
nodes 1, 2 and resource 1. For example, the connections may consist of direct
optical fiber paths from the nodes to the switch and from the switch to the
resource, via an interface at the switch. This establishes the physical
allocation of resource 1 to the communication session of nodes 1, 2 for time
slot $t_{n}$. c) Quantum communication sequence: Node-to-processor
communication in time slot $t_{n}$ with a batch size of three entanglement
generation attempts. d) Concurrent classical communication sequences: Nodes
and the processor communicate in time slot $t_{n}$, governing resource
allocation and the RCP (see Algorithm III for RCP details.)

##  II Preliminaries

Operation of the EGS requires interactions between the set of quantum network
nodes $U$ and the EGS processor with control over $R$ resources. See Fig. 1 a)
for an overview of the physical architecture. Below we delineate the process
by which pairs of nodes may request $\big{(}$Fig. 1 d)$\big{)}$ and receive
$\big{(}$Fig. 1 b) and d)$\big{)}$ resource allocations from the processor. We
assume:

  * •

the EGS operates in a fixed-duration time slotted system where $t_{n}$ denotes
the $n^{th}$ time slot;

  * •

timing synchronization between the processor and each node is continuously
managed by classical control electronics at the physical layer;

  * •

allocation of a single resource to communication session $s$ for one time slot
allows for the creation of a maximum of one entangled pair with a success
probability of $p_{\text{gen}}$. A consistent physical model involves a
batched sequence of attempts, which can be terminated upon the successful
creation of an entangled pair or at the end of the time slot. See Fig. 1 c)
for an example quantum communication sequence compatible with heralded
entanglement generation.

The classical communication sequence repeated in each time slot $t_{n}$ which
governs resource allocation is summarized in Fig. 1 d). In what follows we
introduce and explain each step of this communication sequence. The notation
introduced throughout this section is summarized in Table I.

TABLE I: Inventory of notation introduced in Section II Identifier | Description | Domain
---|---|---
$U$ | the set of (user operated) quantum network nodes, of cardinality $|U|=N$ | $\mathbb{N}$
$R$ | the number of resources controlled by the EGS processor | $\mathbb{N}$
$t_{n}$ | the $n-th$ time-slot of the EGS system | $\mathbb{N}$
$S$ | the set of communication sessions | $\\{1,\cdots,N\\}^{2}$
$\bm{\lambda}(t_{n})$ | the vector of target rates of all communication sessions at time $t_{n}$ | ${\mathbb{R}^{+}}^{|S|}$
$a_{s}(t_{n})$ | the number of demands from communication session $s$ in time-slot $t_{n}$ | $\mathbb{N}$
$\bm{q}(t_{n})$ | the vector of queues, with components $\big{(}q_{s}(t_{n})\ \forall s\big{)}$ | $\mathbb{N}^{|S|}$
$\bm{M}(t_{n})$ | the resource allocation schedule for time-slot $t_{n}$, | $\mathbb{N}^{|S|}$
| with components $\big{(}M_{s}(t_{n})\ \forall s\big{)}$ |
$x_{s}$ | the maximum number of resources that can be allocated to | $\\{1,\cdots,R\\}$
| communication session $s$ in any one time-slot |
$p_{\text{gen}}$ | the probability a communication session allocated a resource for one time-slot | [0, 1]
| successfully generates entanglement |
$g_{s}(t_{n})$ | the number of successfully generated entangled pairs by | $\\{0,1,\cdots,M_{s}(t_{n})\\}$
| communication session $s$ in $t_{n}$ |
$\mathcal{C}$ | the set which has the capacity region of the EGS as interior | $\mathbb{R}^{+}$
$\lambda_{\text{EGS}}$ | the maximum total rate that can be delivered, on average, by the EGS, $\lambda_{\text{EGS}}=R\cdot p_{\text{gen}}$ | $\mathbb{R}^{+}$
$\lambda^{\max}_{\text{gen},s}$ | the maximum rate the EGS can deliver, on average, to communication | $\mathbb{R}^{+}$
| session $s$, $\lambda^{\max}_{\text{gen},s}=x_{s}\cdot p_{\text{gen}}$ |
$\lambda^{\min}_{s}$ | a minimum acceptable rate of entanglement generation specified by | $\mathbb{R}^{+}$
| communication session $s$ |
$\lambda_{u}\phantom{x.}$ | the maximum rate at which each node $u\in U$ can generate | $\mathbb{R}^{+}$
| and/or make use of entanglement, across all of the sessions that it is involved in |

###  II-A Demands for resource allocation from nodes to the EGS processor

######  Definition II.1 (Target Rate, Communication Session).

Each possible pair of nodes has the potential to require shared bipartite
entanglement. To fulfill this need, a node pair $(u_{i},u_{j})$ requires the
processor to allocate a resource. The node pair sets a target rate
$\lambda_{(i,j)}(t_{n})$ once per time slot, which represents the average
number of entangled pairs per time slot they aim to generate using one or more
EGS resources. A distinct pair of nodes with a non-zero target rate is
referred to as a communication session and is associated with a unique
communication session ID, $s$. The set of communication session IDs, $S$ is
defined as follows:

$\displaystyle S:=\big{\\{}s$ $\displaystyle=(i,j)\ |\ i<j\text{ and }$
$\displaystyle\lambda_{s}(t_{n})>0,\forall\
(i,j)\in\\{1,\cdots,N\\}^{2}\big{\\}}$ (1)

where $N=|U|$ is the total number of network nodes with connections to the
EGS.

Henceforth each pair of nodes will be identified by its communication session
id $s$. The target rates of all communication sessions in time-slot $t_{n}$
can be written as a vector $\bm{\lambda}(t_{n})\in\mathbb{R}^{|S|}$, the
$s^{th}$ component of which is labelled by communication session ID $s$ as
$\lambda_{s}(t_{n})$.

A rate of entanglement generation is the service demanded by each
communication session from the EGS. To address the difference between the
desired rate and the rate at which a communication session requires resource
allocation to achieve that rate, we establish the following model for demand,
which is compatible with a discrete time scheduling policy.

######  Definition II.2 (Demand).

Demands for resources are requests made by communication session $s$ to obtain
a single entangled pair. The number of demands $a_{s}(t_{n})$ submitted by
session $s$ at time slot $t_{n}$ depends on its target rate
$\lambda_{s}(t_{n})$. If $\lambda_{s}(t_{n})>1$, then communication session
$s$ first submits $\lfloor\lambda_{s}(t_{n})\rfloor$ demands. For a
communication session $s$ with $0\leq\lambda_{s}(t_{n})\leq 1$, or to account
for the remaining part of the rate for any session with
$\lambda_{s}(t_{n})>1$, each communication session randomly generates demands
by sampling from a Bernoulli distribution with a mean equal to
$\lambda_{s}(t_{n})-\lfloor\lambda_{s}(t_{n})\rfloor$, so that in general the
submitted demands satisfy a (shifted) Bernoulli distribution,
$a_{s}(t_{n})\sim\text{Bernoulli}\big{(}\lambda_{s}(t_{n})-\lfloor\lambda_{s}(t_{n})\rfloor\big{)}+\lfloor\lambda_{s}(t_{n})\rfloor$.

######  Definition II.3 (Designated Communication Node, Secondary Node).

One of the nodes of every communication session is marked as the designated
communication node for communicating the entanglement requests to the switch.
The terms designated communication node and secondary node are used to refer
to the two nodes of a communication session.

###  II-B Processing demands for resource allocation

######  Definition II.4 (Queue).

When the processor receives a demand, it is added to one of $|S|$ queues, one
for each communication session. The set of demands received by the processor
by time-slot $t_{n}$ and not yet satisfied is captured by the queue vector
$\mathbf{q}(t_{n})\in\mathbb{N}^{|S|}=(q_{s}(t_{n})\ \forall s)$, where the
component $q_{s}(t_{n})$ is the queue of communication session $s$ at time
$t_{n}$. Each queue processes demands in first in first out order. As all
demands are identical, we interchangeably use $q_{s}(t_{n})$ to refer to both
the queue length of communication session $s$ in time slot $t_{n}$ and the
queue itself.

######  Definition II.5 ((Demand-Based) Schedule).

A resource allocation schedule is a vector
$\bm{M}(t_{n+1})\in\mathbb{N}^{|S|}$ calculated by the EGS processor in time
slot $t_{n}$ determining the assignment of the resources for time slot
$t_{n+1}$. A single session $s$ may be allocated the use of multiple
resources, up to a maximum number $x_{s}$ set by the EGS which does not exceed
$R$, the total number of resources controlled by the EGS. For every session
$s\in S$ the entry

$M_{s}(t_{n+1})\in\\{0,\ 1,\ \cdots,\ x_{s}\\}$ (2)

corresponds to the number of resources assigned to $s$ for the entire duration
of time slot $t_{n+1}$. A demand based schedule is based on the vector of all
queues, $\bm{q}(t_{n})$, as it stands before new demands are registered in
$t_{n}$, and satisfies

$\displaystyle\sum_{s}M_{s}(t_{n+1})$
$\displaystyle\leq\min\big{(}\sum_{s}q_{s}(t_{n}),\ R\big{)},$ (3)
$\displaystyle 0\leq M_{s}(t_{n+1})$
$\displaystyle\leq\min\big{(}q_{s}(t_{n}),\ x_{s}\big{)}\leq R,\ \forall\ s.$
(4)

Each node of a communication session $s$ requires a physical connection to the
EGS switch. A single physical connection, such as an optical fiber, can be
used for this purpose. To enable multiple connections between a node and the
switch, options include the use of optical multiplexers over a single fiber or
utilizing multiple fibers within a fiber bundle. The parameters $\big{(}x_{s}\
\forall s\big{)}$ are motivated by situations where the number of physical
connections that can be dedicated to service communication session $s$ are
limited.

######  Definition II.6 (Maximum Weight Scheduling).

The set $\mathcal{M}$ of feasible demand based schedules at time slot $t_{n}$
contains all vectors $\mathbf{M}^{\prime}(t_{n+1})\in\mathbb{N}^{|S|}$
satisfying (2), (3), and (4). The EGS processor selects a maximum weight
schedule $\mathbf{M}(t_{n+1})\in$ $\mathcal{M}$ from the feasible schedules
for the following time slot by solving for

$\mathbf{M}(t_{n+1})\in\text{arg}\ \underset{\mathbf{M}^{\prime}}{\text{max
}}\sum_{s}q_{s}(t_{n})M^{\prime}_{s}(t_{n+1}).$ (5)

In words, the schedule is selected from the set of feasible schedules by first
solving for the subset of schedules that allocate resources to the sessions
with the largest number of queued demands. If that subset contains more than
one schedule, a schedule is randomly selected from the subset.

By the end of $t_{n}$, the schedule for $t_{n+1}$ has been computed by the
processor and broadcast to the nodes. If the schedule allocates use of a
resource to communication session $s$ for $t_{n+1}$, the users of $s$ utilize
the allocated resource to make a batch of entanglement generation attempts
over the duration of $t_{n+1}$. The demand at the front of queue $s$ is only
marked as served once both a resource has been allocated and the users of $s$
have successfully generated entanglement. Hence the dynamics of each queue are
given by,

$q_{s}(t_{n+1})=[q_{s}(t_{n})+a_{s}(t_{n})-g_{s}(t_{n})]^{+}\ \forall\ s,$ (6)

where $[z]^{+}=\max(z,0)$, and $g_{s}(t_{n})$ is the number of successfully
generated entangled pairs by $s$ during $t_{n}$. In words, every subsequent
time slot the demands that arrived in the previous time slot are added to the
queue and those that were scheduled and successfully resulted in the
generation of an entangled pair are removed from the queue. The updated queue
is always of non-negative length since the number of successfully generated
entangled pairs is a sample of a binomial random variable where the number of
trials is the number of resources allocated to $s$, $M_{s}(t_{n})\big{(}\leq
q_{s}(t_{n})\big{)}$, and the trial success probability is $p_{\text{gen}}$,

$g_{s}(t_{n})\sim\text{Bin}\big{(}M_{s}(t_{n}),\ p_{\text{gen}}\big{)}.$

######  Definition II.7 (Supportable rate).

The arrival rate vector
$\bm{\lambda}(t_{n})\in\mathbb{{R}^{+}}^{|S|}=\big{(}\lambda_{s}(t_{n})\
\forall\ s\big{)}^{\text{T}}$ is supportable if there exists a schedule under
which,

$\underset{Q\rightarrow\infty}{\text{lim}}\
\underset{n\rightarrow\infty}{\text{lim}}\text{P}\big{(}|\bm{q}(t_{n})|\geq
Q\big{)}=0,$ (7)

where $|\bm{q}(t_{n})|:=\underset{s}{\Sigma}|q_{s}(t_{n})|$ is the sum of the
number of demands in the queue of each session in time slot $t_{n}$. That is,
$\bm{\lambda}(t_{n})$ is supportable if the probability that the total queue
length becomes infinite is zero.

######  Definition II.8 (Capacity Region).

The capacity region of an EGS is the set of arrival rate vectors that are
supportable by the EGS. For each rate vector $\bm{\lambda}$ in the capacity
region, there exists some scheduling routine such that an EGS operating under
that scheduling algorithm can support the rate vector $\bm{\lambda}$.

If the rate vector $\bm{\lambda}$ falls outside the capacity region, the EGS
cannot support it under any scheduling algorithm, leading to unpredictable
performance. The goal of moderating the rate vector through the Rate Control
Protocol (RCP) is twofold: first, to keep it within the capacity region, and
second, to maximize resource utilization by saturating the capacity region,
thus fully leveraging the potential of the EGS to facilitate entanglement
generation.

######  Theorem II.1 (Capacity Region).

Let $x_{s}$ be the maximum number of resources that can be allocated to a
session $s$ per time slot. For each resource, $p_{\emph{\text{gen}}}$ is the
probability that a communication session allocated the resource for one time
slot will successfully create an entangled pair. The capacity region of an EGS
with R resources is the set of rate vectors
$\bm{\lambda}\in\text{\emph{Int}}\mathcal{C}$, where $\mathcal{C}$ is defined
as:

$\mathcal{C}=\big{\\{}\bm{\lambda}:\bm{\lambda}\geq\bm{0},\
\sum_{s}\lambda_{s}\leq\lambda_{\text{\emph{EGS}}},\text{ and
}\lambda_{s}\leq\lambda^{\max}_{\text{\emph{gen}},s}\ \forall\ s\in S\\},$ (8)

$\lambda_{\text{\emph{EGS}}}=R\cdot p_{\text{\emph{gen}}}$ and
$\lambda^{\max}_{\text{\emph{gen}},s}=x_{s}\cdot p_{\text{\emph{gen}}}$.
Moreover, maximum weight scheduling (Definition II.6) is throughput optimal
and supports any rate vector $\bm{\lambda}\in\emph{\text{Int}}\mathcal{C}$.
For proof, see Section V-A2.

The first requirement of $\mathcal{C}$ states that all request rate vectors
must be positive, meaning every component of the rate vector must be positive
or zero $(\bm{\lambda}\geq\bm{0}\Leftrightarrow\lambda_{s}\geq 0\ \forall s\in
S$). The second requirement enforces that the total rate of entanglement
requested from the EGS, $\underset{s}{\sum}\lambda_{s}$, cannot exceed the
total average service rate of the EGS, $R\cdot p_{\text{gen}}$. The final
requirement states that the request rate $\lambda_{s}$ of any communication
session $s$ must not exceed the maximum average service rate that can be
allocated to the communication session, $x_{s}\cdot p_{\text{gen}}$.

###  II-C Constraints

We assume that there are two types of constraints on the sequence of target
rates set by a session. The first is a minimum rate of entanglement generation
$\lambda^{\min}_{s}$; below this rate, session $s$ cannot obtain sufficient
entangled pairs within a short enough period of time in order to enable its
target application. The second constraint $\lambda_{u}\ \forall u\in U$ is an
upper limit on the rate at which each node $u$ can generate and/or make use of
entanglement across all of the sessions that it is involved in. This parameter
can capture a range of technical limitations of the quantum nodes, including a
limited rate of entanglement generation or a limited speed of writing
generated entanglement to memory, hence temporarily decreasing the
availability of the node for engaging in further entanglement generation
immediately following the successful production of a pair.

##  III RCP Algorithm

An algorithm moderating competition for EGS resources enables the possibility
of introducing a notion of fairness in how resources are allocated amongst
competing communication sessions and ensuring that the resources are fully
utilized. We consider a situation where the rate vector produced by any such
algorithm is constrained by the maximum service rate of the switch, as
described by the capacity region $\mathcal{C}$, as well as the node or user
level constraints described by $\lambda_{u}\ \forall u$ and
$\lambda^{\min}_{s}\ \forall s$. In the framework of NUM, we pose an
optimization problem where each communication session $s$ is associated with a
utility function $f_{s}(\lambda_{s}(t_{n})):\mathbb{R}\mapsto\mathbb{R}$,
which encodes the benefit $s$ derives from the rate vector
$\bm{\lambda(t_{n})}$. We apply the theory of Lagrange multipliers and
Lagrangian duality (see [25] for detailed coverage) to formulate and analyze
the optimization problem. We then derive the RCP (Algorithm III) as the
solution to this problem.

The primal problem is to maximize the aggregate utility or the total benefit
that users derive from the EGS by maximizing the sum of the utility functions,
including the constraints by the use of Lagrange multipliers. The dual problem
is to determine an optimal vector of Lagrange multipliers. In the case where
there is no duality gap [25], a solution to the dual problem is equivalent to
a solution of the primal problem. The vector of Lagrange multipliers
$\bm{p}(t_{n+1})=\big{(}p_{c}(t_{n}),p_{u}(t_{n})\ \forall
u\big{)}\in{\mathbb{R}^{+}}^{(1+N)}$, with components for the processor and
each node, is denoted as the price vector in our algorithm and serves as a
measure of the competition for resources amongst the communication sessions.
Define $S(u):=\\{s:u\in s\\}\subseteq S$ to be the subset of communication
sessions in which node $u$ participates. In each communication session one
node is designated to communicate demand to the switch and the other node is
secondary (see Definition II.3). Note that $u\in s\Leftrightarrow s\in S(u)$.
The feasible rate region of the communication session $s$ is,

$\Lambda_{s}:=\\{\lambda_{s}:\lambda^{\min}_{s}\leq\
\lambda_{s}\leq\lambda^{\max}_{\text{gen},s}\\}\ \forall\ s,$ (9)

and the feasible region for a rate vector $\bm{\lambda}$ is,

$\Lambda=\underset{s}{\bigcup}\Lambda_{s}.$ (10)

We make the following two assumptions on the utility function $f_{s}$ of each
communication session $s$:

  * A1:

On the interval
$\Lambda_{s}=[\lambda^{\min}_{s},\lambda^{\max}_{\text{gen},s}]$ the utility
functions $f_{s}$ are increasing, strictly concave, and twice continuously
differentiable;

  * A2:

The curvatures of all $f_{s}$ are bounded away from zero on $\Lambda_{s}$. For
some constant $\alpha_{s}>0$,

$\displaystyle-f^{{}^{\prime\prime}}_{s}(\lambda_{s})$
$\displaystyle\geq\frac{1}{\alpha_{s}}>0\ \forall\ \lambda_{s}\in\Lambda_{s}.$

To ensure feasibility and satisfy the Slater constraint qualification [25], in
addition to assumptions A1 and A2 it is necessary that the rate vector with
components equal to the minimal rates of each communication session is an
interior point of the constraint set,

$\displaystyle\sum_{s}\lambda^{\min}_{s}$
$\displaystyle<\lambda_{\text{EGS}};$ (11) $\displaystyle\underset{s\in
S(u)}{\sum}\lambda^{\min}_{s}$ $\displaystyle<\lambda_{u}\ \forall\ u.$ (12)

Algorithm 1: Rate Control Protocol (RCP)

x

Processor’s Algorithm: At times $t_{n}=1,\ 2,\cdots,$ the processor:

  1. 1.

receives rates $\lambda_{s}(t_{n})$ from all communication sessions $s\in S$;

  2. 2.

computes a new central price,

$\displaystyle p_{c}(t_{n+1})=\big{[}$
$\displaystyle\frac{1}{\lambda_{\text{EGS}}}\sum_{s}q_{s}(t_{n})$
$\displaystyle+\theta_{c}\big{(}\sum_{s}\lambda_{s}(t_{n})-\lambda_{\text{EGS}}\big{)}\big{]}^{+},$
(13)

where $\theta_{c}$ is a constant step-size for the central price;

  3. 3.

broadcasts the new central price $p_{c}(t_{n+1})$ to all communication
sessions $s\in S$.

Network Node u’s Algorithm: At times $t_{n}=1,\ 2,\cdots,$ network node $u$:

  1. 1.

marks the subset of communication sessions $\text{COMM}(u)\subseteq S(u)$
involving node $u$ for which it is the designated communication node;

  2. 2.

receives from every secondary node $u^{\prime}$ the price
$p_{u^{\prime}}(t_{n})$ for each communication session
$s=(u,u^{\prime})\in\text{COMM}(u);$

  3. 3.

computes a new node price,

$\displaystyle p_{u}(t_{n+1})=\big{[}$
$\displaystyle\frac{1}{\lambda_{u}}\underset{s\in S(u)}{\sum}q_{s}(t_{n})$
$\displaystyle+\theta_{u}\big{(}\underset{s\in
S(u)}{\sum}\lambda_{s}(t_{n})-\lambda_{u}\big{)}\big{]}^{+},\ \forall\ u,$
(14)

where $\theta_{u}\ \forall u$ is a constant step-size for each node, which may
be fixed or differ from node to node;

  4. 4.

communicates the new price $p_{u}(t_{n+1})$ to the communication node from
every communication session $s\in S(u)\setminus\text{COMM}(u)$ in which $u$ is
a secondary node;

  5. 5.

receives from the switch the central price $p_{c}(t_{n+1})$;

  6. 6.

computes the new rate for every communication session $s\in\text{COMM}(u)$,

$\lambda_{s}(t_{n+1})=\Bigg{[}\Big{(}\frac{\text{d}f_{s}}{\text{d}\lambda_{s}}\Big{)}^{-1}\big{(}\bm{p}(t_{n+1})\big{)}\Bigg{]}^{\lambda^{\max}_{\text{gen},s}}_{\lambda^{\min}_{s}},$
(15)

where $[z]^{M}_{m}=\max\big{(}\min(z,\ M),m\big{)}$ and
$\bm{p}(t_{i})=\big{(}p_{c}(t_{i}),\ p_{u}(t_{i})\ \forall\ u\big{)}$ is the
vector of prices pertaining to time slot $t_{i}$;

  7. 7.

communicates the new rate $\lambda_{s}(t_{n+1})$ to the EGS processor, for
every communication session $s\in\text{COMM}(u)$.

###  III-A Derivation

Formally, the RCP yields rate vectors which solve the Primal Problem:

$\underset{\bm{\lambda}\in\Lambda}{\max}\
F(\bm{\lambda}):=\sum_{s}f_{s}(\lambda_{s}),\\\ $ (16)

subject to,

$\displaystyle\sum_{s}\lambda_{s}$ $\displaystyle\leq\lambda_{\text{EGS}}$
(17) $\displaystyle\sum_{s\in S(u)}\lambda_{s}$ $\displaystyle\leq\lambda_{u}\
\forall u.$ (18)

The Lagrangian, which includes the constraints (17), (18) with a vector of
Lagrange multipliers $\bm{p}=(p_{c},p_{u}\ \forall u)\geq\bm{0}$ together with
the objective function (16), is given by

$\displaystyle L(\bm{\lambda},\bm{p})=$
$\displaystyle\sum_{s}f_{s}(\lambda_{s})-p_{c}\bigg{(}\sum_{s}\lambda_{s}-\lambda_{\text{EGS}}\bigg{)}$
$\displaystyle-\underset{u}{\sum}p_{u}\bigg{(}\underset{s\in
S(u)}{\sum}\lambda_{s}-\lambda_{u}\bigg{)}.$ (19)

We identify that the problem is separable in the communication sessions, $S$,
and re-write the Lagrangian in separable form,

$\displaystyle
L(\bm{\lambda},\bm{p})=\sum_{s}l_{s}(\lambda_{s})+p_{c}\lambda_{\text{EGS}}+\sum_{u}p_{u}\lambda_{u},$
(20)

where $l_{s}(\lambda_{s})$ is defined as

$l_{s}(\lambda_{s}):=f_{s}(\lambda_{s})-\lambda_{s}p_{c}-\lambda_{s}\underset{u\in
s}{\sum}p_{u},$

and we make use of the equivalence

$\displaystyle\sum_{u}p_{u}\sum_{s\in
S(u)}\lambda_{s}=\sum_{s}\lambda_{s}\sum_{u\in s}p_{u}.$

A rate vector $\bm{\lambda}^{*}$ is a local maximum of (16) if it satisfies
the optimality condition [25],

$\gradient_{\lambda_{s}}F(\bm{\lambda}^{*})^{T}(\bm{\lambda}-\bm{\lambda}^{*})\leq
0\ \forall\bm{\lambda}\in\ \Lambda.$ (21)

If moreover $F(\bm{\lambda})$ is concave over $\Lambda$, then (21) is also
sufficient for $\bm{\lambda}^{*}$ to maximize $F(\bm{\lambda})$ over $\Lambda$
[25] (it is also a global maximum).

To obtain a $\bm{\lambda}^{*}$ satisfying both the optimality condition (21)
and the constraints (17), (18) we set the gradient with respect to rate of
each communication session of the Lagrangian to zero,

$\gradient_{\lambda_{s}}L=\sum_{s}\frac{\text{d}l_{s}(\lambda_{s})}{\text{d}\lambda_{s}}=0.$

The maximization in the primal problem (16) is constrained to the feasible
rate region defined by (9), (10). To restrict solutions to the problem domain,
any $\tilde{\bm{\lambda}}^{*}\cancel{\in}\Lambda$ is projected component-wise
so that $\tilde{\lambda}^{*}_{s}\mapsto\lambda^{*}_{S}\in\Lambda_{s}\ \forall
s$. With the assumptions in (11), (12) there exists at least one set of
Lagrange multipliers [25]. In terms of a given vector of Lagrange multipliers
$\bm{p}$, an optimal rate vector $\bm{\lambda}^{*}$ satisfies,

$\lambda^{*}_{s}=\Bigg{[}\bigg{(}\frac{\text{d}f_{s}}{\text{d}\lambda_{s}}\bigg{)}^{-1}(\textbf{p})\Bigg{]}^{\lambda^{\max}_{\text{gen},s}}_{\lambda^{\min}_{s}}\
\forall\ s,$ (22)

where $[z]^{M}_{m}=\max\bigg{(}\min\big{(}z,\ M\big{)},m\bigg{)}$. To obtain a
$\bm{\lambda}^{*}$, it remains to obtain a vector of Lagrange multipliers.

An optimal vector $\bm{p}^{*}$ of Lagrange multipliers is a solution to the
Dual Problem:
Select $\bm{p}=(p_{c},\ p_{u}\ \forall\ u)$ so as to achieve,

$\underset{\bm{p}\geq\textbf{0}}{\text{inf }}D(\textbf{p}),$ (23)

where the dual objective function $D(\textbf{p})$ is defined as,

$D(\textbf{p})=\underset{\bm{\lambda}\in\Lambda}{\text{sup}}\
L(\bm{\lambda},\bm{p}).$ (24)

With assumptions A1, A2 and (11, 12), the problem satisfies the Slater
constraint qualification and has no duality gap [25], meaning a solution to
the dual problem is also a solution to the primal problem. Define
$\bm{\lambda}^{*}$ to be a rate vector that maximizes $L(\bm{\lambda},\
\bm{p})$. A vector of Lagrange multipliers $\bm{p}^{*}$ is an optimal solution
to the dual problem if it satisfies the optimality condition,

$\gradient_{p}D(\bm{p}^{*})^{T}(\bm{p}-\bm{p^{*}})\geq 0\ \forall\bm{p}\geq
0.$ (25)

Gradient projection is a type of algorithm where in order to solve an
optimization problem such as the dual problem, (23), with respect to a vector
$\bm{p}$, one starts by selecting some initial vector $\bm{p}(0)$ and
iteratively adjusting $\bm{p}(t_{n})\mapsto\bm{p}(t_{n+1})$ by making steps in
the opposite direction of the gradient of the objective function. We introduce
a vector of step-sizes $\bm{\theta}=(\theta_{c},\theta_{u}\ \forall
u)\in\mathbb{R}^{1+N}$. The components of $\gradient_{p}D(\bm{p})$ are,

$\displaystyle\frac{\partial D(\bm{p})}{\partial p_{c}}$ $\displaystyle=-\
\bigg{(}\sum_{s}\lambda^{*}_{s}-\lambda_{\text{EGS}}\bigg{)};$ (26)
$\displaystyle\frac{\partial D(\bm{p})}{\partial p_{u}}$ $\displaystyle=-\
\bigg{(}\underset{s\in S(u)}{\sum}\lambda^{*}_{s}-\lambda_{u}\bigg{)}\
\forall\ u.$ (27)

An implementation of the gradient projection algorithm is to iteratively
adjusting the Lagrange multipliers according to,

$\displaystyle p_{c}(t_{n+1})$
$\displaystyle=\big{[}p_{c}(t_{n})+\theta_{c}\big{(}\sum_{s}\lambda^{*}_{s}(t_{n})-\lambda_{\text{EGS}}\big{)}\big{]}^{+};$
(28) $\displaystyle p_{u}(t_{n+1})$
$\displaystyle=\big{[}p_{u}(t_{n})+\theta_{u}\big{(}\underset{s\in
S(u)}{\sum}\lambda^{*}_{s}(t_{n})-\lambda_{u}\big{)}\big{]}^{+},\ \forall\ u,$
(29)

where $\lambda^{*}_{s}(t_{n})=\lambda^{*}_{s}\big{(}\bm{p}(t_{n})\big{)}$ is
given by inputting the vector of Lagrange multipliers in (22). An
implementation of the algorithm necessitates identifying parameters in the
system that correspond to the components of the vector of Lagrange
multipliers. We note that the centralized price $p_{c}(t_{n})$ and the user
prices $p_{u}(t_{n})\ \forall\ u$, have respectively, the same dynamics as the
total queue lengths and the sum total of the session queue lengths in which
user $u$ participates (6). Therefore, we make the following identifications,

$\displaystyle p_{c}(t_{n})$
$\displaystyle\leftrightarrow\frac{1}{\lambda_{\text{EGS}}}\sum_{s}q_{s}(t_{n});$
$\displaystyle p_{u}(t_{n})$
$\displaystyle\leftrightarrow\frac{1}{\lambda_{u}}\sum_{s\in
S(u)}q_{s}(t_{n})\ \forall u.$

Note that these identifications are not unique, since the only strict criteria
on the identification is that the queue dynamics generated by (6) match the
dynamics of (28) and (29), whereas the scaling is arbitrary. For more
information on the interpretation of Lagrange multipliers as prices in
communication networks, see [22, 23].

###  III-B Convergence

The RCP is a gradient projection algorithm with constant step-sizes from the
vector $\bm{\theta}\in\mathbb{R}^{1+N}=(\theta_{c},\theta_{u}\ \forall u)$.
Establishing that the algorithm converges is crucial to ensure that it yields
solutions that effectively address the problem it is designed to solve. To
establish convergence, we follow a similar treatment as in [26].

######  Theorem III.1 (RCP Convergence).

Suppose assumptions A1 and A2 and the constraints (11, 12) are satisfied and
each of the the step-sizes $\theta_{r}\in\\{\theta_{c},\theta_{u}\ \forall
u\\}$ satisfies $\theta_{r}\in(0,2/\overline{\alpha}|S|)$, where
$\overline{\alpha}=\underset{s\in S}{\max}\ \alpha_{s}$ with $\alpha_{s}$ the
curvature bound of assumption A2, and $|S|$ is the number of communication
sessions. Then, starting from any initial rate $\bm{\lambda}(0)\in\Lambda$ and
price $\bm{p}(0)\geq\bm{0}$ vectors, every accumulation point
$\big{(}\hat{\bm{\lambda}},\hat{\bm{p}}\big{)}$ of the sequence over time
slots $\\{\big{(}\bm{\lambda}(t_{n}),\bm{p}(t_{n})\big{)}\\}_{t_{n}}$
generated by the RCP is primal-dual optimal. For proof, see Section V-A3.

##  IV Case Study

Figure 2: The RCP drives the sum of the demanded rates of entanglement
generation across all communication sessions,
$\underset{s}{\Sigma}\lambda_{s}(t_{n})$, to converge with respect to the
sequence of time slots to the maximum average entanglement generation rate of
the EGS, $\lambda_{\text{EGS}}$. The EGS has $R=3$ resources, the probability
of entanglement generation is $p_{\text{gen}}=0.05$, and the EGS is connected
to $N=20$ (top), $N=50$ (middle) and $N=100$ (bottom) nodes. The total number
of communication sessions served are $|S|=19,\ 123,\ \text{ and }495$ in the
top, middle, and bottom plots, respectively. Black dotted lines indicate the
convergence times, $\Delta\tau$. The observed values for the tightness of
convergence, $\delta$, are $\delta_{1}=0.12$, $\delta_{2}=0.035$ and
$\delta_{3}=0.012$. Step-sizes $(\theta_{c},\theta_{u}\ \forall u)$ were all
$1/(40\cdot\lambda_{\text{EGS}})$.

To illustrate use of the RCP we associate a log utility function with each
session,

$f_{s}(\lambda_{s})=\log(\lambda_{s})\ \forall\ s\in S.$ (30)

Log utility functions are suitable when throughput is the target performance
metric, and a set of sessions all employing log utility functions will have
the property of proportional fairness. In such a system, if the proportion by
which one session rate changes is positive, there is at least one other
session for which the proportional change is negative [23]. For compatibility
with Theorem III.1 note that log utility functions satisfy A1, and A2 is
satisfied with $\alpha_{s}=(\lambda^{\max}_{\text{gen},s})^{2}\ \forall s$.

Although the convergence theorem only guarantees asymptotic convergence of the
sequence $\\{\big{(}\bm{\lambda(t_{n})},\bm{p(t_{n})}\big{)}\\}_{t_{n}}$ to an
optimal rate-price pair $\big{(}\hat{\bm{\lambda}},\hat{\bm{p}}\big{)}$, in
any realization of an EGS one expects that the convergence time $\Delta\tau$,
the number of time slots that the RCP must run before convergence is attained,
is finite. In addition, it is practically relevant to characterize the
tightness of convergence $\delta$, or the maximum size of fluctuations about
the optima.

If an EGS is connected to $N$ nodes, there are $|S|_{\max}=\binom{N}{2}$
possible sessions. We assume that in a real network not all pairs of users
require shared entanglement. In Fig. 2 we numerically investigate the
convergence time and tightness of convergence, $(\Delta\tau,\delta)$, for an
EGS with $R=3$ resources and $p_{\text{gen}}=0.05$ connected to $N=20,\ 50$
and $100$ users, where the number of sessions is restricted to
$|S|=0.1\cdot|S|_{\max}$ by randomly sampling $10\%$ of the possible sessions.
In these simulations we set $x_{s}=1\ \forall s$, and average over 1000
independent runs of the simulation, each using the same set of sessions.

The reported convergence times $\Delta\tau$ are the number of time slots that
occur before the sum of demand rates $\underset{s}{\Sigma}\lambda_{s}(t_{n})$
first crosses the optimal value $\lambda_{\text{EGS}}$. Reporting of the
tightness of convergence, $\delta$, is based on the maximum size of
fluctuations of $\underset{s}{\Sigma}\lambda_{s}(t_{n})$ about
$\lambda_{\text{EGS}}$ following $\Delta\tau$. As the number of sessions
hosted by an EGS increases, we observe a trade-off between $\Delta\tau$ and
$\delta$. When the number of sessions is lower, $\Delta\tau$ is shorter but
$\delta$ is larger. We have performed additional simulations which indicate
that increasing the step size used in the RCP can be used to trade larger
$\delta$ for somewhat shorter $\Delta\tau$.

If constraint changes occur slowly compared to $\Delta\tau$, Theorem III.1
implies that the RCP should re-establish convergence to a new optimal rate and
price vector pair,
$(\hat{\bm{\lambda}},\hat{\bm{p}})\mapsto(\hat{\bm{\lambda}}^{\prime},\
\hat{\bm{p}}^{\prime})$. In a real EGS system it is possible that the number
of available resources will not be static in time, as resources may require
periodic downtime for calibration. The effect of a change in the number of
resources $R\mapsto R^{\prime}$ changes the maximum service rate
$\lambda_{\text{EGS}}=R\cdot
p_{\text{gen}}\mapsto\lambda^{\prime}_{\text{EGS}}=R^{\prime}\cdot
p_{\text{gen}}$. To validate the robustness of the algorithm against such
constraint changes we simulate EGS systems originally equipped with $R=3$
resource nodes, where after every $10,000$ time-slots one of the resources may
either be taken offline for calibration or an offline resource may be returned
to service. Fig. 3 demonstrates that the RCP successfully re-establishes
convergence of $\underset{s}{\Sigma}\lambda_{s}(t_{n})$ about
$\lambda^{\prime}_{\text{EGS}}$ following these constraint changes in an EGS
system connected to $N=50$ nodes, serving $|S|=123$ communication sessions.

In Fig. 3 we record the sequence of convergence times, $\\{\Delta\tau\\}$,
after each constraint change as the first time-steps where
$\underset{s}{\Sigma}\lambda_{s}(t_{n})$ crosses
$\lambda^{\prime}_{\text{EGS}}$. To calculate the tightness of convergence,
$\delta$, we first calculate the sequence of $\\{\delta^{\prime}\\}$, the size
of the maximum fluctuations about $\lambda^{\prime}_{\text{EGS}}$ following
each $\Delta\tau^{\prime}$ and set $\delta=\max(\\{\delta^{\prime}\\})$.
Notably, every subsequent $\Delta\tau^{\prime}<\Delta\tau$ and the achieved
$\delta$ is equal to that observed when there are no changes to the constraint
set in Fig. 2 (middle plot, $\delta_{2}$) for an EGS with the same number of
nodes, serving the same number of communication sessions. Additional
simulations of EGS systems connected to various numbers of nodes ranging from
$10$ to $100$, with random changes to the number of resources after every
$10,000$ time-steps, suggest that the data in Fig. 3 is representative.
Specifically, in each case investigated the absolute relative difference,

$\displaystyle\frac{|\delta-\tilde{\delta}|}{\tilde{\delta}}<1$

between the achieved tightness of convergence when there are ($\delta$) and
are not ($\tilde{\delta}$) changes to the constraints is less than $1$.

Figure 3: In response to changes in the number of resources available at the
EGS ($R\rightarrow R^{\prime}$), the RCP drives the sum of the demanded rates
of entanglement generation across all communication sessions,
$\underset{s}{\Sigma}\lambda_{s}(t_{n})$, to converge with respect to the
sequence of time slots to the updated maximum average entanglement generation
rate of the EGS, $\lambda_{\text{EGS}}=R^{\prime}\cdot p_{\text{gen}}$. In
simulation, an EGS connected to $N=50$ nodes, serving $|S|=123$ communication
sessions, is originally equipped with $R=3$ resources. After every $10,000$
time-slots, one of the resources may either be taken offline for calibration
or an offline node may be returned to service. Black dashed lines indicate the
convergence, $\Delta\tau$ calculated for every $R^{\prime}$ (initially $R$).
We observe and overall tightness of convergence of $\delta=0.035$, identical
to that observed in Fig. 3 for the EGS operated with fixed $R=3$ and with the
same $N,\ |S|$. Step-sizes $(\theta_{c},\theta_{u}\ \forall u)$ were all
$1/(10\cdot\lambda_{\text{EGS}})$.

The constraints $\\{\lambda_{u}\\}_{u}$ on the capabilities of nodes appear in
(3) and therefore affect both the prices calculated by the nodes and the rates
set by communication sessions in (15). Since these constraints limit the total
rate at which a node can submit demands summed across all of the communication
sessions in which it participates, it is expected that uniform settings of
$\\{\lambda_{u}\\}_{u}$ yield rate vectors under the RCP where
$\\{\lambda_{s}(t_{n})\\}_{s}$ are approximately uniform. In contrast, if the
node constraints are non-uniform amongst the nodes, it is expected that the
RCP yields rate vectors with larger differences between the rates set by each
communication session. In Fig. 4 we investigate the effect of different
settings for these constraints by plotting the difference between the average
maximum $\underset{s}{\max}\\{\lambda_{s}(t_{n})\\}_{s}$ and minimum
$\underset{s}{\min}\\{\lambda_{s}(t_{n})\\}_{s}$ communication session rates
yielded by the RCP for two different settings of the constraints. In the first
setting, node constraints are set uniformly as
$\lambda_{u}=\big{(}(|S|-1)/2\big{)}\cdot p_{\text{gen}}\ \forall u$ so that
in practice the algorithm functions as if the network node constraints have
been removed. In the other setting there are three possible constraint values:
a quarter of the nodes sampled at random have $\lambda_{u}=1.5\cdot
p_{\text{gen}}$, half of the nodes have $\lambda_{u}=p_{\text{gen}}$, and a
quarter of the nodes have $\lambda_{u}=0.5\cdot p_{\text{gen}}$. Fig. 4
confirms that the difference between the average maximum rate and the average
minimum rate requested by any session at time-step $t_{n}$ is one or more
orders of magnitude larger when nodes are associated with the non-uniform
constraint set. The uniform node constraint setting led to communication
sessions updating their rates of demand submission to be nearly uniform across
all communication sessions.

Figure 4: Differences between the average maximum rate and average minimum
rate requested by any communication session in time-slot $t_{n}$, for an EGS
connected to $N=20$ (top), $N=50$ (middle) and $N=100$ (bottom) nodes serving
$|S|=19,\ 123,\text{ and }495$ communication sessions, respectively. As
described in the main text, nodes are either associated with a uniform and
effectively un-restricted set of capabilities or a non-uniform and more
restricted set of capabilities. Step-sizes $(\theta_{c},\theta_{u}\ \forall
u)$ were all $1/(40\cdot\lambda_{\text{EGS}})$.

##  V Discussion

We have presented the first control architecture for an EGS. The architecture
is tailored to a simple system model. As a natural extension of this work, a
refined version of the control architecture can be developed to suit a more
versatile physical model. In the following discussion, we explore
considerations for the development of a second generation control
architecture.

In this work we assume a demand model in which user generated demands are
fully parameterized by a desired rate of entanglement generation.
Specifically, every communication session $s$ sets $\lambda_{s}(t_{n})$,
updated once per time-slot and specifies the constraint parameter
$\lambda^{\min}_{s}$ which defines the minimum rate of entanglement generation
the communication session must receive in order to enable some target
application. While this model is mathematically simple, it may not fully
address real application requirements on a physical quantum network. Real
applications may require the simultaneous existence of a number of entangled
pairs, each with some minimum fidelity and it is possible that applications
need such packets of pairs to be supplied periodically over a longer
application run-time. In the future, it may therefore be relevant to consider
a demand model wherein communication sessions submit demands for packets of
entanglement generation. A packet would be fully specified by the desired
number of entangled pairs, a minimum fidelity for the pairs, some maximum
window of time between the generation time of the first and last entangled
pair of the request, and possibly some rate at which the demand with the
preceding parameters should be repeatedly fulfilled.

The discussed model assumes that user controlled nodes can engage in multiple
entanglement generation tasks in parallel. We do not impose restrictions on
simultaneously scheduling communication sessions. Hence, it is possible for
communication sessions $s$ and $s^{\prime}$ with node $u\in s,s^{\prime}$ to
be scheduled simultaneously. Additionally, we consider the option of assigning
multiple resource nodes to a single communication session in any time-slot.
Therefore, we consider nodes with an unrestricted number of qubits and
independent physical connections to the EGS. A subtlety we do not address here
is that allocating multiple resources to a single communication session may
require temporal multiplexing in the scheduling of individual entanglement
generation attempts, especially when the multiple qubits of a single node are
coupled to the physical connection via a single output. Furthermore, for nodes
consisting of a single quantum processor, it may not be possible to calibrate
the node to simultaneously engage in entanglement generation attempts with
multiple partner nodes, even if the node has unlimited qubits. To capture this
physical feature, it will be interesting to include the restriction of
scheduling only non-overlapping communication sessions in the design of
scheduling routines for future EGS control architectures.

The control architecture for an EGS relies on precise timing synchronization.
Our model assumes that at both the control and physical layers, all
communication sessions can adhere to the time slots defined by the EGS
processor. Tight synchronization of timing is possible at the physical layer,
which controls the quantum devices and coordinates the exact timing of
entanglement generation attempts. However, tight timing synchronization of any
type of classical communication may be a considerable challenge in any real
world application. In particular, such coordination is a serious challenge if
there are non-uniform communication times between any of the nodes and the EGS
or between any of the node pairs. To reduce the timing requirements and
possibly make the control architecture delineated here executable on a real-
world system, it is possible to consider the processor of the EGS simulating
the actions of the nodes. To do so, the processor would locally run the RCP
and simulate the generation of demands originating from the user operated
nodes by simply adding demands to the queues based on the rates output by the
RCP. Such an approach trades the difficulty of timing synchronization for the
requirement of increased power of the classical processor at the EGS. To
reduce the need for timing synchronization, a second generation architecture
may be designed which does not rely on fixed, centrally defined time slots.

###  V-A Proofs

####  V-A1 Outline of goals to prove

In this section we will prove two theorems to establish the results quoted in
the main body of the article. The results are as follows:

  1. 1.

The capacity region of the EGS is the set of demand arrival rate vectors fully
contained in the set $\mathcal{C}$ (8) and maximum weight scheduling
(Definition II.6) supports any rate vector from within $\mathcal{C}$ (Theorem
II.1). To establish the capacity region, we first prove a proposition stating
that any rate vector $\bm{\lambda}\ \cancel{\in}\ \mathcal{C}$ necessarily
results in divergent queues. We then prove a second proposition establishing
at once that any rate vector $\bm{\lambda}\in\text{Int}\mathcal{C}$ is
supportable under some scheduling algorithm and that maximum weight scheduling
is such a scheduling algorithm. Therefore, we also demonstrate that maximum
weight scheduling is throughput optimal.

  2. 2.

The RCP, Algorithm III, results in the calculation of a sequence of rate and
price vector pairs $\big{(}\bm{\lambda}(t_{n}),\bm{p}(t_{n})\big{)}$ which
converge to optimal solutions $\big{(}\hat{\bm{\lambda}},\
\hat{\bm{p}}\big{)}$ of the primal and dual problems, defined in Section III
(Theorem III.1).

####  V-A2 Proof of Theorem II.1

First it is to be shown that no rate vector $\bm{\lambda}\ \cancel{\in}\
\mathcal{C}$ of an EGS with $R$ resources is supportable under any scheduling
algorithm.

######  Proposition V.1.

If $\bm{\lambda}\ \cancel{\in}\ \mathcal{C}$, no scheduling algorithm can
support $\bm{\lambda}$.

###### Proof.

There are three cases where $\bm{\lambda}\ \cancel{\in}\ \mathcal{C}$,

  1. 1.

$\underset{s}{\sum}\lambda_{s}>R\cdot p_{\text{gen}}$, or

  2. 2.

$\lambda_{s^{*}}>x_{s^{*}}\cdot p_{\text{gen}}\text{ for some }s^{*}\in S$.

  3. 3.

$\bm{\lambda}$ is not non-negative ( $\exists\ \lambda_{s^{*}}<0$ for at least
some $s^{*}\in S$).

In the third case, the node pair corresponding to session $s^{*}$ has set a
non-physical rate and the rate must be changed. The proof for case $(2)$ is
very similar to case $(1)$ and equations from the first case are re-used or
modified to complete the proof of case $(2)$. The main strategy of the proof
relies on Definition II.7; a rate vector $\bm{\lambda}\ \cancel{\in}\
\mathcal{C}$ is not supportable if $\bm{\lambda}$ causes the queue lengths at
the EGS processor to diverge with probability 1, regardless of scheduling
algorithm. To prove the proposition in each case, it serves to calculate the
total queue length.

Proposition V.1 (1): Suppose $\underset{s}{\sum}\lambda_{s}>R\cdot
p_{\text{gen}}.$ Then, $\exists\ \epsilon>0$ such that

$\displaystyle\sum_{s}\lambda_{s}\geq R\cdot p_{\text{gen}}+\epsilon.$ (31)

Assume that the initial length of each queue is finite. The sum of queue
lengths at time step $t_{n+1}$, $\underset{s}{\sum}q_{s}(t_{n+1})$ is,

$\displaystyle\sum_{s}q_{s}(t_{n+1})$
$\displaystyle=\sum_{s}\big{[}q_{s}(t_{n})+a_{s}(t_{n})-g_{s}(t_{n})\big{]}^{+}$
$\displaystyle\geq\sum_{s}\big{(}q_{s}(t_{n})+a_{s}(t_{n})-g_{s}(t_{n})\big{)}$
$\displaystyle\geq\sum_{s}\Big{(}q_{s}(t_{1})+\overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\big{(}a_{s}(t_{i})-g_{s}(t_{i})\big{)}\Big{)}$
(32)

where $a_{s}(t_{i})$ is the integer number of demands submitted by
communication session $s$ at time step $t_{i}$ and $g_{s}(t_{i})$ is the
integer number of successfully generated entangled pairs between the nodes
corresponding to communication session $s$ in time step $t_{i}$. The final
inequality in (32) follows from the previous inequality by repeated
application of (6). By the strong law of large numbers,

$\displaystyle\underset{n\rightarrow\infty}{\text{lim}}\ \frac{1}{t_{n}}\
\overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\ a_{s}(t_{i})=\lambda_{s}\
\forall\ s\in S\text{, with probability 1}.$ (33)

Recall that the number of successfully generated entangled pairs between the
nodes corresponding to communication session $s$ at time $t_{i}$ is a sample
from a binomial random process where the number of trials is set by
$M_{s}(t_{i})$ and the trial success probability is $p_{\text{gen}}$,

$\displaystyle g_{s}(t_{i})\sim\text{Bin}\big{(}M_{s}(t_{i}),\
p_{\text{gen}}\big{)}.$

By the strong law of large numbers,

$\displaystyle\underset{n\rightarrow\infty}{\text{lim}}\ \frac{1}{t_{n}}\
\overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\ g_{s}(t_{i})=M_{s}(t_{n})\cdot
p_{\text{gen}}\text{, with probability 1}.$ (34)

Since each feasible schedule satisfies $\underset{s}{\sum}M_{s}(t_{i})\leq R$,
it follows from (34) that

$\displaystyle\underset{n\rightarrow\infty}{\text{lim}}\ \frac{1}{t_{n}}\
\overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\ \sum_{s}\ g_{s}(t_{i})$
$\displaystyle=\sum_{s}\ \underset{n\rightarrow\infty}{\text{lim}}\
\frac{1}{t_{n}}\ \overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\ g_{s}(t_{i})$
$\displaystyle\leq R\cdot p_{\text{gen}},$ (35)

where we use the distribution property of limits, which is possible because
the individual limits (34) exist. Finally, by assumption (31) and (32, 33) and
(V-A2),

$\displaystyle\underset{n\rightarrow\infty}{\text{lim}}$ $\displaystyle\
\frac{1}{t_{n}}\ \sum_{s}q_{s}(t_{n+1})$
$\displaystyle\geq\underset{n\rightarrow\infty}{\text{lim}}\ \frac{1}{t_{n}}\
\sum_{s}q_{s}(t_{1})$
$\displaystyle\phantom{x}+\underset{n\rightarrow\infty}{\text{lim}}\
\frac{1}{t_{n}}\
\overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\big{(}\sum_{s}a_{s}(t_{i})-\sum_{s}M_{s}(t_{i})\big{)}$
$\displaystyle\geq\sum_{s}\ \lambda_{s}-R\cdot p_{\text{gen}}$
$\displaystyle\geq R\cdot p_{\text{gen}}+\epsilon-R\cdot p_{\text{gen}}$
$\displaystyle\geq\epsilon.$ (36)

Therefore, with probability 1,
$\underset{s}{\sum}q_{s}(t_{n})\rightarrow\infty$ as $n\rightarrow{\infty},$
so $\bm{\lambda}$ is not supportable, regardless of scheduling algorithm.

Proposition V.1 (2): Suppose that $\lambda_{s^{*}}>x_{s^{*}}\cdot
p_{\text{gen}}$ for some $s^{*}\in S$. Then, $\exists\ \epsilon>0$ such that,

$\displaystyle\lambda_{s^{*}}\geq x_{s^{*}}\cdot p_{\text{gen}}+\epsilon.$
(37)

In this case, we show that $\bm{\lambda}$ is not supportable by proving that
the queue $q_{s^{*}}(t_{i})$ of demands associated with communication session
$s^{*}$ diverges for large $t_{i}$. Recall (34) and note $M_{s}(t_{i})\leq
x_{s}\ \forall\ s,\ \forall\ t_{i}$. This inequality describes that a maximum
of $x_{s}$ heralding stations can be allocated any communication session $s$
in $t_{i}$. With this restriction, (34) becomes,

$\displaystyle\underset{n\rightarrow\infty}{\text{lim}}\ \frac{1}{t_{n}}\
\overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\ g_{s}(t_{i})\leq x_{s}\cdot
p_{\text{gen}}\ \forall s.$ (38)

Combining assumption (37) using (33), (38), and making repeated use of (6),

$\displaystyle\underset{n\rightarrow\infty}{\text{lim}}\ \frac{1}{t_{n}}\ $
$\displaystyle q_{s^{*}}(t_{n+1})$
$\displaystyle\geq\underset{n\rightarrow\infty}{\text{lim}}\ \frac{1}{t_{n}}\
q_{s^{*}}(t_{1})$
$\displaystyle\phantom{x}+\underset{n\rightarrow\infty}{\text{lim}}\
\frac{1}{t_{n}}\
\overset{t_{n}}{\underset{t_{i}=t_{1}}{\sum}}\big{(}a_{s^{*}}(t_{i})-g_{s^{*}}(t_{i})\big{)}$
$\displaystyle\geq\lambda_{s^{*}}-x_{s^{*}}\cdot p_{\text{gen}}$
$\displaystyle\geq x_{s^{*}}\cdot p_{\text{gen}}+\epsilon-x_{s^{*}}\cdot
p_{\text{gen}}$ $\displaystyle\geq\epsilon.$ (39)

Therefore, with probability $1$, $q_{s^{*}}(t_{n+1})\rightarrow\infty$ as
$n\rightarrow\infty$. Hence $\bm{\lambda}$ is not supportable. ∎

Proposition V.1 proved that rate vectors $\bm{\lambda}\ \cancel{\in}\
\mathcal{C}$ are not in the capacity region of the EGS. To finish proving
$\mathcal{C}$ is the capacity region of the EGS (Theorem II.1), it is
necessary to prove that any rate vector $\bm{\lambda}\in\mathcal{C}$ is
supportable under some scheduling algorithm. To do so, we prove that the
specific scheduling algorithm of Maximum Weight Scheduling (Definition II.6)
supports all arrival rate vectors fully contained in $\mathcal{C}$.

######  Proposition V.2.

Maximum Weight scheduling can support any arrival rate vector $\bm{\lambda}$
for which $\exists\epsilon>0$ such that
$(1+\epsilon)\bm{\lambda}\in\mathcal{C}$.

Modelling a queue vector as a Markov chain is a standard tool in queuing
theory [23]. This approach makes it possible to take advantage of the many
strong analytic results on the behaviour of Markov chains, which can then be
used to make statements about the queue vector. The vector
$\bm{q}(t_{n})=\big{(}q_{s}(t_{n}\big{)}\ \forall\ s)$ of queued demands from
each communication session maintained in the processor at $t_{n}$ can be
modelled as a Markov chain, with transitions given by (6). An irreducible
Markov chain has the property that any state $i$ of the chain is reachable
from any other state $j$. A positive recurrent Markov chain has the property
that from any state $i$, the expectation value of the time it will take to re-
visit any other state $j$ is finite. A queue vector, with specified dynamics,
that can be modelled as an irreducible Markov chain with the property of
positive recurrence will not diverge (i.e. is guaranteed to remain a finite
queue) [23]. The dynamics of such a queue vector are fixed by the arrival rate
vector and the scheduling routine, therefore if a queue vector can be modelled
as a positive recurrent Markov chain, the arrival rate vector is supportable
by the scheduling routine. To prove Proposition V.2 we demonstrate that the
queue vector is an irreducible Markov chain and use the Foster-Lyapunov
Theorem to prove that whenever $\bm{\lambda}$ lies strictly within
$\mathcal{C}$ the Markov chain is also positive recurrent. An equivalent
statement is that all rate vectors lying strictly within $\mathcal{C}$ are
supportable by some scheduling algorithm.

######  Theorem V.1 (Foster-Lyapunov Theorem [23]).

Let $\\{X_{k}\\}$ be an irreducible Markov chain with a state space
$\mathcal{S}$. Suppose that there exists a function $V\ :\
\mathcal{S}\rightarrow\mathbb{R}^{+}$ and a finite set
$\mathcal{B}\subseteq\mathcal{S}$ satisfying the following conditions:

  1. 1.

$\mathbb{E}[V(X_{k+1})-V(X_{k})|X_{k}=x]\leq-\epsilon$ if
$x\in\mathcal{B}^{c}$, for some $\epsilon>0$, and

  2. 2.

$\mathbb{E}[V(X_{k+1})-V(X_{k})|X_{k}=x]\leq A$ if $x\in\mathcal{B}$, for some
$A<\infty$.

Then the Markov chain $\\{X_{k}\\}$ is positive recurrent.

###### Proof of Proposition V.2.

First we establish that the queue vector, $\bm{q}(t_{i})\ \forall\ t_{i}$ is
an irreducible Markov chain. The queue vector, $\bm{q}(t_{i})$ is a Markov
chain with state space

$\displaystyle\mathcal{S}=\\{\bm{q}:\ $ $\displaystyle\bm{q}\text{ is
reachable from }\bm{0}$ $\displaystyle\text{ under the given scheduling
algorithm}\\}.$

Assume that $\bm{q}(t_{1})$ is finite and $\bm{q}(t_{1})\in\mathcal{S}$. It
follows from the definition of $\mathcal{S}$ that
$\bm{q}(t_{i})\in\mathcal{S}\ \forall t_{i}$ if $\bm{q}(t_{1})\in\mathcal{S}$.
Irreducibility of $\bm{q}(t_{i})\ \forall t_{i}$ requires that any state
$\bm{q}(t_{j})$ is reachable from any other state $\bm{q}(t_{i})$. By the
definition of the state space $\mathcal{S}$, it suffices to demonstrate that
from $\bm{q}(t_{i})$, the Markov chain can always return to $\bm{0}$. Under
Maximum Weight scheduling (Definition II.6), the processor always serves
$k(t_{i})$ demands per time-slot, where

$k(t_{i})=\text{max}\\{k\ :\ k\leq R\text{ and }k\leq\underset{s}{\Sigma}\
\min\big{(}|q_{s}(t_{i})|,\ x_{s}\big{)}\\},$

where $|q_{s}(t_{i})|$ is the number of demands in the queue for session $s$
in time-slot $t_{i}$ and $x_{s}$ is the maximum number of resource modules
that can be allocated communication session $s$ per time-slot. Hence when
$\bm{q}(t_{i})$ is non-zero, at least one demand and up to $R$ demands are
served per time-slot. Therefore, from any $\bm{q}(t_{i})\in\mathcal{S}$,
$\bm{q}(t_{i+l})=\bm{0}$ is reachable from $\bm{q}(t_{i})$ in
$l\in\\{\lceil\frac{|\bm{q}(t_{i})}{R}\rceil,\lceil\frac{|\bm{q}(t_{i})}{R}\rceil+1,\cdots,\
|\bm{q}(t_{i})|\\}$ time steps, where $|\bm{q}(t_{i})|:=\underset{s}{\Sigma}\
|q_{s}(t_{i})|$. Since any other $\bm{q}(t_{j})\in\mathcal{S}$ is then
reachable from $\bm{0}$, it follows that $\bm{q}(t_{i})$ is irreducible. To
prove that $\bm{\lambda}$ is supportable, it suffices to demonstrate that
$\bm{q}(t_{i})$ is positive recurrent.

Define the Lyapunov function

$\displaystyle
L\big{(}\bm{q}(t_{i})\big{)}=\frac{1}{2}\sum_{s}q^{2}_{s}(t_{i}).$ (40)

To apply the the Foster-Lyapunov theorem (V.1), the key quantity is the drift
of $L\big{(}\bm{q}(t_{i})\big{)}$. Using the queue update dynamics (6), the
drift can be expanded as

$\displaystyle L\big{(}$
$\displaystyle\bm{q}(t_{i+1})\big{)}-L\big{(}\bm{q}(t_{i})\big{)}$
$\displaystyle=\frac{1}{2}\sum_{s}\Big{(}\big{[}q_{s}(t_{i})+a_{s}(t_{i})-g_{s}(t_{i})\big{]}^{+}\Big{)}^{2}-\frac{1}{2}\sum_{s}q^{2}_{s}(t_{i})$
$\displaystyle\leq\frac{1}{2}\sum_{s}\big{(}q_{s}(t_{i})+a_{s}(t_{i})-g_{s}(t_{i})\big{)}^{2}-\frac{1}{2}\sum_{s}q^{2}_{s}(t_{i})$
$\displaystyle=\frac{1}{2}\sum_{s}\big{(}a_{s}(t_{i})-g_{s}(t)\big{)}^{2}$
$\displaystyle\phantom{x}+\sum_{s}q_{s}(t_{i})\big{(}a_{s}(t_{i})-g_{s}(t_{i})\big{)}.$
(41)

Taking the conditional expectation of the Lyapunov drift with respect to the
randomness of arrivals and the probabilistic success of scheduled demands,

$\displaystyle\mathbb{E}\big{[}$ $\displaystyle
L\big{(}\bm{q}(t_{i+1})\big{)}-L\big{(}\bm{q}(t_{i})\big{)}\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}$
$\displaystyle\leq\frac{1}{2}\sum_{s}\mathbb{E}\big{[}\big{(}a_{s}(t_{i})-g_{s}(t_{i})\big{)}^{2}|\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}$
$\displaystyle+\sum_{s}\mathbb{E}\big{[}q_{s}(t_{i})\big{(}a_{s}(t_{i})-g_{s}(t_{i})\big{)}\
|\ \bm{q}(t_{i})=\tilde{\bm{q}}\big{]},$ (42)

where $\tilde{\bm{q}}\in\mathcal{S}$ is a particular queue vector.

Using $\big{(}a_{s}-g_{s}\big{)}^{2}\leq a^{2}_{s}+{g_{s}}^{2}$ and the
linearity of expectation, the first term of the conditional expectation can be
re-written,

$\displaystyle\mathbb{E}\big{[}$
$\displaystyle\sum_{s}\big{(}a_{s}(t_{i})-g_{s}(t_{i})\big{)}^{2}\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}\leq$
$\displaystyle\sum_{s}\mathbb{E}\big{[}a^{2}_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}+\sum_{s}\mathbb{E}\big{[}{g_{s}}^{2}(t_{i})\
|\ \bm{q}(t_{i})=\tilde{\bm{q}}\big{]}$ (43)

Recall that $g_{s}(t_{i})\leq M_{s}(t_{i})\leq x_{s}\ \forall\ s,\ \forall\
t_{i}$. Hence,

$\displaystyle\underset{s}{\sum}\mathbb{E}\big{[}{g_{s}}^{2}(t)\ |\
\bm{q}(t)=\tilde{\bm{q}}\big{]}\leq\sum_{s}x_{s}^{2}.$ (44)

Define the variance in the arrivals to the queue of session $s$,
$\sigma^{2}_{s}:=\text{Var}[a_{s}(t_{i})]$. Then, noting that the arrivals are
independent of the state of the queues, using the definition of variance and
$\mathbb{E}[a_{s}(t_{i})]=\lambda_{s}$,

$\displaystyle\mathbb{E}[a^{2}_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}]=\mathbb{E}[a^{2}_{s}(t_{i})]=\sigma^{2}_{s}+\lambda^{2}_{s}$
(45)

Together (44) and (45) bound the first term of (V-A2),

$\displaystyle\frac{1}{2}\sum_{s}$
$\displaystyle\mathbb{E}\big{[}\big{(}a_{s}(t_{i})-g_{s}(t_{i})\big{)}^{2}|\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}$ $\displaystyle\leq\frac{1}{2}\sum_{s}\
\big{(}\sigma^{2}_{s}+\lambda^{2}_{s}+x_{s}^{2}\big{)}=:B$

Then (V-A2) is,

$\displaystyle\mathbb{E}\big{[}$ $\displaystyle
L\big{(}\bm{q}(t_{i+1})\big{)}-L\big{(}\bm{q}(t_{i})\big{)}\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}$ $\displaystyle\leq B+\ \sum_{s}\
\mathbb{E}\big{[}q_{s}(t_{i})\big{(}a_{s}(t_{i})-g_{s}(t_{i})\big{)}\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}$ $\displaystyle=B+\ \sum_{s}\
\tilde{q}_{s}\big{(}\lambda_{s}-\mathbb{E}\big{[}g_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}\big{)}.$ (46)

Recall that the conditional expectation of the Lyapunov drift is taken with
respect to the randomness of the arrival processes as well as the success of
scheduled demands. The schedule selected for a given time-slot depends on the
queues, but the success of any scheduled demand does not. The conditional
expectation of pair production for communication session $s$ can be re-written
as,

$\displaystyle\mathbb{E}[g_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}]=p_{\text{gen}}\cdot\mathbb{E}[M_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}].$ (47)

Recall that $\bm{M}$ denotes the schedule decided under the maximum weight
scheduling policy, II.6. Allow $\tilde{\bm{M}}$ to denote a schedule that is
decided by any other scheduling policy. It follows from Definition II.6 that,

$\displaystyle\underset{s}{\sum}\ \tilde{q}_{s}\cdot\mathbb{E}[M_{s}(t_{i})\
|\ \bm{q}(t_{i})=\tilde{\bm{q}}]\geq\sum_{s}\
\tilde{q}_{s}\cdot\mathbb{E}[\tilde{M}_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}].$ (48)

Consider a scheduling policy $\tilde{\bm{M}}$ which schedules each session at
a rate of $\frac{\lambda_{s}+\epsilon}{p_{\text{gen}}}$ (this is possible
since, by assumption, $(1+\epsilon)\bm{\lambda}\in\mathcal{C}$). Such a
scheduling policy is aware of the demand arrival rates to each queue but is
not demand based (i.e. it does not use queue information in deciding the
schedule). Hence,

$\displaystyle\sum_{s}\ \tilde{q}_{s}\cdot\mathbb{E}[\tilde{M}_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}]$ $\displaystyle=\sum_{s}\
\tilde{q}_{s}\cdot\mathbb{E}[\tilde{M}_{s}(t_{i})]$ $\displaystyle=\sum_{s}\
\tilde{q}_{s}\bigg{(}\frac{\lambda_{s}+\epsilon}{p_{\text{gen}}}\bigg{)}.$
(49)

Combining (47), (48) and (V-A2), the conditional expectation of the Lyapunov
drift is bounded by,

$\displaystyle\mathbb{E}\big{[}$ $\displaystyle
L\big{(}\bm{q}(t_{i+1})\big{)}-L\big{(}\bm{q}(t_{i})\big{)}\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}$ $\displaystyle\leq B+\ \sum_{s}\
\tilde{q}_{s}\lambda_{s}-\sum_{s}\ \tilde{q}_{s}\cdot
p_{\text{gen}}\cdot\mathbb{E}\big{[}M_{s}(t_{i})\ |\
\bm{q}(t_{i})=\tilde{\bm{q}}\big{]}\big{)}$ $\displaystyle\leq B+\sum_{s}\
\tilde{q}_{s}\lambda_{s}-p_{\text{gen}}\cdot\sum_{s}\
\tilde{q}_{s}\cdot\mathbb{E}[\tilde{M}_{s}(t_{i})]$
$\displaystyle=B-\epsilon\cdot\sum_{s}\ \tilde{q}_{s}.$ (50)

Application of the Foster-Lyapunov theorem completes the proof.

∎

####  V-A3 Proof of Theorem III.1

The proof of this theorem is closely inspired by the proof of an analogous
theorem in [26]. To begin, we establish basic properties of the Dual function
which follow from assumption A1.

######  Lemma V.1.

Under assumption A1 the dual objective function $D(\bm{p})$ (24) is convex,
lower bounded, and continuously differentiable.

For each session $s\in S$, and price vector $\bm{p}\geq 0$, define the
quantity $\beta_{s}(\bm{p}):\mathbb{R}^{1+N}\mapsto\mathbb{R}^{+}$ as follows,

$\displaystyle\beta_{s}(\bm{p}):=\begin{cases}\frac{1}{-f_{s}^{{}^{\prime\prime}}\big{(}\lambda^{*}_{s}(\bm{p})\big{)}},\text{
if }f^{\prime}_{s}(\lambda^{\max}_{\text{gen},s})\leq p_{s}\leq
f^{\prime}_{s}(\lambda^{\min}_{s})\\\ 0,\text{ otherwise,}\end{cases}$ (51)

where $p_{s}:=p_{c}+\underset{u\in s}{\sum}p_{u}$ and
$\lambda^{*}_{s}(\bm{p})$ is the unique maximizer of (24).

For any price vector $\bm{p}\geq\bm{0}$ define the matrix
$B(\bm{p})=diag\big{(}\beta_{s}(\bm{p}),\ s\in S\big{)}$ to be the
$|S|\times|S|$ matrix with diagonal elements $\beta_{s}(\bm{p})$. Note that
from assumption A2, for all $\bm{p}\geq\bm{0}$,

$\displaystyle 0\leq\beta_{s}(\bm{p})\leq\alpha_{s}<\infty.$ (52)

Define the user-session mapping matrix $R$ to be the $N\times|S|$ matrix whose
$(u,\ s)$-th entry is given by,

$\displaystyle R_{u}^{\ s}=\begin{cases}1,\text{ if }u\in s\text{ or
equivalently }s\in S(u)\\\ 0,\text{ otherwise.}\end{cases}$ (53)

The augmented session mapping matrix $\tilde{R}$ is the
$\big{(}1+N\big{)}\times|S|$ matrix whose $(r,\ s)$-th entry is,

$\displaystyle\tilde{R}_{r}^{\ s}=\begin{cases}1,\text{ if }r=1\\\ R_{r-1}^{\
\ s},\ r\neq 1.\end{cases}$ (54)

######  Lemma V.2.

Under assumption A1, where it exists, the Hessian of the dual function $D$ is
given by

$\displaystyle\gradient^{2}D(\bm{p})=\tilde{R}B(\bm{p})\tilde{R}^{\text{T}}.$
(55)

###### Proof.

Let $\gradient_{p}\lambda^{*}$ denote the $|S|\times(1+N)$ Jacobian matrix
whose $(s,\ r)$-th element is $\big{(}\partial\lambda^{*}_{s}/\partial
p_{r}\big{)}(\bm{p}),\ r\in(c,\ u\ \forall u)$. As a consequence of the
Inverse function theorem [27] and (22), when it exists,

$\displaystyle\frac{\partial\lambda^{*}_{s}}{\partial
p_{r}}=\begin{cases}\frac{\tilde{R}_{r}^{\
s}}{f^{{}^{\prime\prime}}_{s}\big{(}\lambda^{*}_{s}(\bm{p})\big{)}},\text{ if
}f^{{}^{\prime}}_{s}(\lambda^{\max}_{\text{gen},s})<p_{s}<f^{{}^{\prime}}_{s}(\lambda^{\min}_{s});\\\
0,\text{ otherwise; }\end{cases}$ (56)

where $r\in(c,\ u\ \forall u).$ Using (51) we can write,

$\displaystyle\gradient_{p}\lambda^{*}=-B(\bm{p})\tilde{R}^{\text{T}}.$ (57)

From (26) and (27), $\gradient D(\bm{p})=c-\tilde{R}\lambda$, where
$c:=(\lambda_{\text{EGS}},\ \overline{\lambda}_{u}\ \forall u)$, therefore,

$\displaystyle\gradient^{2}D(\bm{p})=-\tilde{R}\gradient_{p}\bm{\lambda}=\tilde{R}B(\bm{p})\tilde{R}^{\text{T}}.$

∎

######  Lemma V.3.

Under assumptions A1 and A2, the gradient of the dual function $\gradient
D(\bm{p})$ (24, 26, 27) is Lipschitz continuous with Lipschitz constant
$L=\underset{s\in S}{\max}\ \beta_{s}(p)\cdot\ |S|$.

We use the following theorem to prove Lemma V.3,

######  Theorem V.2 (Rudin, 9.19 [27]).

Suppose $\mathbf{f}$ maps a convex open set $E\subset\mathbb{R}^{n}$ into
$\mathbb{R}^{m}$, $\mathbf{f}$ is differentiable in $E$, and there is a real
number $M$ such that

$\displaystyle||\mathbf{f}^{\prime}(\mathbf{x})||\leq M,$

for every $\mathbf{x}\in E$. Then,

$\displaystyle|\mathbf{f}(\mathbf{b})-\mathbf{f}(\mathbf{a})|\leq
M|\mathbf{b}-\mathbf{a}|,$

for all $\mathbf{a}\in E,\ \mathbf{b}\in E$.

###### Proof of Lemma V.3.

From Lemma V.2, the Hessian of the dual function is the
$\big{(}1+N\big{)}\times\big{(}1+N\big{)}$ matrix
$\gradient^{2}D(p)=\tilde{R}B(p)\tilde{R}^{\text{T}}$. It is simple to
explicitly determine the $(r,r^{\prime})$-th entry of $\gradient^{2}D(p)$. By
matrix multiplication, $B(p)\tilde{R}^{\text{T}}$ is the
$|S|\times\big{(}1+N\big{)}$ matrix whose $(s,r)$-th entry is,

$\displaystyle\big{(}B(p)\tilde{R}^{\text{T}}\big{)}_{s}^{\
r}=\begin{cases}\beta_{s}(p),\text{ if }r=1\text{ or }\big{(}r>1\text{ and
}s\in S(r-1)\big{)}\\\ 0,\text{ otherwise}.\end{cases}$ (58)

By matrix multiplication we calculate the $(r,\ r^{\prime})$-th entry of
$\gradient^{2}D(p)$ as,

$\displaystyle\big{(}\gradient^{2}D(p)\big{)}_{r}^{\ r^{\prime}}$
$\displaystyle=\sum_{s}R_{r}^{\ s}\big{(}B(p)R^{\text{T}}\big{)}_{s}^{\
r^{\prime}}$ $\displaystyle=\begin{cases}\sum_{s}\ \beta_{s},\
r=r^{\prime}=1\\\ \underset{s\in S(r^{\prime}-1)}{\sum}\beta_{s},\ r=1\text{
and }r^{\prime}>1\\\ \underset{s\in S(r-1)}{\sum}\beta_{s},\ r>1\text{ and
}r^{\prime}=1\\\ \underset{s\in S(r-1)\cap S(r^{\prime}-1)}{\sum}\beta_{s},\
r>1\text{ and }r^{\prime}>1\end{cases}$ (59)

Using the definition of the operator norm ([27], Definition 9.6 (c)) we bound
the norm of the Hessian of the dual function,

$\displaystyle||\gradient^{2}D(p)||\leq\underset{s\in S}{\max}\
\beta_{s}\cdot\ |S|.$ (60)

The result of the lemma then follows by application of Theorem V.2. Proof of
Theorem III.1 is assured by the following Theorem, which follows from the
Descent Lemma of Convex Optimization Theory [28],

######  Theorem V.3 ([28]).

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ be a continuously differentiable
function and let $X$ be a closed convex set. Assume $\gradient f$ satisfies
the Lipschitz condition with Lipschitz constant $L$ and consider the gradient
projection iteration,

$x_{k+1}=P_{x}\big{(}x_{k}-\gamma\gradient f(x_{k})\big{)},$

with a constant step-size $\gamma$ in the range $\big{(}0,\
\frac{2}{L}\big{)}$. Then every limit point $\overline{x}$ of the generated
sequence $\\{x_{k}\\}$ satisfies the optimality condition:

$\gradient f(\overline{x})^{\text{T}}(x-\overline{x})\geq 0,\ \forall\ x\in
X.$

∎

## References

  * [1] S. Wehner, D. Elkouss, and R. Hanson.  Quantum internet: A vision for the road ahead.  Science, 362(6412), 2018.
  * [2] B. H. Charles and G. Brassard.  Quantum cryptography: Public key distribution and coin tossing.  Theoretical Computer Science, 560:7–11, December 2014.
  * [3] A. K. Ekert.  Quantum cryptography based on bell’s theorem.  Phys. Rev. Lett., 67:661–663, August 1991.
  * [4] P. Arright and L. Salvail.  Blind quantum computation.  International Journal of Quantum Information, 04(05):883–898, 2006\.
  * [5] A. Broadbent, J. Fitzsimons, and E. Kashefi.  Universal blind quantum computation.  In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 517–526, Atlanta, Georgia, USA, October 2009. IEEE.
  * [6] P. Kómár, E. M. Kessler, M. Bishof, L. Jiang, A. S. Sørensen, J. Ye, and M. D. Lukin.  A quantum network of clocks.  Nature Physics, 10(8):582–587, June 2014.
  * [7] C. Cabrillo, J. I. Cirac, P. García-Fernández, and P. Zoller.  Creation of entangled states of distant atoms by interference.  Phys. Rev. A, 59:1025–1033, February 1999.
  * [8] L.-M. Duan, M. D. Lukin, J. I. Cirac, and P. Zoller.  Long-distance quantum communication with atomic ensembles and linear optics.  Nature, 414(6862):413–418, November 2001.
  * [9] H. Bernien, B. Hensen, W. Pfaff, G. Koolstra, M. S. Blok, L. Robledo, T. H. Taminiau, M. Markham, D. J. Twitchen, L. Childress, and R. Hanson.  Heralded entanglement between solid-state qubits separated by three metres.  Nature, 497(7447):86–90, April 2013.
  * [10] P. C. Humphreys, N. Kalb, J. P. J. Morits, R. N. Schouten, R. F. L. Vermeulen, D. J. Twitchen, M. Markham, and R. Hanson.  Deterministic delivery of remote entanglement on a quantum network.  Nature, 558(7709):268–273, June 2018.
  * [11] P. Maunz, D. L. Moehring, S. Olmschenk, K. C. Younge, D. N. Matsukevich, and C. Monroe.  Quantum interference of photon pairs from two remote trapped atomic ions.  Nature Physics, 3(8):538–541, 2007.
  * [12] V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. A. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Canteri, M. Teller, J. Schupp, J. Bate, M. Meraner, N. Sangouard, B. P. Lanyon, and T. E. Northup.  Entanglement of trapped-ion qubits separated by 230 meters.  Phys. Rev. Lett., 130:050803, February 2023.
  * [13] C. W. Chou, H. de Riedmatten, D. Felinto, S. V. Polyakov, S. J. van Enk, and H. J. Kimble.  Measurement-induced entanglement for excitation stored in remote atomic ensembles.  Nature, 438(7069):828–832, December 2005.
  * [14] C. W. Chou, J. Laurat, H. Deng, K. S. Choi, H. de Riedmatten, D. Felinto, and H. J. Kimble.  Functional quantum nodes for entanglement distribution over scalable quantum networks.  Science, 316(5829):1316–1320, June 2007.
  * [15] T. van Leent, M. Bock, F. Fertig, R. Garthoff, S. Eppelt, Y. Zhou, P. Malik, M. Seubert, T. Bauer, W. Rosenfeld, W. Zhang, C. Becher, and H. Weinfurter.  Entangling single atoms over 33 km telecom fibre.  Nature, 607(7917):69–73, July 2022.
  * [16] G. Vardoyan, S. Guha, P. Nain, and D. Towsley.  On the stochastic analysis of a quantum entanglement distribution switch.  IEEE Transactions on Quantum Engineering, 2:1–16, 2021.
  * [17] G. Avis, F. Rozpędek, and S. Wehner.  Analysis of multipartite entanglement distribution using a central quantum-network node, 2022.
  * [18] L. Tassiulas and A. Ephremides.  Stability properties of constrained queuing systems and scheduling policies for maximum throughput in multihop radio networks.  IEEE Transactions on Automatic Control, 37(12):1936–1948, December 1992.
  * [19] N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand.  Achieving 100% throughput in an input-queued switch.  IEEE Transactions on Communications, 47(8):1260–1267, August 1999\.
  * [20] T. Vasantam and D. Towsley.  A throughput optimal scheduling policy for a quantum switch.  In P. R. Hemmer and A. L. Migdall, editors, Quantum Computing, Communication, and Simulation II, page 1201505, San Fransisco, California, USA, mar 2022. SPIE.
  * [21] R. Yehia, S. Neves, E. Diamanti, and I. Kerenidis.  Quantum city: simulation of a practical near-term metropolitan quantum network, 2022.
  * [22] F.P. Kelly, A.K. Maulloo, and D. Tan.  Rate control for communication networks: Shadow prices, proportional fairness and stability.  Journal of the Operational Research Society, 49, February 1998.
  * [23] R. Srikant and Lei Ying.  Communication Networks: An Optimization, Control, and Stochastic Nerworks Perspective.  Cambridge University Press, Cambridge, UK, 2014.
  * [24] G. Vardoyan and S. Wehner.  Quantum network utility maximization, 2022.
  * [25] D. P. Bertsekas.  Nonlinear Programming, Second Edition.  Athena Scientific, Belmont, Massachusetts, USA, 1999.
  * [26] S.H. Low and D.E. Lapsley.  Optimization flow control. i. basic algorithm and convergence.  IEEE/ACM Transactions on Networking, 7(6):861–874, 1999.
  * [27] W. Rudin.  Principles of Mathematical Analysis, Third Edition.  McGraw-Hill Inc., New York, USA, 1976.
  * [28] D. P. Bertsekas.  Convex Optimization Algorithms.  Athena Scientific, Belmont, Massachusetts, USA, 2015.