# Policies for elementary link generation in quantum networks

Sumeet Khatri  Hearne Institute for Theoretical Physics, Department of Physics
and Astronomy, and Center for Computation and Technology, Louisiana State
University, Baton Rouge, Louisiana, 70803, USA

###### Abstract

Protocols in a quantum network involve multiple parties performing actions on
their quantum systems in a carefully orchestrated manner over time in order to
accomplish a given task. This sequence of actions over time is often referred
to as a strategy, or policy. In this work, we consider policy optimization in
a quantum network. Specifically, as a first step towards developing full-
fledged quantum network protocols, we consider policies for generating
elementary links in a quantum network. We start by casting elementary link
generation as a quantum partially observable Markov decision process, as
defined in [Phys. Rev. A 90, 032311 (2014)]. Then, we analyze in detail the
commonly used memory cutoff policy. Under this policy, once an elementary link
is established it is kept in quantum memory for some amount $t^{\star}$ of
time, called the cutoff, before it is discarded and the elementary link
generation is reattempted. For this policy, we determine the average quantum
state of the elementary link as a function of time for an arbitrary number of
nodes in the link, as well as the average fidelity of the link as a function
of time for any noise model for the quantum memories. Finally, we show how
optimal policies can be obtained in the finite-horizon setting using dynamic
programming. By casting elementary link generation as a quantum decision
process, this work goes beyond the analytical results derived here by
providing the theoretical framework for performing reinforcement learning of
practical quantum network protocols.

###### Table of Contents

  1. 1 Introduction
    1. 1.1 Summary of results
    2. 1.2 Relation to prior work
  2. 2 Elementary link generation
    1. 2.1 Formulation as a quantum decision process
    2. 2.2 Link quantities
  3. 3 The memory cutoff policy for elementary link generation
    1. 3.1 Calculation of link quantities
    2. 3.2 Waiting time
    3. 3.3 Multiple parallel links
    4. 3.4 Total number of active links
    5. 3.5 Collective link status
  4. 4 Finite-horizon policy optimization
  5. 5 Summary and outlook

##  1 Introduction

A quantum network is a collection of nodes, each equipped with quantum
information processing capabilities, that are connected to each other by
quantum channels. The nodes in such a network can, in principle, perform tasks
such as quantum teleportation [1, 2], quantum key distribution [3, 4, 5, 6],
quantum clock synchronization [7, 8, 9], distributed quantum computation [10],
and distributed quantum metrology and sensing [11, 12, 13, 14, 15, 16]. The
future quantum internet [17, 18, 19, 20, 21] will be an interconnected network
of such quantum networks, much like today’s internet, that will enable these
applications to be performed on a global scale.

Figure 1: Representation of a quantum network as a hypergraph. The nodes
represent the senders, receivers, or repeaters depending on the situation.
Edges represent entangled states shared by the corresponding nodes. Edges
between two nodes (shown in red) represent bipartite entanglement, while
hyperedges (consisting of more than two nodes and indicated by a blue bubble)
represent multipartite entanglement. Nodes can be connected by multiple edges,
indicating that they can share multiple entangled states simultaneously.

As shown in Figure 1, a quantum network can be modeled as a graph. The nodes
of the graph represent the senders/receivers in the network, and the edges
represent elementary links, which in this work we take to be an entangled
state shared by the corresponding nodes. The edges can be between two nodes
only, as indicated by the red lines, or they can be hyperedges connecting
three or more nodes, as indicated by the blue bubbles. Groups of nodes can be
connected by more than one edge, and in this case the graph is called a
multigraph. Multiple edges between nodes are shown explicitly in Figure 1 for
two-node edges, although we can also have multiple hyperedges between a set of
adjacent nodes. Each of these edges is regarded as a distinct edge in the
graph.

In general, the goal in a quantum network is to transmit quantum information
between a collection of distant nodes, i.e., nodes that are not connected to
each other by a single elementary link. In this setting, any node in the
network that is not either a sender or a receiver can function as a so-called
quantum repeater. A quantum repeater can be thought of as a helper node whose
task is to mitigate the effects of loss and noise along a path connecting a
sender and a receiver, thereby making the quantum information transmission
more reliable. Quantum repeaters are needed because directly transmitting
quantum information from a sender to a receiver is often too lossy and noisy
to be useful for the applications mentioned above. In fact, the loss in an
optical fiber, a commonly used medium for quantum information transmission,
increases exponentially with distance [22, 23], limiting direct transmission
distances to roughly hundreds of kilometers. The original quantum repeater
proposal in [24, 25] consists of placing quantum repeaters at intermediate
points along a straight line connecting the sender and receiver. The protocol
to generate sender-receiver entanglement then consists of first generating
bipartite entanglement along the elementary links between the repeaters. The
repeaters then perform entanglement distillation [26, 27, 28] and entanglement
swapping [1, 29] to iteratively extend the entanglement range to the desired
distance.

A vast body of literature exists on a variety of quantum repeater schemes [24,
25, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59]. (See also [60, 61, 62] and
the references therein.) Considering a quantum network such as the one in
Figure 1, as opposed to just one line between a sender and a receiver, is a
much more complicated setting that leads to questions about, e.g., routing
[63, 64, 65, 66, 67, 68, 69, 70, 71, 72] and multicast communication
(communication between several senders and receivers simultaneously).
Consequently, protocols in a general quantum network can be much more varied
than protocols along a linear chain of nodes. General quantum network
protocols have been described in [73, 74, 75, 76, 69, 70, 77]. Linear
programs, and other techniques for obtaining optimal entanglement distribution
rates in a quantum network, have been explored in [78, 79, 80, 81, 77].

Figure 2: Elementary link generation in a quantum network as a quantum
partially observable Markov decision process (see Section 2.1 and Definition
2.1 for details). As shown in the case of a bipartite link, the agent consists
of the nodes belonging to the elementary link, and the environment is the
quantum systems distributed to the nodes from the entanglement source.

In this work, we view entanglement distribution protocols in quantum networks
from the lens of decision processes [82], which form the theoretical
foundation for reinforcement learning [83] and artificial intelligence [84].
In a decision process, an agent interacts with its environment through a
sequence of actions, and it receives rewards from the environment based on
these actions. The goal of the agent is to perform actions that maximize its
expected total reward. We consider a particular quantum generalization of a
decision process given in [85] (see also [86]), called a quantum partially
observable Markov decision process, in which the agent is classical and the
environment is quantum. The agent’s action at each time step results in a
transformation of the quantum state of the environment, and the agent receives
both partial (classical) information about the new quantum state of the
environment along with a reward. Such decision processes have been considered
previously in the context of quantum control [87, 88, 89, 90, 91], quantum-
enhanced parameter estimation [92, 93, 94, 95, 96], and quantum error
correction [89, 97, 98]. We now apply this concept to quantum networks.
Specifically, we consider elementary link generation, which is the first step
towards obtaining long-range entanglement distribution in quantum networks,
and we show that elementary link generation can be cast as a quantum partially
observable Markov decision process; see Figure 2. The advantage of viewing
elementary link generation from the point of view of decision processes is
that we are able to systematically study different policies and determine
which policy is optimal in terms of both the fidelity of the link and the
probability that the link is active at any given time. We can also keep track
of the quantum state of the link over time, which is useful calculating
entanglement measures and determining rates for entanglement distillation.
Furthermore, because decision processes form the theoretical foundation for
reinforcement learning, our work provides the tools needed in order to perform
reinforcement learning in quantum networks.

###  1.1 Summary of results

The following is a summary of the main results of this work.

  1. 1.

Our first result, in Section 2.1, is conceptual in nature and is captured by
Figure 2 and detailed in Definition 2.1. In Definition 2.1, we formally cast
elementary link generation as a quantum partially observable Markov decision
process (of the type considered in [85]) by establishing in the context of
elementary link generation all of the elements that define a quantum partially
observable Markov decision process. In this framework, at each time step, the
agent (which is all of the nodes in the elementary link as a collective
entity) either requests entanglement from a source station (which is the
environment), or keeps the entangled state currently stored in memory. The
agent’s choice of action can depend on, e.g., the quality of the initial
entanglement and coherence times of the quantum memories. We formally define a
policy for elementary link generation, and we describe mathematically how the
quantum state of the environment (i.e., the entangled state of the elementary
link) transforms based on the actions taken by the agent. In Section 2.2, we
define various quantities of interest relating to an elementary link.

  2. 2.

With elementary link generation cast within the framework of a decision
process, we proceed to provide a closed-form expression for the average
quantum state of any elementary link in a network at any time (Theorem 2.1 and
Corollary 2.1), as well as the fidelity of the link at any time (Theorem 2.2).
These results hold for any policy and for any noise model for the quantum
memories.

  3. 3.

In Section 3, we consider in detail the so-called memory cutoff policy. In
this policy, an elementary link, once established, is kept in quantum memories
at the nodes for some amount $t^{\star}$ of time, called the cutoff, before it
is discarded and the link is reattempted. The memory cutoff policy has been
considered in prior work [31, 32, 33, 34, 99, 100, 101, 102, 103, 104, 105],
and it is a natural policy to consider for near-term protocols, in which
quantum memories have relatively short coherence times, and there is limited
capability to perform entanglement distillation. For this policy, given any
number of nodes in the elementary link and any noise model for the quantum
memories, our main results are expressions for the link activity probability
in the finite- and infinite-horizon settings111By definition, the finite-
horizon setting corresponds to a given, finite interaction time between the
agent and the environment. In the infinite-horizon setting, the interaction
proceeds indefinitely. (Proposition 3.2 and Theorem 3.2, respectively), which
immediately lead to expressions for the average quantum state of the link as a
function of time and for the average fidelity of the link as a function of
time, again in both the finite- and infinite-horizon settings. We also derive
in Section 3.1 formulas for the other elementary link quantities defined in
Section 2.2, and in Section 3.2 we derive formulas for the expected waiting
time for an elementary link.

  4. 4.

In Section 4, we show how to obtain an optimal policy using the techniques of
dynamic programming in the finite-horizon setting, i.e., in the case that the
termination time of the elementary link generation procedure is fixed at the
outset and is finite. The main result of this section is Theorem 4.1, in which
we prove that the optimal policy can be obtained using a backward recursion
procedure such that the optimal action at each time is deterministic.

We expect the results derived in this work to be useful as a building block
for large-scale quantum network protocols. For example, the policies for
elementary link generation obtained through the results of this work can be
used as an underlying policy layer over which routing policies can be applied
in order to obtain an overall policy for generating end-to-end entanglement in
a network. We elaborate on this and on further avenues for development of the
mathematical tools established in this work in Section 5. Furthermore, because
our results apply to elementary links consisting of an arbitrary number of
nodes and to any noise model for the quantum memories, they can be applied to
protocols that go beyond bipartite entanglement distribution, namely to
protocols for distributing multipartite entanglement [106, 107, 108, 39, 38,
44, 67, 47, 42]. We also expect our results to be useful in the analysis of
entanglement distribution using all-photonic quantum repeaters [36] and in the
analysis of entanglement distribution using satellite-based quantum networks
[109, 110, 111, 112, 113], in which an elementary link can easily be on the
order of 1000 km [114] while still having a high fidelity. Finally, since
decision processes are at the heart of reinforcement learning, the results of
this work provide the theoretical foundation for performing reinforcement
learning of (near-optimal) quantum network protocols that can be used in
practice.

###  1.2 Relation to prior work

Policy-based approaches to quantum network protocols have been considered
before in [115, 116, 99, 117] (see also [62]), where terms such as “rule-set”
or “schedule” have been used instead of “policy”. In [99], the authors
consider different control protocols for elementary link generation in a
quantum network based on different configurations of the sources and heralding
stations and the impact they have on end-to-end entanglement distribution
rates. In [115], the authors look at protocols for end-to-end entanglement
distribution along a chain of quantum repeaters and simulate different
scheduling protocols for entanglement distillation along elementary links.
Similarly, in [116], the authors use finite state machines to analyze the
different layers of an end-to-end entanglement distribution protocol in
quantum networks, such as entanglement distillation and entanglement swapping.
Finally, in [117], the authors use an approach based on rule-sets to determine
end-to-end entanglement distribution rates and fidelities of the end-to-end
pairs along a chain of quantum repeaters.

One of the goals of this work is to explicitly formalize the approaches taken
in the aforementioned works within the context of decision processes, because
this allows us to systematically study different policies and calculate
quantities that are relevant for quantum networks, such as entanglement
distribution rates and fidelities of the quantum states of the links.

This work is complementary to other prior work on using Markov chains to
analyze waiting times and entanglement distribution rates for a chain of
quantum repeaters [118, 119, 120, 102], and to prior work on analyzing the
quantum state in a quantum repeater chain with noisy quantum memories [121,
122, 123, 124, 125]. It is also complementary to [126], in which the authors
use reinforcement learning to discover protocols for quantum teleportation,
entanglement distillation, and end-to-end bipartite entanglement distribution
along a chain of quantum repeaters. While the work in [126] is largely
numerical, our work is focused on formally developing the mathematical tools
needed to perform reinforcement learning of protocols in general quantum
networks. The development of the mathematical tools is essential when an agent
acts in a quantum-mechanical environment, because it is important to
understand how the agent’s actions affect the quantum state of the
environment. Furthermore, we expect that the protocols learned in [126],
particularly those for entanglement distillation and entanglement swapping,
could be incorporated as subroutines within the mathematical framework of
decision processes developed in this work, so that large-scale quantum network
protocols (going beyond the elementary link level) can be discovered using
reinforcement learning.

This work is also related to the work in [127], in which the authors develop a
link-layer protocol for generating elementary links in a quantum network, and
they perform simulations of entanglement distribution using a discrete-event
simulator under various scenarios. The effect of different scheduling
strategies is also considered. The protocols in [127] consider actions in a
more fine-grained manner than what we consider in this work. In particular,
the steps required for heralding (namely, the communication signals for the
results of the heralding) are explicitly taken into account. In Remark 2.3, we
briefly explain how the approach of [127] can be viewed in terms of the
framework being considered here.

The approach to policy optimization taken in this work is similar to the
approach in [128], in the sense that both approaches make use of the principle
of dynamic programming. While in [128] the focus is on obtaining end-to-end
bipartite entanglement in a chain of quantum repeaters, the goal here is
simply to examine elementary link generation and to determine the optimal
sequence of actions that should be performed in order to maximize both the
fidelity of any given elementary link and the probability that any given
elementary link is active at any given time.

##  2 Elementary link generation

Let us go back to the graphical representation of a quantum network in Figure
1. In this work, we suppose that all of the edges in the graph represent
entangled states shared by the corresponding nodes. These entangled states are
distributed to the nodes by stations containing an entanglement source. These
source stations can be on the ground at fixed locations, they can be at one of
the nodes in the edge, or they can be on satellites orbiting the earth [109,
110].

The model for transmission of quantum states from the source stations to the
nodes is as follows. The source prepares a $k$-partite state $\rho^{S}$, where
$k$ is the number of nodes belonging to the edge. Each of the $k$ quantum
systems is encoded into $d$ bosonic modes, with $d\geq 1$. The source state
$\rho^{S}$ is typically of the form $|\psi^{S}\rangle\langle\psi^{S}|$, where

$|\psi^{S}\rangle=\sqrt{\smash[b]{p_{0}^{S}}}|\text{vac}\rangle+\sqrt{\smash[b]{p_{1}^{S}}}|\psi_{1}^{S}\rangle+\sqrt{\smash[b]{p_{2}^{S}}}|\psi_{2}^{S}\rangle+\dotsb,$
(2.1)

where $|\psi_{n}^{S}\rangle$ is a state vector with $n$ photons in total for
each of the $k$ parties and the numbers $p_{n}^{S}\geq 0$ are probabilities,
so that $\sum_{n=0}^{\infty}p_{n}^{S}=1$. For example, in the case $k=2$ and
$d=2$, the following source state is generated from a parametric down-
conversion process (see, e.g., [129, 124]):

$\displaystyle|\psi^{S}\rangle$
$\displaystyle=\sum_{n=0}^{\infty}\frac{\sqrt{n+1}r^{n}}{\text{e}^{q}}|\psi_{n}\rangle,$
(2.2) $\displaystyle|\psi_{n}\rangle$
$\displaystyle=\frac{1}{\sqrt{n+1}}\sum_{m=0}^{n}(-1)^{m}|n-m,m;m,n-m\rangle,$
(2.3)

where $r$ and $q$ are parameters characterizing the process. One often
considers a truncated version of this state as an approximation, so that [124]

$|\psi\rangle=\sqrt{p_{0}}|0,0;0,0\rangle+\sqrt{\frac{p_{1}}{2}}(|1,0;0,1\rangle+|0,1;1,0\rangle)\\\
+\sqrt{\frac{p_{2}}{3}}(|2,0;0,2\rangle+|1,1;1,1\rangle+|0,2;2,0\rangle),$
(2.4)

where $p_{0}+p_{1}+p_{2}=1$. Typically, a source state of the form (2.1) is
not ideal, in the sense that the desired state is given by one of the state
vectors $|\psi_{j}^{S}\rangle$, and the other terms arise due to the naturally
imperfect nature of the source. For example, for the state in (2.4), the
desired bipartite state is the maximally entangled state
$|\Psi^{+}\rangle\equiv\frac{1}{\sqrt{2}}(|1,0;0,1\rangle+|0,1;1,0\rangle)$.

Once the source state is prepared, each mode is sent through a bosonic pure-
loss/attenuation channel $\mathcal{L}_{\eta}$ [130], where $\eta\in(0,1]$ is
the transmissivity of the medium. This channel provides a good model for
transmission of photons through an optical fiber, in which case
$\eta=\text{e}^{-\frac{L}{L_{0}}}$ [22, 23], where $L$ is the transmission
distance and $L_{0}$ is the attenuation length of the fiber. Letting

$\mathcal{L}_{\eta}^{(d)}\coloneqq\underbrace{\mathcal{L}_{\eta}\otimes\mathcal{L}_{\eta}\otimes\dotsb\otimes\mathcal{L}_{\eta}}_{d\text{
times}}$ (2.5)

denote the quantum channel that acts on the $d$ modes of each of the $k$
systems, the overall quantum channel through which the source state $\rho^{S}$
is sent is

$\mathcal{L}_{\vec{\eta}}^{(k;d)}\coloneqq\underbrace{\mathcal{L}_{\eta_{1}}^{(d)}\otimes\mathcal{L}_{\eta_{2}}^{(d)}\otimes\dotsb\otimes\mathcal{L}_{\eta_{k}}^{(d)}}_{k\text{
times}},$ (2.6)

where $\vec{\eta}=(\eta_{1},\eta_{2},\dotsc,\eta_{k})$ and $\eta_{j}$ is the
transmissivity of the medium to the $j^{\text{th}}$ node in the edge. The
quantum state shared by the $k$ nodes after transmission from the source is
then

$\rho_{\text{out}}^{S}\coloneqq\mathcal{L}_{\vec{\eta}}^{(k;d)}(\rho^{S}).$
(2.7)

After transmission from the source to the nodes, the nodes typically have to
execute a heralding procedure, which is a sequence of local operations and
classical communication between the nodes that confirms whether all of the
nodes received their quantum systems and whether they are in the desired
subspace. If the heralding procedure succeeds, then the nodes store their
quantum systems in a quantum memory. Mathematically, the heralding procedure
can be described by a set $\\{\mathcal{M}_{0},\mathcal{M}_{1}\\}$ of
completely positive trace non-increasing maps such that
$\mathcal{M}_{0}+\mathcal{M}_{1}$ is trace preserving. The map
$\mathcal{M}_{0}$ corresponds to failure of the heralding procedure, and the
map $\mathcal{M}_{1}$ corresponds to success. The outcome of the heralding
procedure can then be captured by the following transformation of the state
$\rho_{\text{out}}^{S}$ to a classical-quantum state:

$\rho_{\text{out}}^{S}\mapsto|0\rangle\langle
0|\otimes\mathcal{M}_{0}(\rho_{\text{out}}^{S})+|1\rangle\langle
1|\otimes\mathcal{M}_{1}(\rho_{\text{out}}^{S})=|0\rangle\langle
0|\otimes\widetilde{\tau}^{\varnothing}+|1\rangle\langle
1|\otimes\widetilde{\rho}_{0},$ (2.8)

where the classical register holds the binary outcome of the heralding
procedure (1 for success and 0 for failure) and the quantum register holds the
quantum state of the nodes corresponding to the outcome. In particular,
$\widetilde{\tau}^{\varnothing}\coloneqq\mathcal{M}_{0}(\rho_{\text{out}}^{S})$
is the (unnormalized) quantum state corresponding to failure, and
$\widetilde{\rho}_{0}\coloneqq\mathcal{M}_{1}(\rho_{\text{out}}^{S})$ is the
(unnormalized) quantum state corresponding to success. The subscript “0” in
$\widetilde{\rho}_{0}$ indicates that the quantum memories of the nodes are in
their initial state immediately after success of the heradling procedure; we
expand on this below. The quantum states conditioned on success and failure,
respectively, are defined to be

$\rho_{0}\coloneqq\frac{\widetilde{\rho}_{0}}{\operatorname{Tr}[\widetilde{\rho}_{0}]},\quad\tau^{\varnothing}\coloneqq\frac{\widetilde{\tau}^{\varnothing}}{\operatorname{Tr}[\widetilde{\tau}^{\varnothing}]}.$
(2.9)

Throughout this work, we let

$p\coloneqq\operatorname{Tr}[\widetilde{\rho}_{0}]$ (2.10)

denote the overall probability of success of the transmission from the source
and of the heralding procedure.

Now, as mentioned above, once the heralding procedure succeeds, the nodes
store their quantum systems in their local quantum memory. Quantum memories
have been made using trapped ions [131], Rydberg atoms [132, 133], atom-cavity
systems [134, 135], NV centers in diamond [136, 137, 138, 100, 139, 101],
individual rare-earth ions in crystals [140], and superconducting processors
[141]. The quantum memories are in general imperfect, which means that the
quantum systems decohere over time. We describe this decoherence by a quantum
channel $\mathcal{N}_{j}$ acting on each quantum system
$j\in\\{1,2,\dotsc,k\\}$ of the elementary link. The decoherence channel is
applied at every time step in which the quantum system is in memory. The
overall quantum channel acting on all of the quantum systems in the elementary
link is

$\widehat{\mathcal{N}}\coloneqq\mathcal{N}_{1}\otimes\mathcal{N}_{2}\otimes\dotsb\otimes\mathcal{N}_{k}.$
(2.11)

The quantum state of the elementary link after $m$ time steps in the memories
is therefore given by

$\rho(m)\coloneqq\widehat{\mathcal{N}}^{\circ m}(\rho_{0}).$ (2.12)

For a particular target/desired quantum state of the elementary link, which we
assume to be a pure state $\psi=|\psi\rangle\langle\psi|$, we let

$f_{m}(\rho_{0};\psi)\coloneqq\langle\psi|\rho(m)|\psi\rangle=\langle\psi|\widehat{\mathcal{N}}^{\circ
m}(\rho_{0})|\psi\rangle$ (2.13)

denote the fidelity of the state $\rho(m)$ with respect to the target state
$\psi$. For brevity, we suppress the dependence of $f_{m}$ on the target state
$\psi$ whenever it is understood or is unimportant. We also suppress, for
brevity, the dependence of $f_{m}$ on the decoherence channels of the quantum
memories.

###  2.1 Formulation as a quantum decision process

Let us now describe elementary link generation from the point of view of
decision processes. Specifically, in this section, we cast elementary link
generation as a quantum partially observable Markov decision process, as
defined in [85] (see also [86]), which is a particular quantum generalization
of Markov decision processes. We start by reviewing the general definition of
a classical Markov decision process. Then, we proceed to the general
definition of a quantum partially observable Markov decision process. We then
apply this definition to come up with a quantum partially observable Markov
decision process that is specific to elementary link generation.

Figure 3: Schematic diagrams of classical (left) and quantum partially
observable (right) Markov decision processes. See [82, 142] for details on
classical Markov decision processes. Our definition of quantum partially
observable Markov decision processes is based on the definition given in [85].
See the main text for details on the elements of both types of decision
processes.

A classical Markov decision process, depicted in the left panel of Figure 3,
is a sequence of interactions between an agent and its environment that is
defined by the following elements. (We follow the definition presented in [82,
Chapter 2].)

  * •

A set $\mathcal{X}$ of states of the environment, with associated random
variables $X(t)$ for all $t\geq 1$ whose values are contained in
$\mathcal{X}$. We also have a set $\mathcal{A}$ of actions of the agent, with
associated random variables $A(t)$ for all $t\geq 1$ whose values are
contained in $\mathcal{A}$. The sequence

$H(t)\coloneqq(X(1),A(1),X(2),A(2),\dotsc,A(t-1),X(t))$ (2.14)

of state and action random variables tells us the history of the agent-
environment interaction up to some time $t\geq 1$. Any realization of the
history is a sequence of the form

$h^{t}\coloneqq(x_{1},a_{1},x_{2},a_{2},\dotsc,a_{t-1},x_{t}),$ (2.15)

where $x_{j}\in\mathcal{X}$ and $a_{j}\in\mathcal{A}$. Given any history
$h^{t}$ of the form shown above, we let

$h^{t}_{j}\coloneqq(x_{1},a_{1},x_{2},a_{2},\dotsc,a_{j-1},x_{j})$ (2.16)

denote the history up to time $j\geq 2$. For $j=1$, we let $h^{t}_{1}=x_{1}$.
Then, we can regard the state and action random variables as functions such
that, for any history $h^{t}$ as in (2.15),

$X(j)(h^{t})=x_{j},\quad A(j)(h^{t})=a_{j}$ (2.17)

for all $1\leq j\leq t$.

  * •

A transition function
$T_{t}:\mathcal{X}\times\mathcal{A}\times\mathcal{X}\to[0,1]$ for all $t\geq
1$ such that
$T_{t}(x_{t},a_{t},x_{t+1})=\Pr[X(t+1)=x_{t+1}|X(t)=x_{t},A(t)=a_{t}]$. In
other words, the transition function gives us the probability that, at time
$t$, the environment transitions to a particular state at time $t+1$ given its
state at time $t$ and the agent’s action at time $t$.

  * •

A reward function
$r_{t}:\mathcal{X}\times\mathcal{A}\times\mathcal{X}\to\mathbb{R}$ for $t\geq
2$ such that $r_{t}(x_{t-1},a_{t-1},x_{t})$ is the reward received by the
agent at time $t$ based on the state $x_{t-1}$ of the environment at time
$t-1$, the agent’s action $a_{t-1}$ at time $t-1$, and the new state $x_{t}$
of the environment at time $t$ based on the agent’s action. The reward $r_{1}$
at time $t=1$ is a given fixed value at the start of the decision process.

  * •

A decision function $d_{t}$ for $t\geq 1$ such that

$d_{t}(h^{t})(a_{t})\coloneqq\Pr[A(t)=a_{t}|H(t)=h^{t}].$ (2.18)

In other words, the decision function gives us the probability that, at time
$t$, the agent takes the action $a_{t}$ conditioned on the history $h^{t}$ of
the interaction up to time $t$. The sequence
$\pi\coloneqq(d_{1},d_{2},\dotsc)$ is called a policy for the agent, and it
tells us how action decisions are made at each time step.

At each time step $t\geq 1$, the environment is in some state
$x_{t}\in\mathcal{X}$. The agent receives information about the state of the
environment and selects an action $a_{t}\in\mathcal{A}$. The environment,
based on this action, transitions to a different state $x_{t+1}\in\mathcal{X}$
according to the transition function $T_{t}$ and simultaneously provides the
agent with some reward according to the reward function $r_{t+1}$. The agent
also receives full (or partial) information about the new state of the
environment, which they can then use to select the next action. The agent’s
goal is to perform actions that maximize its long-term reward. Specifically,
in the finite-horizon setting, the agent’s goal is to maximize the expected
value of the quantity $\sum_{t=1}^{T}r_{t}$ up to a given amount $T<\infty$ of
time, called the horizon time. In the infinite-horizon setting, the agent’s
goal is to maximize the expected value of the quantity
$\sum_{t=1}^{\infty}\gamma^{t-1}r_{t}$, where $\gamma\in(0,1]$ is a discount
factor. A thorough introduction to classical Markov decision processes can be
found in [82, 142]. Note that what makes a classical Markov decision process
Markovian is the fact that the transition function and the reward function at
each time depend only on the state and action of the previous time step.
However, the decision function can in general depend on the entire history of
the interaction, even in a Markov decision process.

By the basic rules of probability, the probability of any history $h^{t}$ is
given by

$\displaystyle\Pr[H(t)=h^{t}]$
$\displaystyle=\Pr[X(t)=x_{t}|H(t-1)=h_{t-1}^{t},A(t-1)=a_{t-1}]\cdot$
$\displaystyle\qquad\qquad\Pr[A(t-1)=a_{t-1}|H(t-1)=h_{t-1}^{t}]\cdot\Pr[H(t-1)=h_{t-1}^{t}]$
(2.19)
$\displaystyle=\Pr[X(1)=x_{1}]\prod_{j=2}^{t}\left(\Pr[X(j)=x_{j}|H(j-1)=h_{j-1}^{t},A(j-1)=a_{j-1}]\right.\cdot$
$\displaystyle\qquad\qquad\qquad\qquad\left.\Pr[A(j-1)=a_{j-1}|H(j-1)=h_{j-1}^{t}]\right)$
(2.20)
$\displaystyle=\Pr[X(1)=x_{1}]\prod_{j=2}^{t}\left(T_{j-1}(x_{j-1},a_{j-1},x_{j})\cdot
d_{j-1}(h_{j-1}^{t})(a_{j-1})\right).$ (2.21)

We now state the definition of a quantum partially observable Markov decision
process (which we refer to from now on as a “quantum decision process” for
brevity), as defined in [85]; see the right panel of Figure 3 for a schematic
diagram. Roughly speaking, a quantum decision process is similar to a
classical Markov decision process, with the main differences being that in the
quantum case the environment is a quantum system, and each of the agent’s
actions in the set $\mathcal{A}$ of actions corresponds to a physical
evolution of the quantum system, which is described by a completely positive
trace non-increasing map acting on the quantum state of the environment. At
each time step, the agent only receives classical information about the state
of the quantum system, which we call observations, and they are elements in
the set $\mathcal{X}$, hence making the process “partially observable”. In
detail, we have the following.

  * •

We define an orthonormal basis $\\{|x\rangle\\}_{x\in\mathcal{X}}$ of vectors
corresponding to the set $\mathcal{X}$ of classical observations of the agent,
and an orthonormal basis $\\{|a\rangle\\}_{a\in\mathcal{A}}$ of vectors
corresponding to the set $\mathcal{A}$ of the agent’s actions. For every time
step $t\geq 1$, we define classical registers $X_{t}$ and $A_{t}$ for the
observation and action values, respectively, at time $t$. We denote the
collection of observation and action value classical registers up to time $t$
by $H_{t}\equiv X_{1}A_{1}\dotsb A_{t-1}X_{t}$. Then, based on the definition
of a history in (2.15), we define

$|h^{t}\rangle_{H_{t}}\coloneqq|x_{1}\rangle_{X_{1}}\otimes|a_{1}\rangle_{A_{1}}\otimes|x_{2}\rangle_{X_{2}}\otimes|a_{2}\rangle_{A_{2}}\otimes\dotsb\otimes|a_{t-1}\rangle_{A_{t-1}}\otimes|x_{t}\rangle_{X_{t}}.$
(2.22)

  * •

The transition functions are completely positive trace non-increasing maps
such that, at time $t\geq 1$, $\mathcal{T}^{t;x_{t},a_{t},x_{t+1}}$ gives the
evolution of the quantum state of the environment under the given values
$x_{t}\in\mathcal{X}$, $a_{t}\in\mathcal{A}$, and $x_{t+1}\in\mathcal{X}$ of
the observation, action, and observation at the next time step, respectively.
The transition maps are such that the sum
$\sum_{x_{t+1}\in\mathcal{X}}^{1}\mathcal{T}^{t;x_{t},a_{t},x_{t+1}}$ is a
trace preserving map for all $t\geq 1$, all observations
$x_{t}\in\mathcal{X}$, and all actions $a_{t}\in\mathcal{A}$. At time $t=0$,
before the start of the interaction, we have a set
$\\{\mathcal{T}^{0;x_{1}}\\}_{x_{1}\in\mathcal{X}}$ of completely positive
trace non-increasing maps that give rise to the first observation
$x_{1}\in\mathcal{X}$ of the agent, and they have the property that
$\sum_{x_{1}\in\mathcal{X}}\mathcal{T}^{0;x_{1}}$ is a trace preserving map

  * •

The reward at times $t\geq 2$ is given by a set
$\\{R^{t;x_{t-1},a_{t-1},x_{t}}:x_{t-1},x_{t}\in\mathcal{X},a_{t-1}\in\mathcal{A}\\}$
of Hermitian operators acting on the Hilbert space corresponding to the
quantum system of the environment, such that the value of the reward is the
expectation value of the appropriate Hermitian operator. The reward at time
$t=1$ is given by a set $\\{R^{1;x_{1}}:x_{1}\in\mathcal{X}\\}$ of Hermitian
operators acting on the Hilbert space corresponding to the quantum system of
the environment. See (2.34) and (2.37) below for details on how the reward is
calculated.

  * •

The decision function and policy are defined exactly as in the classical case:
for any history $h^{t}$, with $t\geq 1$, $d_{t}(h^{t}):\mathcal{A}\to[0,1]$ is
a probability distribution over actions, and $\pi=(d_{1},d_{2},\dotsc)$ is a
policy. In addition to this, to each each element of the policy, we define a
density operator as follows:

$\pi(t;h^{t})\coloneqq\sum_{a\in\mathcal{A}}d_{t}(h^{t})(a)|a\rangle\langle
a|,\quad t\geq 1,$ (2.23)

for all histories $h^{t}$.

  * •

An additional defining element is the initial quantum state $\rho_{E_{0}}$ of
the environment, where $E_{0}$ is a label for the quantum system of the
environment before its interaction with the agent. We denote by $E_{t}$ the
quantum system of the environment at times $t\geq 1$ during its interaction
with the agent.

Figure 4: An alternative depiction of the quantum decision process shown in
the right panel of Figure 3. In this diagram, we explicitly illustrate the
interaction of the agent and the environment over time via a sequence of
quantum channels (shown here up to time $t=3$). The decision channels
$\mathcal{D}^{t}$ correspond to the decision functions of the agent (see
(2.24)), and the environment response channels $\mathcal{E}^{t}$ correspond to
the transition maps of the environment (see (2.25) and (2.26)). The operator
$\widehat{R}$ corresponding to the reward is defined in (2.42), and the states
$\widehat{\sigma}(t)$ are defined in (2.27).

An alternative way of depicting a quantum decision process is shown in Figure
4 up to time $t=3$. In this depiction, we explicitly show the progression
through time of the interaction between the agent and the environment. From
the diagram in Figure 4, we see that a quantum decision process falls into the
general paradigm of agent-environment interactions considered previously in
[143, 144], and more generally we have that it falls within the theoretical
framework of quantum combs/games [145, 146, 147] (see also [148]).

The decision channels $\mathcal{D}^{t}$ in Figure 4 are defined as

$\mathcal{D}_{H_{t}\to H_{t}A_{t}}^{t}(|h^{t}\rangle\langle
h^{t}|_{H_{t}})\coloneqq|h^{t}\rangle\langle
h^{t}|_{H^{t}}\otimes\sum_{a\in\mathcal{A}}d_{t}(h^{t})(a)|a\rangle\langle
a|_{A_{t}},$ (2.24)

and the quantum channels $\mathcal{E}^{t}$, called environment response
channels, are defined as

$\displaystyle\mathcal{E}_{E_{0}\to
H_{1}E_{1}}^{0}(\rho_{E_{0}})\coloneqq\sum_{x_{1}\in\mathcal{X}}|x_{1}\rangle\langle
x_{1}|_{H_{1}}\otimes\mathcal{T}_{E_{0}\to E_{1}}^{0;x_{1}}(\rho_{E_{0}}),$
(2.25) $\displaystyle\mathcal{E}_{H_{t}A_{t}E_{t}\to
H_{t+1}E_{t+1}}^{t}(\omega_{H_{t}}\otimes\pi_{A_{t}}\otimes\rho_{E_{t}})$
$\displaystyle\coloneqq\sum_{\begin{subarray}{c}x_{t},x_{t+1}\in\mathcal{X}\\\
a_{t}\in\mathcal{A}\end{subarray}}\operatorname{Tr}_{X_{t}A_{t}}[(\omega_{H_{t}}\otimes\pi_{A_{t}})|x_{t},a_{t}\rangle\langle
x_{t},a_{t}|_{X_{t}A_{t}}]|x_{t},a_{t},x_{t+1}\rangle\langle
x_{t},a_{t},x_{t+1}|_{X_{t}A_{t}X_{t+1}}\otimes\mathcal{T}_{E_{t}\to
E_{t+1}}^{t;x_{t},a_{t},x_{t+1}}(\rho_{E_{t}})$ (2.26)

for any states $\rho_{E_{0}},\omega_{H_{t}},\pi_{A_{t}},\rho_{E_{t}}$. Using
the decision channels and the environment response channels, it is
straightforward to show that the classical-quantum states
$\widehat{\sigma}(t)$ at the end of each time step $t\geq 1$ are given by

$\widehat{\sigma}_{H_{t}E_{t}}(t)=\sum_{h^{t}}|h^{t}\rangle\langle
h^{t}|_{H_{t}}\otimes\widetilde{\sigma}_{E_{t}}(t;h^{t}),$ (2.27)

where

$\widetilde{\sigma}_{E_{t}}(t;h^{t})=\left(\prod_{j=1}^{t-1}d_{j}(h_{j}^{t})(a_{j})\right)\left(\mathcal{T}_{E_{t-1}\to
E_{t}}^{t-1;x_{t-1},a_{t-1},x_{t}}\circ\dotsb\circ\mathcal{T}_{E_{1}\to
E_{2}}^{1;x_{1},a_{1},x_{2}}\circ\mathcal{T}_{E_{0}\to
E_{1}}^{0;x_{1}}\right)(\rho_{E_{0}}).$ (2.28)

The expected quantum state at time $t\geq 1$ is then

$\sigma_{E_{t}}(t)\coloneqq\operatorname{Tr}_{H_{t}}[\widehat{\sigma}_{H_{t}E_{t}}(t)]=\sum_{h^{t}}\widetilde{\sigma}_{E_{t}}(t;h^{t}).$
(2.29)

Any quantum decision process as defined above induces a classical Markov
decision process such that the probability of any history $h^{t}$ is given by
$\Pr[H(t)=h^{t}]=\operatorname{Tr}[\widetilde{\sigma}_{E_{t}}(t;h^{t})]$.
Using this, along with (2.20), it is straightforward to show that the
transition probabilities of the induced classical Markov decision process are
given by

$\Pr[X(t+1)=x_{t+1}|X(t)=x_{t},A(t)=a_{t}]=\operatorname{Tr}[\mathcal{T}_{E_{t}\to
E_{t+1}}^{t;x_{t},a_{t},x_{t+1}}(\sigma_{E_{t}}(t|h^{t}))],$ (2.30)

for all histories $h^{t}$, where

$\sigma_{E_{t}}(t|h^{t})\coloneqq\frac{\widetilde{\sigma}_{E_{t}}(t;h^{t})}{\Pr[H(t)=h^{t}]}.$
(2.31)

is the conditional quantum state of the environment.

Finally, let us discuss how rewards are calculated. Throughout this work, we
focus our attention on so-called episodic processes, in which the decision
process proceeds for a given finite horizon time $T$ and the reward is given
only at this final time step. In particular, then, using the Hermitian
operators
$\\{R_{E_{t}}^{t;x_{t-1},a_{t-1},x_{t}}:x_{t-1},x_{t}\in\mathcal{X},a_{t-1}\in\mathcal{A},t\geq
2\\}$ and $\\{R_{E_{1}}^{1;x_{1}}:x_{1}\in\mathcal{X}\\}$ for the rewards as
described above, for any history $h^{t}=(x_{1},a_{1},\dotsc,a_{t-1},x_{t})$ we
have that

$\displaystyle t=1:$ $\displaystyle\quad
r_{1}(x_{1})\coloneqq\left\\{\begin{array}[]{l
l}\operatorname{Tr}[R_{E_{1}}^{1;x_{1}}\sigma_{E_{1}}(1|x_{1})]&\text{if
}T=1,\\\ 0&\text{otherwise},\end{array}\right.$ (2.34)
$\displaystyle\forall~{}t\geq 2:$ $\displaystyle\quad
r_{t}(x_{t-1},a_{t-1},x_{t})\coloneqq\left\\{\begin{array}[]{l l}0&\text{if
}t<T,\\\
\operatorname{Tr}[R_{E_{t}}^{t;x_{t-1},a_{t-1},x_{t}}\sigma_{E_{t}}(t|h^{t})]&\text{if
}t=T.\end{array}\right.$ (2.37)

The expected total reward up to time $T\geq 2$ is then

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}r_{t}\right]$
$\displaystyle=\mathbb{E}[r_{T}]$ (2.38)
$\displaystyle=\sum_{h^{T}}\Pr[H(T)=h^{T}]r_{T}(x_{T-1},a_{T-1},x_{T})$ (2.39)
$\displaystyle=\sum_{h^{T}}\operatorname{Tr}[R_{E_{T}}^{T;x_{T-1},a_{T-1},x_{T}}\widetilde{\sigma}_{E_{T}}(T;h^{T})]$
(2.40)
$\displaystyle=\operatorname{Tr}[\widehat{R}_{X_{T-1}A_{T-1}X_{T}E_{T}}(T)\widehat{\sigma}_{H_{T}E_{T}}(T)],$
(2.41)

where in the last line we defined the operator

$\widehat{R}_{X_{t-1}A_{t-1}X_{t}E_{t}}(t)\coloneqq\sum_{\begin{subarray}{c}x_{t-1},x_{t}\in\mathcal{X}\\\
a_{t-1}\in\mathcal{A}\end{subarray}}|x_{t-1},a_{t-1},x_{t}\rangle\langle
x_{t-1},a_{t-1},x_{t}|_{X_{t-1}A_{t-1}X_{t}}\otimes
R_{E_{t}}^{t;x_{t-1},a_{t-1},x_{t}}$ (2.42)

for all $t\geq 2$.

From now on, for simplicity of notation, we drop the subscripts containing the
labels of the classical registers of the history and the quantum systems of
the environment when writing quantum states and other operators, unless they
are needed for clarity.

We are now ready to take the generic definition of a quantum decision process
given above and apply it to the task of elementary link generation in a
quantum network. Roughly speaking, as outlined in Section 1.1 and illustrated
in Figure 2, the decision process for any elementary link is such that, at
each time step, the agent (which we define to be all of the nodes in the
elementary link as a collective entity) either requests entanglement from a
source station (which we define to be the environment) or keeps the entangled
state currently stored in memory, in which case the decoherence channel is
applied to each of the quantum systems comprising the entangled state of the
elementary link. This process goes on for a given time $T<\infty$, after which
a reward is given. Formally, we have the following.

######  Definition 2.1 (Quantum decision process for elementary link
generation).

Given any elementary link in a quantum network, as shown in Figure 2, we
define a quantum decision process for the elementary link by letting the
source station used to establish the entangled state of the elementary link be
the environment, and we let the nodes belonging to the elementary link
collectively be the agent. Then, the other elements of the quantum decision
process are defined as follows.

  * •

We let $\mathcal{X}=\\{0,1\\}$ tell us whether or not the elementary link is
active at a particular time. In particular, then, for the random variables
$X(t)$ for all $t\geq 1$, we have:

    * –

$X(t)=0$: link is inactive;

    * –

$X(t)=1$: link is active.

We let $\mathcal{A}=\\{0,1\\}$ be the set of possible actions of the agent, so
that for the random variables $A(t)$ for all $t\geq 1$, we have:

    * –

$A(t)=0$: wait/keep the entangled state;

    * –

$A(t)=1$: discard the entangled state and request a new entangled state.

  * •

The transition maps are defined to be time independent, and we denote them by
$\mathcal{T}^{x_{t},a_{t},x_{t+1}}\equiv\mathcal{T}^{t;x_{t},a_{t},x_{t+1}}$
for all $x_{t},a_{t},x_{t+1}\in\\{0,1\\}$ and all $t\geq 1$, where

$\displaystyle\mathcal{T}^{x_{t},1,1}(\sigma)$
$\displaystyle\coloneqq\operatorname{Tr}[\sigma]\,\widetilde{\rho}_{0}\quad\forall~{}x_{t}\in\\{0,1\\},$
(2.43) $\displaystyle\mathcal{T}^{x_{t},1,0}(\sigma)$
$\displaystyle\coloneqq\operatorname{Tr}[\sigma]\,\widetilde{\tau}^{\varnothing}\quad\forall~{}x_{t}\in\\{0,1\\},$
(2.44) $\displaystyle\mathcal{T}^{1,0,1}(\sigma)$
$\displaystyle\coloneqq\widehat{\mathcal{N}}(\sigma),$ (2.45)
$\displaystyle\mathcal{T}^{0,0,0}(\sigma)$ $\displaystyle\coloneqq\sigma$
(2.46)

for any linear operator $\sigma$, where we recall the definitions of
$\widetilde{\tau}^{\varnothing}$ and $\widetilde{\rho}_{0}$ from (2.8). The
maps $\mathcal{T}^{0;x_{1}}$, $x_{1}\in\\{0,1\\}$, are defined to be

$\displaystyle\mathcal{T}^{0;0}(\sigma)$
$\displaystyle\coloneqq(\mathcal{M}_{0}\circ\mathcal{L})(\sigma),$ (2.47)
$\displaystyle\mathcal{T}^{0;1}(\sigma)$
$\displaystyle\coloneqq(\mathcal{M}_{1}\circ\mathcal{L})(\sigma)$ (2.48)

for any linear operator $\sigma$, where we recall from the discussion at the
beginning of Section 2 that $\mathcal{L}$ is the transmission channel from the
source to the nodes and $\mathcal{M}_{0}$ and $\mathcal{M}_{1}$ are completely
positive trace non-increasing maps corresponding to the heralding procedure at
the nodes.

  * •

The reward at time $t\geq 1$ is defined as follows. For any history
$h^{t}=(x_{1},a_{1},\dotsc,a_{t-1},x_{t})$ and horizon time $0<T<\infty$,

$\displaystyle t=1:$ $\displaystyle\quad
r_{1}(x_{1})=\left\\{\begin{array}[]{l l}0&\text{if }T>1,\\\
\delta_{x_{1},1}\langle\psi|\sigma(1|x_{1})|\psi\rangle&\text{if
}T=1,\end{array}\right.$ (2.51) $\displaystyle\forall~{}t\geq 2:$
$\displaystyle\quad r_{t}(x_{t-1},a_{t-1},x_{t})=\left\\{\begin{array}[]{l
l}0&\text{if }t<T,\\\
\delta_{x_{t},1}\langle\psi|\sigma(t|h^{t})|\psi\rangle&\text{if
}t=T,\end{array}\right.$ (2.54)

where $|\psi\rangle\langle\psi|$ is the target/desired entangled state of the
elementary link.

  * •

The initial state $\rho_{E_{0}}$ of the environment is the state $\rho^{S}$
produced by the source station (see the discussion at the beginning of Section
2). $\blacktriangleleft$

######  Remark 2.1.

Let us make some remarks about our definition of the quantum decision process
for elementary link generation.

  * •

Note that our definition of the transition maps is consistent with our
description of the decision process given before Definition 2.1: if the action
is to wait, and the link is currently active, then we apply the decoherence
channel $\widehat{\mathcal{N}}$ to the quantum state of the link; if the
action is to request a new entangled state, then the current quantum state of
the link is discarded and a new link is attempted. If the link is currently
not active and the action is to wait, then the quantum state stays as it is.

  * •

Using (2.30) and the definition of the transition maps, we have the following
values for the transition probabilities for all $t\geq 1$ and for any history
$h^{t}=(x_{1},a_{1},\dotsc,a_{t-1},x_{t})$:

$\displaystyle\Pr[X(t+1)=0|X(t)=x_{t},A(t)=1]$ $\displaystyle=1-p,$ (2.55)
$\displaystyle\Pr[X(t+1)=1|X(t)=x_{t},A(t)=1]$ $\displaystyle=p,$ (2.56)
$\displaystyle\Pr[X(t+1)=x_{t+1}|X(t)=x_{t},A(t)=0]$
$\displaystyle=\delta_{x_{t},x_{t+1}}\quad\forall~{}x_{t+1}\in\\{0,1\\}.$
(2.57)

Observe that the transition probabilities are time independent.

  * •

Our definition of the reward in (2.51) and (2.54) is similar to the definition
of the reward given in [88, Eq. (1)], in which the reward is equal to zero for
all times except for the final time, at which point the reward is simply the
fidelity of the quantum state of the environment with respect to a desired
pure state. Using the fidelity as the reward makes sense from the perspective
of entanglement generation in a quantum network, because having higher
fidelities at the elementary link level allows for more joining measurements,
and therefore entanglement distribution over longer distances. In Section 4,
when we determine optimal policies for elementary link generation, we provide
further justification for defining the reward as in (2.51) and (2.54), and we
discuss other possible quantities to use as the reward.

Using (2.39)–(2.41), the expected total reward after $T$ time steps is

$\mathbb{E}[r_{T}]=\sum_{h^{T}}\delta_{x_{T},1}\langle\psi|\widetilde{\sigma}(T;h^{T})|\psi\rangle=\operatorname{Tr}[(|1\rangle\langle
1|_{X_{T}}\otimes|\psi\rangle\langle\psi|)\widehat{\sigma}(T)].$ (2.58)

In Theorem 2.2 below, we show that this quantity is simply the expected
fidelity of the elementary link when the link is active. $\blacktriangleleft$

We now derive an explicit expression for the conditional quantum state
$\sigma(t|h^{t})$, as defined in (2.31), for any elementary link.

######  Theorem 2.1 (Quantum state of an elementary link).

For every time step $t\geq 1$ and for any history
$h^{t}=(x_{1},a_{1},\dotsc,a_{t-1},x_{t})$, we have

$\sigma(t|h^{t})=x_{t}\rho(M(t)(h^{t}))+(1-x_{t})\tau^{\varnothing},$ (2.59)

where $M(t)$ is defined to be the random variable that indicates the number of
time steps that the quantum state of the elementary link has been held in
memory at time $t\geq 1$, and it satisfies the recursion relation

$M(t)=\left\\{\begin{array}[]{l l}M(t-1)+X(t)&\text{if }A(t-1)=0,\\\
X(t)-1&\text{if }A(t-1)=1,\end{array}\right.$ (2.60)

where $A(0)\equiv 1$ and $M(0)\equiv-1$. Furthermore,

$\Pr[H(t)=h^{t}]=\left(\prod_{j=1}^{t-1}d_{j}(h_{j}^{t})(a_{j})\right)p^{N_{\text{succ}}(t)(h^{t})}(1-p)^{N_{\text{req}}(t)(h^{t})-N_{\text{succ}}(t)(h^{t})}$
(2.61)

for all histories $h^{t}$, where

$N_{\text{req}}(t)\coloneqq\sum_{j=1}^{t}A(j-1),\quad
N_{\text{succ}}(t)\coloneqq\sum_{j=1}^{t}A(j-1)X(j)$ (2.62)

are the number of link requests and the number of successful link requests,
respectively, up to time $t$.

######  Remark 2.2.

Intuitively, the quantity $M(t)$ is the number of consecutive time steps up to
the $t^{\text{th}}$ time step that the action “wait” is performed since the
most recent “request” action. The value $M(t)=-1$ can be thought of as the
resting state of the memory, when it is not loaded. The values that $M(t)$ can
take are $-1,0,1,\dotsc,t-1$. $\blacktriangleleft$

###### Proof of Theorem 2.1.

First, let us observe that the statement of the proposition is true for $t=1$,
since by (2.71) and (2.72) we can write

$\widetilde{\sigma}(1;x_{1})=x_{1}\widetilde{\rho}_{0}+(1-x_{1})\widetilde{\tau}^{\varnothing}.$
(2.63)

Then, indeed, we have $M(1)=0$ according to the definition in (2.60), as
required, if $x_{1}=1$. Furthermore,

$\operatorname{Tr}[\widetilde{\sigma}(1;x_{1})]=x_{1}p+(1-x_{1})(1-p)=p^{x_{1}}(1-p)^{1-x_{1}},$
(2.64)

so that

$\displaystyle\sigma(1|x_{1})$
$\displaystyle=\frac{x_{1}\widetilde{\rho}_{0}+(1-x_{1})\widetilde{\tau}^{\varnothing}}{p^{x_{1}}(1-p)^{1-x_{1}}}$
(2.65) $\displaystyle=\left\\{\begin{array}[]{l l}\rho_{0}&\text{if
}x_{1}=1,\\\ \tau^{\varnothing}&\text{if }x_{1}=0,\end{array}\right.$ (2.68)
$\displaystyle=x_{1}\rho_{0}+(1-x_{1})\tau^{\varnothing}$ (2.69)

where we recall the definitions of $\rho_{0}$ and $\tau^{\varnothing}$ from
(2.9).

Now, recall from (2.28) and Definition 2.1 that

$\widetilde{\sigma}(t;h^{t})=\left(\prod_{j=1}^{t-1}d_{j}(h_{j}^{t})(a_{j})\right)\left(\mathcal{T}^{x_{t-1},a_{t-1},x_{t}}\circ\dotsb\circ\mathcal{T}^{x_{1},a_{1},x_{2}})(\widetilde{\sigma}(1;x_{1})\right),$
(2.70)

where

$\displaystyle\widetilde{\sigma}(1;0)$
$\displaystyle\coloneqq\widetilde{\tau}^{\varnothing},$ (2.71)
$\displaystyle\widetilde{\sigma}(1;1)$
$\displaystyle\coloneqq\widetilde{\rho}_{0}.$ (2.72)

Using the definition of the transition maps, for each time step $j>1$ in which
the action “wait” (i.e., $A(j)=0$) is performed and the link is active (i.e.,
$X(j)=1$), the link stays active at time step $j+1$, and thus by definition
the memory time must be incremented by one, which is consistent with the
definition of the memory time $M(t)$ given in (2.60), and the quantum state of
the link goes from $\rho(M(t))$ to $\rho(M(t)+1)$. If instead the link is
active at time $j$ and the action “request” is performed (i.e., $A(j)=1$),
then the quantum state of the link is discarded and is replaced either by the
state $\rho_{0}$ (if $X(j+1)=1$) with probability $p$ or by the state
$\tau^{\varnothing}$ (if $X(j+1)=0$) with probability $1-p$. In the former
case, the memory time must be reset to zero, consistent with (2.60), and in
the latter case, the memory time is $-1$, also consistent with (2.60).

Furthermore, by definition of the transition maps, each time the action
“request” is performed, we obtain a factor of $p$ (if the request succeeds) or
$1-p$ (if the request fails). If the action “wait” is performed, then we
obtain no additional multiplicative factors. The quantity
$N_{\text{succ}}(t-1)$ is, by definition, equal to the number of requests that
succeeded in $t-1$ time steps. Therefore, overall, we obtain a factor
$p^{N_{\text{succ}}(t-1)}$ at the $(t-1)^{\text{st}}$ time step for the number
of successful requests. The number of failed requests in $t-1$ time steps is
given by

$\displaystyle\sum_{j=1}^{t-1}A(j-1)(1-X(j))$
$\displaystyle=\sum_{j=1}^{t-1}A(j-1)-\sum_{j=1}^{t-1}A(j-1)X(j)$ (2.73)
$\displaystyle=N_{\text{req}}(t-1)-N_{\text{succ}}(t-1),$ (2.74)

so that we obtain an overall factor of
$(1-p)^{N_{\text{req}}(t-1)-N_{\text{succ}}(t-1)}$ at the $(t-1)^{\text{st}}$
time step for the failed requests. Also, the memory time at the
$(t-1)^{\text{st}}$ time step is $M(t-1)(h_{t-1}^{t})$, and the since the
quantum state is either $\rho(M(t-1)(h_{t-1}^{t}))$ or $\tau^{\varnothing}$,
we obtain

$\displaystyle\widetilde{\sigma}(t;h^{t})$
$\displaystyle=\left(\prod_{j=1}^{t-1}d_{j}(h_{j}^{t})(a_{j})\right)p^{N_{\text{succ}}(t-1)(h_{t-1}^{t})}(1-p)^{N_{\text{req}}(t-1)(h_{t-1}^{t})-N_{\text{succ}}(t-1)(h_{t-1}^{t})}$
$\displaystyle\qquad\qquad\times\left(x_{t-1}\mathcal{T}^{1,a_{t-1},x_{t}}(\rho(M(t-1)(h_{t-1}^{t})))+(1-x_{t-1})\mathcal{T}^{0,a_{t-1},x_{t}}(\tau^{\varnothing})\right)$
(2.75)
$\displaystyle=\left(\prod_{j=1}^{t-1}d_{j}(h_{j}^{t})(a_{j})\right)p^{N_{\text{succ}}(t-1)(h_{t-1}^{t})}(1-p)^{N_{\text{req}}(t-1)(h_{t-1}^{t})-N_{\text{succ}}(t-1)(h_{t-1}^{t})}$
$\displaystyle\qquad\qquad\times
p^{a_{t-1}x_{t}}(1-p)^{a_{t-1}(1-x_{t})}(x_{t}\rho(M(t)(h^{t}))+(1-x_{t})\tau^{\varnothing})$
(2.76)
$\displaystyle=\left(\left(\prod_{j=1}^{t}d_{j}(h_{j}^{t})(a_{j})\right)p^{N_{\text{succ}}(t)(h^{t})}(1-p)^{N_{\text{req}}(t)(h^{t})-N_{\text{succ}}(t)(h^{t})}\right)(x_{t}\rho(M(t)(h^{t}))+(1-x_{t})\tau^{\varnothing}).$
(2.77)

Then, since $\Pr[H(t)=h^{t}]=\operatorname{Tr}[\widetilde{\sigma}(t;h^{t})]$,
we have

$\Pr[H(t)=h^{t}]=\left(\prod_{j=1}^{t}d_{j}(h_{j}^{t})(a_{j})\right)p^{N_{\text{succ}}(t)(h^{t})}(1-p)^{N_{\text{req}}(t)(h^{t})-N_{\text{succ}}(t)(h^{t})},$
(2.78)

as required. Finally,

$\sigma(t|h^{t})=\frac{\widetilde{\sigma}(t;h^{t})}{\operatorname{Tr}[\widetilde{\sigma}(t;h^{t})]}=x_{t}\rho(M(t)(h^{t}))+(1-x_{t})\tau^{\varnothing},$
(2.79)

which completes the proof. ∎

Using Theorem 2.1, we immediately obtain an expression for the expected
quantum state of the link at any time $t\geq 1$.

######  Corollary 2.1 (Average quantum state of an elementary link).

For any $t\geq 1$, the average quantum state of any elementary link is

$\sigma(t)=(1-\Pr[X(t)=1])\tau^{\varnothing}+\sum_{m=0}^{t-1}\Pr[X(t)=1,M(t)=m]\rho(m).$
(2.80)

###### Proof.

Using the result of Theorem 2.1, along with (2.29), the expected quantum state
of the link at time $t\geq 1$ is given by

$\displaystyle\sigma(t)=\operatorname{Tr}_{H_{t}}[\widehat{\sigma}(t)]$
$\displaystyle=\sum_{h^{t}}\widetilde{\sigma}(t;h^{t})$ (2.81)
$\displaystyle=\sum_{h^{t}}\Pr[H(t)=h^{t}]\left(X(t)(h^{t})\rho(M(t)(h^{t}))+(1-X(t)(h^{t}))\tau^{\varnothing}\right)$
(2.82)
$\displaystyle=\sum_{h^{t}:x_{t}=0}\Pr[H(t)=h^{t}]\tau^{\varnothing}+\sum_{h^{t}:x_{t}=1}\Pr[H(t)=h^{t}]\rho(M(t)(h^{t}))$
(2.83)
$\displaystyle=(1-\Pr[X(t)=1])\tau^{\varnothing}+\sum_{m=0}^{t-1}\Pr[X(t)=1,M(t)=m]\rho(m),$
(2.84)

where to obtain the last equality we rearranged the sum over the set
$\\{h^{t}:x_{t}=1\\}$ so that the sum is over the possible values of the
memory time $m$, which are $0,1,\dotsc,t-1$ when the link is active. This
completes the proof. ∎

The expected quantum state of the link at time $t\geq 1$, given that the link
is active at time $t$, is defined to be

$\displaystyle\sigma(t|X(t)=1)$
$\displaystyle\coloneqq\frac{\operatorname{Tr}_{H_{t}}[|1\rangle\langle
1|_{X_{t}}\widehat{\sigma}(t)]}{\operatorname{Tr}[|1\rangle\langle
1|_{X_{t}}\widehat{\sigma}(t)]}$ (2.85)
$\displaystyle=\sum_{m=0}^{t-1}\Pr[M(t)=m|X(t)=1]\rho(m).$ (2.86)

Note that $\operatorname{Tr}[|1\rangle\langle
1|_{X_{t}}\widehat{\sigma}(t)]=\Pr[X(t)=1]$; see Theorem 2.2 below.

Observe that the expressions in (2.80) and (2.86) hold for any policy of the
agent. Given a particular policy, determining the average quantum state means
determining the joint probability distrubtion of the random variables $X(t)$
and $M(t)$, i.e., determining the quantities $\Pr[X(t)=1,M(t)=m]$ for all
possible values of $m$. The probability distribution of $X(t)$ can then be
obtained via marginalization, i.e., via
$\Pr[X(t)=1]=\sum_{m}\Pr[X(t)=1,M(t)=m]$, where the sum is over all possible
values of the memory random variable $M(t)$ (which can depend on the policy).

######  Remark 2.3.

Throughout this section, we have assumed that there are only two actions that
the agent can perform during the elementary link generation process. In
practice, it might be necessary to add other actions to the decision process,
as done in, e.g., [127]. All that has to be done in this case is to
appropriately define the transition maps in order to accomodate the additional
actions, and the general formulas in (2.27)–(2.30) still hold. We can
similarly incorporate other classical discrete-valued properties of the link
into the link random variable $X(t)$ if needed. $\blacktriangleleft$

###  2.2 Link quantities

In the previous section, we defined two elementary link quantities, the status
$X(t)$ and the memory time $M(t)$. We are interested throughout this work with
several other quantities, which we now define.

######  Definition 2.2 (Link quantities).

Given any edge in a graph corresponding to a quantum network, we define the
following quantities for the associated elementary link.

  * •

The random variable $X(t)$ for the status of the elementary link at time $t$:
$X(t)=0$ if the link is inactive, and $X(t)=1$ if the link is active.

  * •

The random variable $M(t)$ for the amount of time that the quantum state of
the elementary link is held in memory at time $t$. It is defined by the
recursion relation in (2.60). For any $t\geq 1$, the values that $M(t)$ can
take are $-1,0,1,\dotsc,t-1$. An explicit expression for $M(t)$ is the
following:

$\displaystyle M(t)$
$\displaystyle=A(0)(X(1)+X(2)+\dotsb+X(t)-1)\overline{A(1)}\,\overline{A(2)}\dotsb\overline{A(t-1)}$
$\displaystyle\quad+A(1)(X(2)+X(3)+\dotsb+X(t)-1)\overline{A(2)}\,\overline{A(3)}\dotsb\overline{A(t-1)}$
$\displaystyle\quad+A(2)(X(3)+X(4)+\dotsb+X(t)-1)\overline{A(3)}\,\overline{A(4)}\dotsb\overline{A(t-1)}$
$\displaystyle\quad+\dotsb$ $\displaystyle\quad+A(t-1)(X(t)-1)$ (2.87)
$\displaystyle=\sum_{j=1}^{t}A(j-1)\left(\sum_{\ell=j}^{t}X(\ell)-1\right)\prod_{k=j}^{t-1}\overline{A(k)},$
(2.88)

where $A(0)\equiv 1$ and $\overline{A(k)}\coloneqq 1-A(k)$ for all $k\geq 1$.
It can be shown that this definition is equivalent to the recursive definition
given in (2.60).

  * •

The random variable

$\widetilde{F}(t;\psi)\coloneqq X(t)f_{M(t)}(\rho_{0};\psi),$ (2.89)

which is the fidelity of the quantum state of the link with respect to the
target pure state $\psi$ when the link is active.

  * •

The random variable

$F(t;\psi)\coloneqq\frac{\widetilde{F}(t;\psi)}{\Pr[X(t)=1]}=\frac{X(t)f_{M(t)}(\rho_{0};\psi)}{\Pr[X(t)=1]},$
(2.90)

which is the fidelity of the quantum state of the link with respect to the
target pure state $\psi$ given that the link is active.

  * •

$N^{\max}$, which is the number of parallel edges between the nodes, and thus
the maximum number of entangled states that can be shared by the nodes of the
edge per time step (see Figure 1). We refer to each of the $N^{\max}$ parallel
edges as a parallel link. We then let

$N(t)\coloneqq\sum_{j=1}^{N^{\max}}X_{j}(t)$ (2.91)

be the number of active parallel links at time $t$, where $X_{j}(t)$ is the
status of the $j^{\text{th}}$ parallel link of the edge at time $t$.

  * •

The success rate up to time $t$ of the link:

$S(t)\coloneqq\frac{\displaystyle\sum_{\ell=1}^{N^{\max}}\sum_{j=1}^{t}A_{\ell}(j-1)X_{\ell}(j)}{\displaystyle\sum_{\ell=1}^{N^{\max}}\sum_{j=1}^{t}A_{\ell}(j-1)},$
(2.92)

which is simply the ratio of the number of successful transmissions when a
request is made to the total number of requests made within time $t$. We let
$A(0)\equiv 1$.

  * •

The link activity rate up to time $t$:

$R(t)\coloneqq\frac{1}{t}\sum_{j=1}^{t}N(j),$ (2.93)

which is the average number of active links along the edge per unit time up to
time $t$.

When we need to refer to a particular edge in the graph, we indicate the edge
on the associated elementary link quantities with a subscript, e.g.,
$X_{e}(t)$ for the status of the elementary link associated with the edge $e$.
When considering any distinct pair of edges in the graph, the corresponding
random variables defined above are independent by definition. For example, for
two edges $e\neq e^{\prime}$, the random variables $X_{e}(t)$ and
$X_{e^{\prime}}(t)$ are independent for all $t\geq 1$, and similarly for the
other random variables. $\blacktriangleleft$

######  Remark 2.4.

In a graph-theoretic setting, the quantity $N^{\max}$ can be interpreted as
the capacity of an edge. The quantity $N(t)$ is then called the flow along the
edge; see Section 3.3 for details. $\blacktriangleleft$

The success rate $S(t)$ and the link activity rate $R(t)$ are two rate
measures that we have defined for an elementary link. The first measure is the
number of successful requests per channel use up to time $t$ (indeed, notice
that the quantity $\sum_{\ell=1}^{N^{\max}}\sum_{j=1}^{t}A_{\ell}(j-1)$ in the
denominator of $S(t)$ is the number of uses of the transmission channel in $t$
time steps). The second rate measure is the average number of parallel links
obtained per unit time up to time $t$. When $N^{\max}=1$, $R(t)$ can be
thought of as the fraction of time that the link is active in $t$ time steps.

######  Theorem 2.2 (Link success probability and fidelity).

Given any elementary link in a quantum network, the probability distribution
of the link value $X(t)$ (equivalently, the expectation value
$\mathbb{E}[X(t)]$) can be written as

$\Pr[X(t)=1]=\operatorname{Tr}[|1\rangle\langle
1|_{X_{t}}\widehat{\sigma}(t)]=\mathbb{E}[X(t)],$ (2.94)

where we recall the definition of the classical-quantum state
$\widehat{\sigma}(t)$ in (2.27). We also have that

$\displaystyle\mathbb{E}[\widetilde{F}(t;\psi)]$
$\displaystyle=\sum_{m=0}^{t-1}f_{m}(\rho_{0};\psi)\Pr[X(t)=1,M(t)=m]$ (2.95)
$\displaystyle=\operatorname{Tr}[(|1\rangle\langle
1|_{X_{t}}\otimes\psi)\widehat{\sigma}(t)],$ (2.96)

and

$\displaystyle\mathbb{E}[F(t;\psi)]$
$\displaystyle=\frac{\mathbb{E}[\widetilde{F}(t;\psi)]}{\Pr[X(t)=1]}$ (2.97)
$\displaystyle=\sum_{m=0}^{t-1}f_{m}(\rho_{0};\psi)\Pr[M(t)=m|X(t)=1]$ (2.98)
$\displaystyle=\frac{\operatorname{Tr}[(|1\rangle\langle
1|_{X_{t}}\otimes\psi)\widehat{\sigma}(t)]}{\operatorname{Tr}[|1\rangle\langle
1|_{X_{t}}\widehat{\sigma}(t)]}.$ (2.99)

###### Proof.

To see the first equality in (2.94), observe that

$\operatorname{Tr}[|1\rangle\langle
1|_{X_{t}}\widehat{\sigma}(t)]=\sum_{h^{t}:X(t)(h^{t})=1}\Pr[H(t)=h^{t}].$
(2.100)

The expression on the right-hand side of this equation is equal to
$\Pr[X(t)=1]$ by definition of the random variable $X(t)$. The second equality
in (2.94) holds because $X(t)$ is a binary/Bernoulli random variable.

The equality in (2.95) follows by definition of $\widetilde{F}(t;\psi)$ and by
definition of expectation. The equality in (2.96) follows by considering that

$\displaystyle\operatorname{Tr}[(|1\rangle\langle
1|_{X_{t}}\otimes\psi)\widehat{\sigma}(t)]$
$\displaystyle=\sum_{h^{t}:x_{t}=1}\Pr[H(t)=h^{t}]\langle\psi|\rho(M(t)(h^{t}))|\psi\rangle$
(2.101)
$\displaystyle=\sum_{h^{t}:x_{t}=1}\Pr[H(t)=h^{t}]f_{M(t)(h^{t})}(\rho_{0};\psi),$
(2.102)

and by considering that the sum over $\\{h^{t}:x_{t}=1\\}$ can be rearranged
into a sum over the possible values of the memory time $M(t)$ when the link is
active, which are $0,1,\dotsc,t-1$. The expressions in (2.98) and (2.99) are
then immediate. ∎

In the following section, we consider a particular policy, the so-called
“memory cutoff” policy, and we determine analytic expressions for
$\Pr[X(t)=1]$, $\Pr[X(t)=1,M(t)=m]$, and for the expected values of
$\widetilde{F}(t)$ and $F(t)$, under this policy.

##  3 The memory cutoff policy for elementary link generation

A natural policy to consider, and one that has been considered extensively
previously [31, 32, 33, 34, 99, 100, 101, 102, 103, 104, 105], is the
following. A link is requested at every time step until the link is
established, and once the link is established, it is held in quantum memories
for some pre-specified amount $t^{\star}$ of time (usually called the “memory
cutoff” and not necessarily equal to the memory coherence time) before the
link is discarded and requested again. The cutoff $t^{\star}$ can be any non-
negative integer. There are two extreme cases of this policy: when
$t^{\star}=0$, a request is made at every time step regardless of whether the
previous request succeeded; if $t^{\star}=\infty$, then a link request is made
at every time step until the link request succeeds, and once the link request
succeeds the quantum systems remain in memory indefinitely—no further request
is ever made. In this section, we provide a complete analysis of this policy,
including analytic formulas for the link value probability and the expected
link fidelity as a function of time, along with the infinite-horizon
($t\to\infty$) behavior of the link.

For the memory cutoff policy with cutoff $t^{\star}$, we denote the memory
time random variable by $M_{t^{\star}}(t)$. It turns out to be more convenient
to use the following simpler formula for the memory time $M_{t^{\star}}(t)$
than the general formula given in (2.88) when $t^{\star}<\infty$:

$M_{t^{\star}}(t)=\left(\sum_{j=1}^{t}X(t)-1\right)\text{mod}(t^{\star}+1),\quad
t^{\star}<\infty.$ (3.1)

With this formula, the memory time is always in $\\{0,1,\dotsc,t^{\star}\\}$
when $t^{\star}<\infty$. Also note that, with this formula, we get a memory
value of $-1\text{mod}(t^{\star}+1)=t^{\star}$ even when the memory is not
loaded. The advantage of this is that, if $M_{t^{\star}}(t)<t^{\star}$, then
$X(t)=1$. When $t^{\star}=\infty$, we have

$M_{\infty}(t)=\sum_{j=1}^{t}X(t)-1,$ (3.2)

and so the values that the memory time can take are $-1,0,1,\dotsc,t-1$.

Mathematically, the memory cutoff policy is described as follows for all
$t^{\star}\geq 0$:

$d_{t}(h^{t})(a_{t})=\Pr[A(t)=a_{t}|H(t)=h^{t}]=\delta_{a_{t},M_{t^{\star}}^{\prime}(t)(h^{t})},$
(3.3)

where for all $t^{\star}<\infty$,

$M_{t^{\star}}^{\prime}(t)(h^{t})\coloneqq\delta_{M(t)(h^{t}),t^{\star}}=\left\\{\begin{array}[]{l
l}0&\text{if }M_{t^{\star}}(t)(h^{t})<t^{\star},\\\ 1&\text{if
}M_{t^{\star}}(t)(h^{t})=t^{\star}\end{array}\right.$ (3.4)

is the function that tells us whether or not the memory time is equal to
$t^{\star}$. For $t^{\star}=\infty$, we have

$M_{\infty}^{\prime}(t)(h^{t})\coloneqq\left\\{\begin{array}[]{l l}1&\text{if
}M_{\infty}(t)(h^{t})=-1,\\\ 0&\text{otherwise}.\end{array}\right.$ (3.5)

From this, we see that the memory cutoff policy is deterministic and that the
action at each time step is determined by the value of
$M_{t^{\star}}^{\prime}(t)$ for all $t^{\star}\geq 0$. In particular,

$A(t)=0\quad\Longleftrightarrow\quad M_{t^{\star}}^{\prime}(t)=0,\qquad
A(t)=1\quad\Longleftrightarrow\quad M_{t^{\star}}^{\prime}(t)=1.$ (3.6)

In other words,

$\Pr[X(t+1)=x_{t+1}|H(t)=h^{t},A(t)=a_{t}]=\Pr[X(t+1)=x_{t+1}|H(t)=h^{t},M_{t^{\star}}^{\prime}(t)=a_{t}],$
(3.7)

for all histories $h^{t}$, all $a_{t},x_{t+1}\in\\{0,1\\}$, and all
$t^{\star}\geq 0$. In particular, we can use (2.57) to conclude that

$\Pr[X(t+1)=x_{t+1}|H(t)=h^{t},M_{t^{\star}}^{\prime}(t)=0]=\left\\{\begin{array}[]{l
l}0&\text{if }x_{t+1}=0,\\\ 1&\text{if }x_{t+1}=1.\end{array}\right.$ (3.8)

The transition probabilities given in (2.55)–(2.57) therefore reduce to the
following for the memory cutoff policy:

$\displaystyle\Pr[X(t+1)=0|H(t)=h^{t},M_{t^{\star}}^{\prime}(t)=1]$
$\displaystyle=1-p,$ (3.9)
$\displaystyle\Pr[X(t+1)=1|H(t)=h^{t},M_{t^{\star}}^{\prime}(t)=1]$
$\displaystyle=p,$ (3.10)
$\displaystyle\Pr[X(t+1)=0|H(t)=h^{t},M_{t^{\star}}^{\prime}(t)=0]$
$\displaystyle=0,$ (3.11)
$\displaystyle\Pr[X(t+1)=1|H(t)=h^{t},M_{t^{\star}}^{\prime}(t)=0]$
$\displaystyle=1,$ (3.12)

for all histories $h^{t}$ and all $t^{\star}\geq 0$. The following conditional
probabilities then hold for any $t^{\star}<\infty$:

$\displaystyle\Pr[X(t+1)=1,M_{t^{\star}}(t+1)=0|X(t)=0,M_{t^{\star}}(t)=m]$
$\displaystyle=p,\quad 0\leq m\leq t^{\star},$ (3.13)
$\displaystyle\Pr[X(t+1)=1,M_{t^{\star}}(t+1)=0|X(t)=1,M_{t^{\star}}(t)=t^{\star}]$
$\displaystyle=p,$ (3.14)
$\displaystyle\Pr[X(t+1)=0,M_{t^{\star}}(t+1)=t^{\star}|X(t)=0,M_{t^{\star}}(t)=m]$
$\displaystyle=1-p,\quad 0\leq m\leq t^{\star},$ (3.15)
$\displaystyle\Pr[X(t+1)=0,M_{t^{\star}}(t+1)=t^{\star}|X(t)=1,M_{t^{\star}}(t)=t^{\star}]$
$\displaystyle=1-p,$ (3.16)
$\displaystyle\Pr[X(t+1)=1,M_{t^{\star}}(t+1)=m+1|X(t)=1,M_{t^{\star}}(t)=m]$
$\displaystyle=1,\quad 0\leq m\leq t^{\star}-1,$ (3.17)
$\displaystyle\Pr[X(t+1)=0,M_{t^{\star}}(t+1)=t^{\star}|X(t)=0,M_{t^{\star}}(t)=t^{\star}]$
$\displaystyle=1,$ (3.18)

with all other possible conditional probabilities equal to zero. Since these
transition probabilities are time-independent, and since the pair
$(X(t+1),M_{t^{\star}}(t+1))$ depends only on $(X(t),M_{t^{\star}}(t))$, we
have that $((X(t),M_{t^{\star}}(t)):t\geq 1)$ is a stationary/time-homogeneous
Markov process. As such, the conditional probabilities can be organized into
the transition matrix $T(t^{\star})$, $t^{\star}<\infty$, defined as follows:

$\left(T(t^{\star})\right)_{\begin{subarray}{c}x,m\\\
x^{\prime},m^{\prime}\end{subarray}}\coloneqq\Pr[X(t+1)=x,M_{t^{\star}}(t+1)=m|X(t)=x^{\prime},M_{t^{\star}}(t)=m^{\prime}],\\\
x,x^{\prime}\in\\{0,1\\},~{}m,m^{\prime}\in\\{0,1,\dotsc,t^{\star}\\}.$ (3.19)

For $t^{\star}=\infty$, observe that the action at time $t\geq 1$ depends only
the current value of the link, not on the entire history of the link. In other
words, the definition of $M_{\infty}^{\prime}(t)$ in (3.5) is equivalent to

$M_{\infty}^{\prime}(t)=1-X(t).$ (3.20)

Indeed, if $X(t)=0$, then by definition of the $t^{\star}=\infty$ cutoff
policy a request is made, so that $M_{\infty}^{\prime}(t)=1$, as required. If
$X(t)=1$, then the link is kept, meaning that $M_{\infty}^{\prime}(t)=0$. The
transition probabilities in (3.9)–(3.12) can therefore be simplified to the
following when $t^{\star}=\infty$:

$\displaystyle\Pr[X(t+1)=0|X(t)=0]$ $\displaystyle=1-p,$ (3.21)
$\displaystyle\Pr[X(t+1)=0|X(t)=1]$ $\displaystyle=0,$ (3.22)
$\displaystyle\Pr[X(t+1)=1|X(t)=0]$ $\displaystyle=p,$ (3.23)
$\displaystyle\Pr[X(t+1)=1|X(t)=1]$ $\displaystyle=1.$ (3.24)

These transition probabilities are time-independent and Markovian, so they can
be organized into the transition matrix $T(\infty)$ defined as follows:

$\left(T(\infty)\right)_{\begin{subarray}{c}x\\\
x^{\prime}\end{subarray}}\coloneqq\Pr[X(t+1)=x|X(t)=x^{\prime}],\quad
x,x^{\prime}\in\\{0,1\\}.$ (3.25)

To begin our analysis of the memory cutoff policy, let us consider what the
histories $h^{t}$ look like by considering a particular example. Consider a
link for which $t^{\star}=3$, and let us consider the link values up to time
$t=10$. Given that each link request succeeds with probability $p$ and fails
with probability $1-p$, in Table 1 we write down the probability for each
sequence of link values according to the formula in (2.61). Note that we only
include those histories that have non-zero probability (indeed, some sequences
$h^{t}=(x_{1},a_{1},\dotsc,a_{t-1},x_{t})\in\\{0,1\\}^{2t-1}$ will have zero
probability under the memory cutoff policy). We also include in the table the
memory times $M_{t^{\star}}(t)$, which are calculated using the formula in
(3.1). Since the memory cutoff policy is deterministic, it suffices to keep
track only of the link values and not of the action values, since the action
values are given deterministically by the link values. For the link value
sequences, we define two quantities that are helpful for obtaining analytic
formulas for the link quantities defined in Section 2.2. The first quantity is
$Y_{1}(t)$, which we define to be the number of full blocks of ones (having
length $t^{\star}+1$) in link value sequences up to time $t-1$. The values
that $Y_{1}(t)$ can take are
$0,1,\dotsc,\lfloor\frac{t-1}{t^{\star}+1}\rfloor$ if $t^{\star}<\infty$, and
0 if $t^{\star}=\infty$. We also define the quantity $Y_{2}(t)$ to be the
number of trailing ones in link value sequences up to time $t$. The values
that $Y_{2}(t)$ can take are $0,1,\dotsc,t^{\star}+1$ if $t^{\star}<\infty$,
and $0,1,\dotsc,t$ if $t^{\star}=\infty$.

$x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $x_{5}$ | $x_{6}$ | $x_{7}$ | $x_{8}$ | $x_{9}$ | $x_{10}$ | $Y_{1}(t)(h^{t})$ | $Y_{2}(t)(h^{t})$ | $\Pr[H(t)=h^{t}]$ | $M_{t^{\star}}(t)(h^{t})$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | $(1-p)^{10}$ | 3
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | $p(1-p)^{6}$ | 3
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | $p(1-p)^{6}$ | 3
0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | $p(1-p)^{6}$ | 3
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | $p(1-p)^{6}$ | 3
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | $p(1-p)^{6}$ | 3
0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | $p(1-p)^{6}$ | 3
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 2 | 0 | $p^{2}(1-p)^{2}$ | 3
1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 2 | 0 | $p^{2}(1-p)^{2}$ | 3
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 2 | 0 | $p^{2}(1-p)^{2}$ | 3
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | $p(1-p)^{9}$ | 0
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 2 | $p(1-p)^{8}$ | 1
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 3 | $p(1-p)^{7}$ | 2
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 4 | $p(1-p)^{6}$ | 3
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | $p^{2}(1-p)^{5}$ | 0
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | $p^{2}(1-p)^{5}$ | 0
0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | $p^{2}(1-p)^{5}$ | 0
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | $p^{2}(1-p)^{5}$ | 0
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | $p^{2}(1-p)^{5}$ | 0
0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | $p^{2}(1-p)^{5}$ | 0
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | $p^{2}(1-p)^{4}$ | 1
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 2 | $p^{2}(1-p)^{4}$ | 1
0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 2 | $p^{2}(1-p)^{4}$ | 1
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 2 | $p^{2}(1-p)^{4}$ | 1
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | $p^{2}(1-p)^{4}$ | 1
1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 3 | $p^{2}(1-p)^{3}$ | 2
0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 3 | $p^{2}(1-p)^{3}$ | 2
0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 3 | $p^{2}(1-p)^{3}$ | 2
0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | $p^{2}(1-p)^{3}$ | 2
1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 4 | $p^{2}(1-p)^{2}$ | 3
0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 4 | $p^{2}(1-p)^{2}$ | 3
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 4 | $p^{2}(1-p)^{2}$ | 3
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 2 | 1 | $p^{3}(1-p)$ | 0
1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | $p^{3}(1-p)$ | 0
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | $p^{3}(1-p)$ | 0
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | $p^{3}$ | 1
Table 1: Link value sequences for a link with $t^{\star}=3$ up to time $t=10$.
The quantity $Y_{1}(t)$ is the number of full blocks of ones in link value
sequences up to time $t-1$, and $Y_{2}(t)$ is the number of trailing ones in
link value sequences up to time $t$. $M_{t^{\star}}(t)$ is the memory time at
time $t$, given by the formula in (3.1).

Using the quantities $Y_{1}(t)$ and $Y_{2}(t)$, along with the general formula
in (2.61), we obtain the following formula for the probability of histories
with non-zero probability.

######  Proposition 3.1.

For any $t\geq 1$, any $t^{\star}<\infty$, any $p\in[0,1]$, and for any
history $h^{t}=(x_{1},a_{1},x_{2},\allowbreak a_{2},\dotsc,a_{t-1},x_{t})$
with non-zero probability,

$\Pr[H(t)=h^{t}]=p^{Y_{1}(t)(h^{t})}(1-p)^{t-(t^{\star}+1)Y_{1}(t)(h^{t})}\delta_{Y_{2}(t)(h^{t}),0}\\\
+(1-\delta_{Y_{2}(t)(h^{t}),0})p^{Y_{1}(t)(h^{t})+1}(1-p)^{t-Y_{2}(t)(h^{t})-(t^{\star}+1)Y_{1}(t)(h^{t})},$
(3.26)

where $Y_{1}(t)(h^{t})$ is defined to be the number of full blocks of ones of
length $t^{\star}+1$ up to time $t-1$ in the sequence
$(x_{1},x_{2},\dotsc,x_{t})$ of link values, and $Y_{2}(t)(h^{t})$ is defined
to be the number of trailing ones in the sequence
$(x_{1},x_{2},\dotsc,x_{t})$. For $t^{\star}=\infty$,

$\Pr[H(t)=h^{t}]=(1-p)^{t}\delta_{Y_{2}(t)(h^{t}),0}+(1-\delta_{Y_{2}(t)(h^{t}),0})p(1-p)^{t-Y_{2}(t)(h^{t})}.$
(3.27)

###### Proof.

The result in (3.26) follows immediately from the formula in (2.61) by
observing that $N_{\text{succ}}(t)=Y_{1}(t)+1-\delta_{Y_{2}(t),0}$ and
$N_{\text{req}}(t)=t-(t^{\star}+1)Y_{1}(t)-Y_{2}(t)$. For $t^{\star}=\infty$,
we only ever have trailing ones in the link value sequences, so that
$Y_{1}(t)(h^{t})=0$ for all $t\geq 1$ and all histories $h^{t}$. The result in
(3.27) then follows. ∎

Next, let us consider the number of link value sequences with non-zero
probability, which we need in order to calculate the link quantities defined
in Section 2.2. Using Table 1 as a guide, we obtain the following.

######  Lemma 3.1.

For any $t\geq 1$ and any $t^{\star}\geq 0$, let $\Omega(t;t^{\star})$ denote
the set of link value sequences for the $t^{\star}$ memory cutoff policy that
have non-zero probability. Then, for all $t^{\star}<\infty$,

$\left|\Omega(t;t^{\star})\right|=\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\sum_{k=0}^{t^{\star}+1}\left(\binom{t-1-xt^{\star}}{x}\delta_{k,0}+(1-\delta_{k,0})\binom{t-k-
xt^{\star}}{x}\boldsymbol{1}_{t-k-x(t^{\star}+1)\geq 0}\right).$ (3.28)

For $t^{\star}=\infty$, $\left|\Omega(t;\infty)\right|=1+t$.

###### Proof.

We start by counting the number of link value sequences when the number of
trailing ones is equal to zero, i.e., when $k\equiv Y_{2}(t)(h^{t})=0$. If we
also let the number $x\equiv Y_{1}(t)(h^{t})$ of full blocks of ones in time
$t-1$ be equal to one, then there are $t^{\star}+1$ ones and $t-t^{\star}-2$
zeros up to time $t-1$. The total number of link value sequences is then equal
to the number of ways that the single block of ones can be moved around in the
link value sequence up to time $t-1$. This quantity is equivalent to the
number of permutations of $t-1-t^{\star}$ objects with $t-t^{\star}-2$ of them
being identical (these are the zeros), which is given by

$\frac{(t-1-t^{\star})!}{(t-2-t^{\star})!(t-1-t^{\star}-t+t^{\star}+2)!}=\frac{(t-1-t^{\star})!}{(t-t^{\star}-2)!(1)!}=\binom{t-1-t^{\star}}{1}.$
(3.29)

We thus have the $x=0$ and $k=0$ term in the sum in (3.28). If we stick to
$k=0$ but now consider more than one full block of ones in time $t-1$ (i.e.,
let $x\equiv Y_{1}(t)(h^{t})\geq 1$), then the number of link value sequences
is given by a similar argument as before: it is equal to the number of ways of
permuting $t-1-xt^{\star}$ objects, with $x$ of them being identical (the
blocks of ones) and the remaining $t-1-x(t^{\star}+1)$ objects also identical
(the number of zeros), i.e., $\binom{t-1-xt^{\star}}{x}$. The total number of
link value sequences with zero trailing ones is therefore

$\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\binom{t-1-xt^{\star}}{x}.$
(3.30)

Let us now consider the case $k\equiv Y_{2}(t)(h^{t})>0$. Then, the number of
time slots in which full blocks of ones can be shuffled around is $t-k$. If
there are $x$ blocks of ones in time $t-k$, then by the same arguments as
before, the number of such link value sequences is given by the number of ways
of permuting $t-k-xt^{\star}$ objects, with $x$ of them being identical (the
full blocks of ones) and the remaining $t-k-x(t^{\star}+1)$ of them also
identical (these are the zeros up to time $t-k$). In other words, the number
of link value sequences with $k>0$ and $x\geq 0$ is

$\binom{t-k-xt^{\star}}{x}\boldsymbol{1}_{t-k-x(t^{\star}+1)\geq 0}.$ (3.31)

We must put the indicator function $\boldsymbol{1}_{t-k-x(t^{\star}+1)\geq 0}$
in order to ensure that the binomial coefficient makes sense. This also means
that, depending on the time $t$, not all values of $k$ between 0 and
$t^{\star}+1$ can be considered in the total number of link value sequences
(simply because it might not be possible to fit all possible values of
trailing ones and full blocks of ones within that amount of time). By
combining (3.30) and (3.31), we obtain the desired result.

In the case $t^{\star}=\infty$, because there are never any full blocks of
ones and only trailing ones, we have $t$ link value sequences, each containing
$k$ trailing ones, where $1\leq k\leq t$. We also have a link value sequence
consisting of all zeros, giving a total of $t+1$ link value sequences. ∎

######  Remark 3.1.

Note that when $t^{\star}=0$, we get

$\displaystyle\left|\Omega(t;0)\right|$
$\displaystyle=\sum_{x=0}^{t-1}\sum_{k=0}^{1}\left(\binom{t-1}{x}\delta_{k,0}+(1-\delta_{k,0})\binom{t-k}{x}\boldsymbol{1}_{t-k-x\geq
0}\right)$ (3.32)
$\displaystyle=\sum_{x=0}^{t-1}\binom{t-1}{x}+\sum_{x=0}^{t-1}\binom{t-1}{x}\underbrace{\boldsymbol{1}_{t-1-x\geq
0}}_{1~{}\forall x}$ (3.33) $\displaystyle=2^{t-1}+2^{t-1}$ (3.34)
$\displaystyle=2^{t}.$ (3.35)

In other words, when $t^{\star}=0$, all $t$-bit strings are valid link value
sequences.

For $t\leq t^{\star}+1$, no full blocks of ones in time $t-1$ are possible, so
we get

$\displaystyle\left|\Omega(t;t^{\star})\right|$
$\displaystyle=\sum_{k=0}^{t^{\star}+1}\left(\binom{t-1}{0}\delta_{k,0}+(1-\delta_{k,0})\binom{t-k}{0}\boldsymbol{1}_{t-k\geq
0}\right)$ (3.36) $\displaystyle=\binom{t-1}{0}+\sum_{k=1}^{t}\binom{t-k}{0}$
(3.37) $\displaystyle=1+t.$ (3.38)

This coincides with the result for $t^{\star}=\infty$, because when
$t^{\star}=\infty$ the condition $t\leq t^{\star}+1$ is satisfied for all
$t\geq 1$. $\blacktriangleleft$

###  3.1 Calculation of link quantities

We now provide analytic expressions for the link quantities defined in Section
2.2 in both the finite-horizon and infinite-horizon cases. All of the results
here apply to any individual elementary link along an edge of the graph
associated with the given quantum network, including individual parallel links
in the case that an edge has $N^{\max}>1$ parallel edges, since all of the
parallel elementary links corresponding to the parallel edges are mutually
independent. We discuss multiple parallel links in more detail in Section 3.3.

We begin by considering the expected fidelity of the link and the expected
quantum state of the link. Recall from Corollary 2.1 and Theorem 2.2 that the
main ingredient for the calculation of the expected fidelity and the expected
quantum state is the joint probability distribution of the random variables
$X(t)$ and $M(t)$.

######  Proposition 3.2.

For any $t\geq 1$, $t^{\star}\geq 0$, and $p\in[0,1]$,

$\Pr[M_{t^{\star}}(t)=m,X(t)=1]=p(1-p)^{t-(m+1)},\quad t\leq
t^{\star}+1,~{}0\leq m\leq t-1,$ (3.39)

and

$\Pr[M_{t^{\star}}(t)=m,X(t)=1]=\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\binom{t-(m+1)-xt^{\star}}{x}\boldsymbol{1}_{t-(m+1)-x(t^{\star}+1)\geq
0}p^{x+1}(1-p)^{t-(m+1)-x(t^{\star}+1)},\\\ t>t^{\star}+1,~{}0\leq m\leq
t^{\star}.$ (3.40)

###### Proof.

For $t\leq t^{\star}+1$, because no full blocks of ones up to time $t-1$ are
possible, the possible values for the memory time are $0,1,\dotsc,t-1$.
Furthermore, for each value of $m\in\\{0,1,\dotsc,t-1\\}$, there is only one
link value sequence for which $M_{t^{\star}}(t)=m$, and this sequence has
$Y_{2}(t)=m+1$ trailing ones and thus probability $p(1-p)^{t-1-m}$ by
Proposition 3.1.

For $t>t^{\star}+1$, we proceed similarly by considering the number $Y_{1}(t)$
of full blocks of ones in time $t-1$ and the number $Y_{2}(t)$ of trailing
ones in link value sequences $(x_{1},x_{2},\dotsc,x_{t})$ such that $x_{t}=1$.
Since we must have $x_{t}=1$, we require $Y_{2}(t)\geq 1$. Now, in order to
have a memory time of $M_{t^{\star}}(t)=m$, we can have link value sequences
consisting of any number $x=Y_{1}(t)$ of full blocks of ones ranging from 0 to
$\lfloor\frac{t-1}{t^{\star}+1}\rfloor$ as long as $Y_{2}(t)=m+1$. (Note that
at the end of each full block of ones the memory time is equal to
$t^{\star}$.) The number of such link value sequences is

$\binom{t-(m+1)-xt^{\star}}{x}\boldsymbol{1}_{t-(m+1)-x(t^{\star}+1)\geq 0},$
(3.41)

as given by (3.31), and the probability of each such link value sequence is
$p^{x+1}(1-p)^{t-(m+1)-x(t^{\star}+1)}$. By summing over all $0\leq
x\leq\lfloor\frac{t-1}{t^{\star}+1}\rfloor$, we obtain the desired result. ∎

As an immediate corollary of Proposition 3.2, we obtain the probability
distribution of the link value random variable $X(t)$.

######  Corollary 3.1.

For any $t\geq 1$, any $t^{\star}\geq 0$, and any $p\in[0,1]$,

$\Pr[X(t)=1]=\left\\{\begin{array}[]{l l}1-(1-p)^{t},&t\leq
t^{\star}+1,\\\\[14.22636pt]
\displaystyle\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\sum_{k=1}^{t^{\star}+1}\binom{t-k-
xt^{\star}}{x}\boldsymbol{1}_{t-k-x(t^{\star}+1)\geq
0}p^{x+1}(1-p)^{t-k-(t^{\star}+1)x},&t>t^{\star}+1\end{array}\right.$ (3.42)

###### Proof.

This follows immediately from the fact that
$\Pr[X(t)=1]=\sum_{m=0}^{t-1}\Pr[X(t)=1,M_{t^{\star}}(t)=m]$ for $t\leq
t^{\star}+1$ and that
$\Pr[X(t)=1]=\sum_{m=0}^{t^{\star}}\Pr[X(t)=1,M_{t^{\star}}(t)=m]$ for
$t>t^{\star}+1$. ∎

Figure 5: (Left) The expected link value, given by (3.42), as a function of
the link success probability $p$ for various values of $t$ and $t^{\star}$.
(Right) The expected link value, given by (3.42), as a function of $t$ for
fixed values of $p$ and $t^{\star}$.

See Figure 5 for plots of $\mathbb{E}[X(t)]$ as a function of the time steps
$t$ and as a function of the elementary link generation probability $p$.

Let us now recall the following quantities:

$\widetilde{F}(t;\psi)=X(t)f_{M(t)}(\rho_{0};\psi),\quad
F(t;\psi)=\frac{\widetilde{F}(t;\psi)}{\Pr[X(t)=1]},$ (3.43)

the latter being the fidelity of the link given that the link is active. From
Proposition 3.2 and Corollary 3.1, along with (2.95) and (2.98), we
immediately obtain analytic expressions for the expectation values of these
quantities under the memory cutoff policy:

$\displaystyle\mathbb{E}[\widetilde{F}(t;\psi)]$
$\displaystyle=\left\\{\begin{array}[]{l
l}\displaystyle\sum_{m=0}^{t-1}f_{m}(\rho_{0};\psi)p(1-p)^{t-(m+1)}&t\leq
t^{\star}+1,\\\\[14.22636pt]
\displaystyle\sum_{m=0}^{t^{\star}}f_{m}(\rho_{0};\psi)\Pr[M_{t^{\star}}(t)=m,X(t)=1],&t>t^{\star}+1,\end{array}\right.$
(3.46) $\displaystyle\mathbb{E}[F(t;\psi)]$
$\displaystyle=\left\\{\begin{array}[]{l
l}\displaystyle\sum_{m=0}^{t-1}f_{m}(\rho_{0};\psi)\frac{p(1-p)^{t-(m+1)}}{1-(1-p)^{t}}&t\leq
t^{\star}+1,\\\\[14.22636pt]
\displaystyle\sum_{m=0}^{t^{\star}}f_{m}(\rho_{0};\psi)\frac{\Pr[M_{t^{\star}}(t)=m,X(t)=1]}{\Pr[X(t)=1]},&t>t^{\star}+1,\end{array}\right.$
(3.49)

where in (3.46) and (3.49) the expression for $\Pr[M_{t^{\star}}(t)=m,X(t)=1]$
for $t>t^{\star}+1$ is given in (3.40), and the expression for $\Pr[X(t)=1]$
for $t>t^{\star}+1$ is given in (3.42). Furthermore, from (2.80), we have that
the expected quantum state of the link at time $t\geq 1$ is

$\sigma(t)=\left\\{\begin{array}[]{l
l}\displaystyle(1-p)^{t}\tau^{\varnothing}+\sum_{m=0}^{t-1}p(1-p)^{t-(m+1)}\rho(m),&t\leq
t^{\star}+1,\\\\[14.22636pt]
\displaystyle(1-\Pr[X(t)=1])\tau^{\varnothing}+\sum_{m=0}^{t^{\star}}\Pr[M_{t^{\star}}(t)=m,X(t)=1]\rho(m)&t>t^{\star}+1,\end{array}\right.$
(3.50)

where for $t>t^{\star}+1$ the expressions for $\Pr[X(t)=1]$ and
$\Pr[M_{t^{\star}}(t)=m,X(t)=1]$ are given in (3.42) and (3.40), respectively.
From (2.86), we also have

$\sigma(t|X(t)=1)=\left\\{\begin{array}[]{l
l}\displaystyle\sum_{m=0}^{t-1}\frac{p(1-p)^{t-(m+1)}}{1-(1-p)^{t}}\rho(m),&t\leq
t^{\star}+1,\\\\[14.22636pt]
\displaystyle\sum_{m=0}^{t^{\star}}\frac{\Pr[M_{t^{\star}}(t)=m,X(t)=1]}{\Pr[X(t)=1]}\rho(m),&t>t^{\star}+1,\end{array}\right.$
(3.51)

where again for $t>t^{\star}+1$ the expressions for $\Pr[X(t)=1]$ and
$\Pr[M_{t^{\star}}(t)=m,X(t)=1]$ are given in (3.42) and (3.40), respectively.

Let us now consider the $t\to\infty$, or infinite-horizon behavior of the
link.

######  Theorem 3.1.

For all $t^{\star}\geq 0$ and $p\in[0,1]$.

$\lim_{t\to\infty}\mathbb{E}[X(t)]=\frac{(t^{\star}+1)p}{1+t^{\star}p}.$
(3.52)

###### Proof.

Since we consider the limit $t\to\infty$, it suffices to consider the
expression for $\Pr[X(t)=1]$ in (3.42) for $t>t^{\star}+1$. Also due to the
$t\to\infty$ limit, we can disregard the indicator function in (3.42), so that

$\lim_{t\to\infty}\mathbb{E}[X(t)]=\lim_{t\to\infty}\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\sum_{k=1}^{t^{\star}+1}\binom{t-k-
xt^{\star}}{x}p^{x+1}(1-p)^{t-k-(t^{\star}+1)x}.$ (3.53)

Next, consider the binomial expansion of $(1-p)^{t-k-(t^{\star}+1)x}$:

$(1-p)^{t-k-(t^{\star}+1)x}=\sum_{j=0}^{\infty}\binom{t-k-(t^{\star}+1)x}{j}(-1)^{j}p^{j}.$
(3.54)

Substituting this into (3.53) gives us

$\displaystyle\lim_{t\to\infty}\mathbb{E}[X(t)]$
$\displaystyle=p\lim_{t\to\infty}\sum_{x,j=0}^{\infty}\sum_{k=1}^{t^{\star}+1}\binom{t-k-t^{\star}x}{x}\binom{t-k-(t^{\star}+1)x}{j}(-1)^{j}p^{x+j}$
(3.55)
$\displaystyle=p\lim_{t\to\infty}\sum_{\ell=0}^{\infty}\sum_{j=0}^{\ell}\sum_{k=1}^{t^{\star}+1}\binom{t-k-t^{\star}j}{j}\binom{t-k-(t^{\star}+1)j}{\ell-j}(-1)^{\ell-j}p^{\ell}.$
(3.56)

Now, for brevity, let $a\equiv t-k$, and let us focus on the sum

$\sum_{j=0}^{\ell}(-1)^{\ell-j}\binom{a-t^{\star}j}{j}\binom{a-t^{\star}j-j}{\ell-j}.$
(3.57)

We start by expanding the binomial coefficients to get

$\displaystyle\binom{a-t^{\star}j}{j}\binom{a-t^{\star}j-j}{\ell-j}$
$\displaystyle=\frac{(a-t^{\star}j)!}{j!(\ell-j)!(a-t^{\star}j-\ell)!}$ (3.58)
$\displaystyle=\frac{1}{j!(\ell-j)!}\prod_{s=0}^{\ell-1}(a-t^{\star}j-s)$
(3.59)
$\displaystyle=\frac{1}{\ell!}\binom{\ell}{j}\prod_{s=0}^{\ell-1}(a-t^{\star}j-s).$
(3.60)

Next, we have

$\prod_{s=0}^{\ell-1}(a-t^{\star}j-s)=\sum_{n=0}^{\ell}(-1)^{\ell-n}\begin{bmatrix}\ell\\\
n\end{bmatrix}(a-t^{\star}j)^{n},$ (3.61)

where $\begin{bmatrix}\ell\\\ n\end{bmatrix}$ is the (unsigned) Stirling
number of the first kind222This number is defined to be the number of
permutations of $\ell$ elements with $n$ disjoint cycles.. Performing the
binomial expansion of $(a-t^{\star}j)^{n}$, the sum in (3.57) becomes

$\sum_{j=0}^{\ell}\sum_{n=0}^{\ell}\sum_{i=0}^{n}(-1)^{\ell-j}\frac{1}{\ell!}\binom{\ell}{j}\begin{bmatrix}\ell\\\
n\end{bmatrix}\binom{n}{i}(-1)^{i}(t^{\star})^{i}j^{i}a^{n-i}.$ (3.62)

Now, it holds that

$\sum_{j=0}^{\ell}(-1)^{\ell-j}\frac{1}{\ell!}\binom{\ell}{j}j^{i}=(-1)^{2\ell}\begin{Bmatrix}i\\\
\ell\end{Bmatrix},$ (3.63)

where $\begin{Bmatrix}i\\\ \ell\end{Bmatrix}$ is the Stirling number of the
second kind333This number is defined to be the number of ways to partition a
set of $i$ objects into $\ell$ non-empty subsets.. For $i<\ell$, it holds that
$\begin{Bmatrix}i\\\ \ell\end{Bmatrix}=0$, and $\begin{Bmatrix}\ell\\\
\ell\end{Bmatrix}=1$. Since $i$ ranges from 0 to $n$, and $n$ itself ranges
from 0 to $\ell$, the sum in (3.63) is zero except for when $i=\ell$. The sum
in (3.63) is therefore effectively equal to $(-1)^{2\ell}\delta_{i,\ell}$.
Substituting this into (3.62) leads to

$\sum_{n=0}^{\ell}\sum_{i=0}^{n}(-1)^{2\ell}\delta_{i,\ell}\begin{bmatrix}\ell\\\
n\end{bmatrix}\binom{n}{i}(-1)^{i}(t^{\star})^{i}a^{n-i}=(-1)^{\ell}(t^{\star})^{\ell},$
(3.64)

where we have used the fact that $\begin{bmatrix}\ell\\\ \ell\end{bmatrix}=1$.
Altogether, we have shown that

$\sum_{j=0}^{\ell}(-1)^{\ell-j}\binom{a-t^{\star}j}{j}\binom{a-t^{\star}j-j}{\ell-j}=(-1)^{\ell}(t^{\star})^{\ell}$
(3.65)

for all $\ell\geq 0$. The sum is independent of $a=t-k$. Substituting this
result into (3.56), and using the fact that

$\sum_{\ell=0}^{\infty}(-1)^{\ell}x^{\ell}=\frac{1}{1+x},\quad x\neq-1,$
(3.66)

we get

$\lim_{t\to\infty}\mathbb{E}[X(t)]=p\sum_{\ell=0}^{\infty}\sum_{k=1}^{t^{\star}+1}(-1)^{\ell}(t^{\star}p)^{\ell}=p(t^{\star}+1)\sum_{\ell=0}^{\infty}(-1)^{\ell}(t^{\star}p)^{\ell}=\frac{(t^{\star}+1)p}{1+t^{\star}p},$
(3.67)

as required. ∎

Note that if $t^{\star}=\infty$, then

$\lim_{t^{\star}\to\infty}\lim_{t\to\infty}\mathbb{E}[X(t)]=\lim_{t^{\star}\to\infty}\frac{(t^{\star}+1)p}{1+t^{\star}p}=1,$
(3.68)

which is what we expect, because if $t^{\star}=\infty$, then the link, once
established, never has to be dropped.

######  Theorem 3.2.

For any $t^{\star}<\infty$, $p\in[0,1]$, and $m\in\\{0,1,\dotsc,t^{\star}\\}$,

$\lim_{t\to\infty}\Pr[M_{t^{\star}}(t)=m,X(t)=1]=\frac{p}{1+t^{\star}p}.$
(3.69)

###### Proof.

The proof is very similar to the proof of Theorem 3.1. Using the result of
Proposition 3.2, in the limit $t\to\infty$ we have

$\lim_{t\to\infty}\Pr[M_{t^{\star}}(t)=m,X(t)=1]=\lim_{t\to\infty}\sum_{x=0}^{\infty}\binom{t-(m+1)-xt^{\star}}{x}p^{x+1}(1-p)^{t-(m+1)-x(t^{\star}+1)}.$
(3.70)

Using the binomial expansion of $(1-p)^{t-(m+1)-x(t^{\star}+1)}$, exactly as
in the proof of Theorem 3.1, we can write

$\displaystyle\lim_{t\to\infty}\Pr[M_{t^{\star}}(t)=m,X(t)=1]$
$\displaystyle=\lim_{t\to\infty}\sum_{x=0}^{\infty}\sum_{j=0}^{\infty}p\binom{t-(m+1)-xt^{\star}}{x}\binom{t-(m+1)-(t^{\star}+1)x}{j}(-1)^{j}p^{x+j}$
(3.71)
$\displaystyle=\lim_{t\to\infty}\sum_{\ell=0}^{\infty}\sum_{j=0}^{\ell}p\binom{t-(m+1)-jt^{\star}}{j}\binom{t-(m+1)-(t^{\star}+1)j}{\ell-j}(-1)^{\ell-j}p^{\ell}.$
(3.72)

Then, using (3.65), we have that

$\sum_{j=0}^{\ell}(-1)^{\ell-j}\binom{t-(m+1)-jt^{\star}}{j}\binom{t-(m+1)-(t^{\star}+1)j}{\ell-j}=(-1)^{\ell}(t^{\star})^{\ell}$
(3.73)

for all $t\geq 1$ and all $m\in\\{0,1,\dotsc,t^{\star}\\}$. Finally, using
(3.66), we obtain

$\lim_{t\to\infty}\Pr[M_{t^{\star}}(t)=m,X(t)=1]=p\sum_{\ell=0}^{\infty}(-1)^{\ell}(t^{\star}p)^{\ell}=\frac{p}{1+t^{\star}p},$
(3.74)

as required. ∎

For $t^{\star}<\infty$, the conditional probabliity
$\Pr[M_{t^{\star}}(t)=m|X(t)=1]$ in the limit $t\to\infty$ is equal to

$\displaystyle\lim_{t\to\infty}\Pr[M_{t^{\star}}(t)=m|X(t)=1]$
$\displaystyle=\lim_{t\to\infty}\frac{\Pr[M_{t^{\star}}(t)=m,X(1)=1]}{\Pr[X(t)=1]}$
(3.75)
$\displaystyle=\frac{\lim_{t\to\infty}\Pr[M_{t^{\star}}(t)=m,X(t)=1]}{\lim_{t\to\infty}\Pr[X(t)=1]}$
(3.76) $\displaystyle=\frac{1}{t^{\star}+1}.$ (3.77)

As an immediate consequence of Theorem 3.1 and Theorem 3.2, we obtain the
following:

$\displaystyle\lim_{t\to\infty}\mathbb{E}[\widetilde{F}(t;\psi)]$
$\displaystyle=\frac{p}{1+t^{\star}p}\sum_{m=0}^{t^{\star}}f_{m}(\rho_{0};\psi),\quad
t^{\star}<\infty,$ (3.78)
$\displaystyle\lim_{t\to\infty}\mathbb{E}[F(t;\psi)]$
$\displaystyle=\frac{1}{t^{\star}+1}\sum_{m=0}^{t^{\star}}f_{m}(\rho_{0};\psi),\quad
t^{\star}<\infty.$ (3.79)

For the expected quantum state, we obtain

$\displaystyle\lim_{t\to\infty}\sigma(t)$
$\displaystyle=\frac{1-p}{1+t^{\star}p}\tau^{\varnothing}+\frac{p}{1+t^{\star}p}\sum_{m=0}^{t^{\star}}\rho(m),\quad
t^{\star}<\infty,$ (3.80) $\displaystyle\lim_{t\to\infty}\sigma(t|X(t)=1)$
$\displaystyle=\frac{1}{t^{\star}+1}\sum_{m=0}^{t^{\star}}\rho(m),\quad
t^{\star}<\infty.$ (3.81)

Let us also determine the probabilities $\Pr[M_{t^{\star}}(t)=m,X(t)=0]$ for
finite $t^{\star}$. Observe that this probability is non-zero only when
$M_{t^{\star}}(t)=t^{\star}$. This is due to the fact that we can have
$X(t)=0$ in only one of two possible ways: either there are some full blocks
of ones of length $t^{\star}+1$ before time $t$, or there are no full blocks
of ones before time $t$. In both cases, the value of the memory can only be
equal to $t^{\star}$. We thus obtain the following.

######  Proposition 3.3.

For any $t\geq 1$, $t^{\star}<\infty$, $p\in[0,1]$, and
$m\in\\{0,1,\dotsc,t^{\star}\\}$,

$\Pr[M_{t^{\star}}(t)=m,X(t)=0]=\left\\{\begin{array}[]{l
l}\delta_{m,t^{\star}}(1-p)^{t},\quad t\leq t^{\star}+1,\\\\[14.22636pt]
\displaystyle\delta_{m,t^{\star}}\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\binom{t-1-xt^{\star}}{x}p^{x}(1-p)^{t-(t^{\star}+1)x},\quad
t>t^{\star}+1.\end{array}\right.$ (3.82)

For $t^{\star}=\infty$,

$\Pr[M_{\infty}(t)=m,X(t)=0]=\delta_{m,-1}(1-p)^{t}$ (3.83)

for all $m\in\\{-1,0,1,\dotsc,t-1\\}$.

###### Proof.

For finite $t^{\star}$, when $t\leq t^{\star}+1$, there is only one link value
sequence ending with a zero, and that is the sequence consisting of all zeros,
which has probability $(1-p)^{t}$. Furthermore, since the value of the memory
for this sequence is equal to $t^{\star}$, only the case
$M_{t^{\star}}(t)=t^{\star}$ has non-zero probability. When $t>t^{\star}+1$,
we can again have non-zero probability only for $M_{t^{\star}}(t)=t^{\star}$.
In this case, because every link value sequence has to end with a zero, we
must have $Y_{2}(t)=0$. Therefore, using (3.26), along with (3.30), we obtain
the desired result.

For $t^{\star}=\infty$, only the link value sequence consisting of all zeros
ends with a zero, and in this case we have $M_{\infty}(t)=-1$. The result then
follows. ∎

By following arguments very similar to the proof of Theorem 3.2, we arrive at
the following infinite-horizon expression for $\Pr[M_{t^{\star}}(t)=m,X(t)=0]$
when $t^{\star}<\infty$:

$\lim_{t\to\infty}\Pr[M(t)=m,X(t)=0]=\delta_{m,t^{\star}}\frac{1-p}{1+t^{\star}p},\quad
m\in\\{0,1,\dotsc,t^{\star}\\}.$ (3.84)

Finally, let us consider the expected success rate $\mathbb{E}[S(t)]$. Letting
$N^{\max}=1$, recall that

$S(t)=\frac{\sum_{j=1}^{t}A(j-1)X(j)}{\sum_{j=1}^{t}A(j-1)}.$ (3.85)

The success rate is simply the ratio of the number of successful requests up
to time $t$ to the total number of requests up to time $t$.

######  Proposition 3.4.

For any $t^{\star}\geq 0$, any $t\geq 1$, and any $p\in[0,1]$,

$\mathbb{E}[S(t)]=\sum_{j=0}^{t-1}\frac{1}{j+1}p(1-p)^{j},\quad t\leq
t^{\star}+1.$ (3.86)

For $t>t^{\star}+1$,

$\mathbb{E}[S(t)]=\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\left(\frac{x}{t-t^{\star}x}\binom{t-1-xt^{\star}}{x}p^{x}(1-p)^{t-(t^{\star}+1)x}\right.\\\
\left.+\sum_{k=1}^{t^{\star}+1}\frac{x+1}{t-k-t^{\star}x+1}\binom{t-k-
xt^{\star}}{x}p^{x+1}(1-p)^{t-k-(t^{\star}+1)x}\boldsymbol{1}_{t-k-(t^{\star}+1)x\geq
0}\right).$ (3.87)

###### Proof.

We start with the observation that, for any history $h^{t}$, the number of
successful requests can be written in terms of the number $Y_{1}(t)(h^{t})$ of
blocks of ones of length $t^{\star}+1$ and the number $Y_{2}(t)(h^{t})$ of
trailing ones in the link value sequence corresponding to $h^{t}$ as

$Y_{1}(t)(h^{t})+1-\delta_{Y_{2}(t)(h^{t}),0}.$ (3.88)

Similarly, the total number of failed requests is

$t-Y_{2}(t)(h^{t})-(t^{\star}+1)Y_{1}(t)(h^{t}).$ (3.89)

Therefore,

$\displaystyle S(t)(h^{t})$
$\displaystyle=\frac{Y_{1}(t)(h^{t})+1-\delta_{Y_{2}(t)(h^{t}),0}}{t-Y_{2}(t)(h^{t})-(t^{\star}+1)Y_{1}(t)(h^{t})+Y_{1}(t)(h^{t})+1-\delta_{Y_{2}(t)(h^{t}),0}}$
(3.90)
$\displaystyle=\frac{Y_{1}(t)(h^{t})+1-\delta_{Y_{2}(t)(h^{t}),0}}{t-Y_{2}(t)(h^{t})-t^{\star}Y_{1}(t)(h^{t})+1-\delta_{Y_{2}(t)(h^{t}),0}}.$
(3.91)

Now, for $t\leq t^{\star}+1$, we always have $Y_{1}(t)(h^{t})=0$ for all
histories $h^{t}$, and the link value sequence can consist only of a positive
number of trailing ones not exceeding $t$. Thus, from Proposition 3.1, the
probability of any such history is $p(1-p)^{t-Y_{2}(t)(h^{t})}$. Using (3.91)
then leads to

$\mathbb{E}[S(t)]=\sum_{h^{t}}S(t)(h^{t})\Pr[H(t)=h^{t}]=\sum_{k=1}^{t}\frac{1}{t-k+1}p(1-p)^{t-k}=\sum_{j=0}^{t-1}\frac{1}{j+1}p(1-p)^{j}$
(3.92)

for $t\leq t^{\star}+1$, as required, where the last equality follows by a
change of summation variable.

For $t>t^{\star}+1$, we use (3.91) again, keeping in mind this time that the
number of trailing ones can be equal to zero, to get

$\displaystyle\mathbb{E}[S(t)]$
$\displaystyle=\sum_{h^{t}}S(t)(h^{t})\Pr[H(t)=h^{t}]$ (3.93)
$\displaystyle=\sum_{h^{t}:Y_{2}(t)(h^{t})=0}S(t)(h^{t})\Pr[H(t)=h^{t}]+\sum_{h^{t}:Y_{2}(t)(h^{t})\geq
1}S(t)(h^{t})\Pr[H(t)=h^{t}]$ (3.94)
$\displaystyle=\sum_{x=0}^{\lfloor\frac{t-1}{t^{\star}+1}\rfloor}\left(\frac{x}{t-t^{\star}x}\Pr[H(t)=h^{t}:Y_{1}(t)(h^{t})=x,Y_{2}(t)(h^{t})=0]\right.$
$\displaystyle\qquad\qquad\qquad\left.+\sum_{k=1}^{t^{\star}+1}\frac{x+1}{t-k-t^{\star}x+1}\Pr[H(t)=h^{t}:Y_{1}(t)(h^{t})=x,Y_{2}(t)(h^{t})=k]\right).$
(3.95)

Using Proposition 3.1, we arrive at the desired result. ∎

Figure 6: The expected success rate, as given by the expressions in
Proposition 3.4, for an elementary link with $p=0.3$ and various cutoffs.

See Figure 6 for a plot of the expected rate $\mathbb{E}[S(t)]$ as a function
of time for various values of the cutoff. We find that the rate has
essentially the shape of a decaying square wave, which is clearer for larger
values of the cutoff. In particular, the “plateaus” in the curves have a
period of $t^{\star}+1$ time steps. Let us now consider the values of these
pleateaus. The largest plateau can be found by considering the case
$t^{\star}=\infty$, because in this case the condition $t\leq t^{\star}+1$ is
satisfied for all $t\geq 1$, and it is when this condition is true that the
largest plateau occurs. Using Proposition 3.4 with $t^{\star}=\infty$, we find
that the value of the largest plateau approaches

$\lim_{t\to\infty}\mathbb{E}[S(t)]=\lim_{t\to\infty}\sum_{j=0}^{t-1}\frac{1}{j+1}p(1-p)^{j}=-\frac{p\ln
p}{1-p},\quad t^{\star}=\infty,$ (3.96)

for all $p\in(0,1)$. In the case $t^{\star}<\infty$, as we see in Figure 6,
there are multiple plateaus, with each plateau lasting for a period of
$t^{\star}+1$ time steps, as mentioned earlier. The values of these pleateaus
depend on the number $x\geq 0$ of full blocks of ones in the link value
sequence. Specifically, the values of the plateaus approach

$\lim_{t\to\infty}\sum_{k=1}^{t-(t^{\star}+1)x}\frac{x+1}{t-k-t^{\star}x+1}\binom{t-k-t^{\star}x}{x}p^{x+1}(1-p)^{t-k-(t^{\star}+1)x}\\\
=\lim_{t\to\infty}\sum_{j=(t^{\star}+1)x}^{t-1}\frac{x+1}{j-t^{\star}x+1}\binom{j-t^{\star}x}{x}p^{x+1}(1-p)^{j-(t^{\star}+1)x}=p\cdot{~{}}_{2}F_{1}(1,1,2+x,1-p),$
(3.97)

for all $x\geq 0$, where ${}_{2}F_{1}(a,b,c,z)$ is the hypergeometric
function. Then, using the fact that
$\lim_{x\to\infty}{~{}}_{2}F_{1}(1,1,2+x,1-p)=1$ [149], we conclude that the
plateaus approach the value of $p$, i.e.,

$\lim_{t\to\infty}\mathbb{E}[S(t)]=p,\quad t^{\star}<\infty.$ (3.98)

###  3.2 Waiting time

Let us now consider the waiting time for an elementary link. The waiting time
is defined to be the number of time steps needed to establish a link from the
time that a link is requested. We focus here on just one elementary link.
Detailed analyses of the waiting time for a chain of bipartite links have been
conducted in [34, 150, 102, 120].

It is well known for the model being considered here that the waiting time,
which we denote by $W$, is a geometric random variable, so that
$\Pr[W=t]=p(1-p)^{t-1}$, where $p$ is the success probability of the link. The
expected waiting time is then $\mathbb{E}[W]=\frac{1}{p}$. We can confirm this
using the formalism developed in this work by noting that the waiting time
probability distribution is given simply by the probability that it takes $t$
time steps to establish the link, starting from $t=1$:

$\Pr[W=t]=\Pr[X(1)=0,X(2)=0,\dotsc,X(t)=1].$ (3.99)

Using the result of Proposition 3.1, we immediately obtain
$\Pr[W=t]=p(1-p)^{t-1}$, from which the expected waiting time is
$\mathbb{E}[W]=\sum_{t=1}^{\infty}tp(1-p)^{t-1}=\frac{1}{p}$, as expected.
Note that this result holds regardless of the value of $t^{\star}$, and it
assumes that the initial request for entanglement is made at time $t=0$.

Let us now consider a scenario in which the elementary link generation process
is persistent, even if no end-user request is made. In other words, we
consider an “always-on”/continuous link generation procedure that is ready to
go whenever end-user entanglement is requested, rather than have the entire
process begin only when end-user entanglement is requested. Then, if an end-
user request for entanglement occurs at time $t_{\text{req}}\geq 0$, then the
waiting time random variable $W(t_{\text{req}})$ has probability distribution

$\Pr[W(t_{\text{req}})=t]=\Pr[X(t_{\text{req}}+1)=0,X(t_{\text{req}}+2)=0,\dotsc,X(t_{\text{req}}+t)=1]$
(3.100)

for all $t\geq 1$. In other words, the waiting time is given by the amount of
time it takes to establish the link after the end-user request is made. Note
that $W=W(0)$. With non-zero memory cutoff and $t_{\text{req}}>0$, we can
obtain a lower expected waiting time than $\frac{1}{p}$, which we now show.

######  Proposition 3.5.

For any $t^{\star}<\infty$, for any $t_{\text{req}}\geq 0$, and for any
$p\in(0,1)$,

$\mathbb{E}[W(t_{\text{req}})]=\frac{\Pr[M_{t^{\star}}(t_{\text{req}}+1)=t^{\star},X(t_{\text{req}}+1)=0]}{p(1-p)}.$
(3.101)

For $t^{\star}=\infty$,

$\mathbb{E}[W(t_{\text{req}})]=\frac{\Pr[X(t_{\text{req}}+1)=0]}{p(1-p)}=\frac{(1-p)^{t_{\text{req}}}}{p}.$
(3.102)

######  Remark 3.2.

As a check, let us first observe the following:

  * •

If $t_{\text{req}}=0$, then since $\Pr[M_{t^{\star}}(1)=t^{\star},X(1)=0]=1-p$
for all $t^{\star}<\infty$ (see Proposition 3.3), we obtain
$\mathbb{E}[W(0)]=\frac{1}{p}$, as expected. We get the same result for
$t^{\star}=\infty$.

  * •

If $t^{\star}=0$, then we get
$\Pr[M_{t^{\star}}(t_{\text{req}}+1)=0,X(t_{\text{req}}+1)=0]=1-p$ for all
$t_{\text{req}}\geq 0$ (see Proposition 3.3), which means that
$\mathbb{E}[W(t_{\text{req}})]=\frac{1}{p}$ for all $t_{\text{req}}\geq 0$.
This makes sense, because in the $t^{\star}=0$ policy the link is never held
in memory. $\blacktriangleleft$

###### Proof of Proposition 3.5.

Using (3.100), we have

$\displaystyle\Pr[W(t_{\text{req}})=t]$
$\displaystyle\quad=\Pr[X(t_{\text{req}}+1)=0,\dotsc,X(t_{\text{req}}+t)=1]$
(3.103)
$\displaystyle\quad=\sum_{m_{1},\dotsc,m_{t}=0}^{t^{\star}}\Pr[X(t_{\text{req}}+1)=0,M_{t^{\star}}(t_{\text{req}}+1)=m_{1},\dotsc,X(t_{\text{req}}+t)=1,M_{t^{\star}}(t_{\text{req}}+t)=m_{t}].$
(3.104)

Using the transition matrix $T(t^{\star})$ defined in (3.13)–(3.19), we obtain

$\Pr[W(t_{\text{req}})=t]\\\
=\sum_{m_{1},\dotsc,m_{t}=0}^{t^{\star}}(T(t^{\star}))_{\begin{subarray}{c}1,m_{t}\\\
0,m_{t-1}\end{subarray}}\dotsb(T(t^{\star}))_{\begin{subarray}{c}0,m_{3}\\\
0,m_{2}\end{subarray}}(T(t^{\star}))_{\begin{subarray}{c}0,m_{2}\\\
0,m_{1}\end{subarray}}\Pr[M_{t^{\star}}(t_{\text{req}}+1)=m_{1},X(t_{\text{req}}+1)=0].$
(3.105)

Using (3.82), along with (3.13)–(3.19), we have that

$\Pr[W(t_{\text{req}})=t]=\Pr[M_{t^{\star}}(t_{\text{req}}+1)=t^{\star},X(t_{\text{req}}+1)=0]p(1-p)^{t-2},$
(3.106)

for all $t\geq 1$. The result then follows.

For $t^{\star}=\infty$, using the transition matrix $T(\infty)$ defined in
(3.25) leads to

$\Pr[X(t_{\text{req}}+1)=0,\dotsc,X(t_{\text{req}}+t)=1]\\\
=(T(\infty))_{\begin{subarray}{c}1\\\
0\end{subarray}}(T(\infty))_{\begin{subarray}{c}0\\\
0\end{subarray}}\dotsb(T(\infty))_{\begin{subarray}{c}0\\\
0\end{subarray}}\Pr[X(t_{\text{req}}+1)=0].$ (3.107)

Then, from (3.42), we have that
$\Pr[X(t_{\text{req}}+1)=0]=(1-p)^{t_{\text{req}}+1}$, so that

$\Pr[W(t_{\text{req}})=t]=p(1-p)^{t-2}(1-p)^{t_{\text{req}}+1}$ (3.108)

for all $t\geq 1$. The result then follows. ∎

Figure 7: The expected waiting time for a single elementary link, given by
(3.101), as a function of the request time $t_{\text{req}}$. We let $p=0.3$,
and we take various values for the cutoff $t^{\star}$.

In the limit $t_{\text{req}}\to\infty$, we obtain using (3.84),

$\lim_{t_{\text{req}}\to\infty}\mathbb{E}[W(t_{\text{req}})]=\frac{1}{p(1+t^{\star}p)},\quad
t^{\star}<\infty.$ (3.109)

See Figure 7 for plots of the expected waiting time, given by (3.101), as a
function of the request time $t_{\text{req}}$ for various values of
$t^{\star}$. As long as $t^{\star}$ is strictly greater than zero, the waiting
time is strictly less than $\frac{1}{p}$, despite the oscillatory behavior for
small values of $t_{\text{req}}$. In the limit $t_{\text{req}}\to\infty$, we
see that the waiting time is monotonically decreasing with increasing
$t^{\star}$, which is also apparent from (3.109).

###  3.3 Multiple parallel links

So far, we have considered only one edge connecting a particular set of nodes
corresponding to an elementary link in a network. Suppose now that those nodes
have $N^{\max}>1$ parallel edges connecting them (see Figure 1). Therefore, at
each time step, the set of nodes can have at most $N^{\max}$ active parallel
links. In this scenario, as described in the Introduction, the network is
described by a multigraph, since each parallel link corresponds to a distinct
edge connecting the nodes. All of these parallel links are mutually
independent by definition. Therefore, if $E$ is a subset of edges in a graph
corresponding to a quantum network, then we can write the classical-quantum
state of an edge $e\in E$ at time $t$ as
$\bigotimes_{j=1}^{N_{e}^{\max}}\widehat{\sigma}_{e,j}(t)$ for all $t\geq 1$,
where each $\widehat{\sigma}_{e,j}(t)$ is given by (2.27) and $N_{e}^{\max}$
is the maximum number of parallel links in the edge $e\in E$. By tracing out
the classical history registers of each parallel link, we obtain the overall
expected quantum state of an edge $e\in E$ at time $t$ as follows:

$\bigotimes_{j=1}^{N_{e}^{\max}}\sigma_{e,j}(t),$ (3.110)

where each $\sigma_{e,j}(t)$ is given by the expression in (3.50). In the
limit $t\to\infty$, we use the expression in (3.80) to obtain

$\bigotimes_{j=1}^{N_{e}^{\max}}\left(\frac{1-p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}\tau_{e,j}^{\varnothing}+\frac{p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}\sum_{m=0}^{t_{e,j}^{\star}}\rho_{e,j}(m)\right)\quad(t\to\infty),$
(3.111)

where $\\{p_{e,j}\\}_{j=1}^{N_{e}^{\max}}$ and
$\\{t_{e,j}^{\star}\\}_{j=1}^{N_{e}^{\max}}$ are the success probabilities and
cutoffs of the parallel links (all finite) for the edge $e\in E$.

Using the joint state of the parallel links in (3.110), it is possible to
apply an entanglement distillation protocol in order to increase the fidelity
of the link, which is important for achieving a high-fidelity long-distance
entangled state. See [26, 27, 28] for examples of bipartite entanglement
distillation protocols, and [151, 152, 153, 154, 155, 156] for examples of
multipartite entanglement distillation protocols. (See also [157, 158, 159,
160, 161, 162, 163, 164, 165, 166].) Upper bounds on the fidelity that can be
achieved after an entanglement distillation protocol, in the non-asymptotic
setting, can be calculated using a semi-definite program (SDP), as shown in
[167]. For practical entanglement distillation schemes, which typically only
consist of one round of local operations and classical communication and also
have non-unit success probability, SDP upper bounds have been provided in
[165]. In [126], the authors use reinforcement learning to discover protocols
for entanglement distillation. See [25, 121, 122, 104] for an analysis of
quantum repeater protocols with entanglement distillation.

Using the expressions in (3.110) and (3.111), along with the fact that the
elementary link generation for each edge in the set $E$ is indepdendent of the
other edges, we can write the overall expected quantum state corresponding to
the set $E$ of edges as follows:

$\sigma_{E}(t)\coloneqq\bigotimes_{e\in
E}\bigotimes_{j=1}^{N_{e}^{\max}}\sigma_{e,j}(t)$ (3.112)

When all of the cutoffs are finite, in the limit $t\to\infty$, we get

$\lim_{t\to\infty}\sigma_{E}(t)=\bigotimes_{e\in
E}\bigotimes_{j=1}^{N_{e}^{\max}}\left(\frac{1-p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}\tau_{e,j}^{\varnothing}+\frac{p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}\sum_{m=0}^{t_{e,j}^{\star}}\rho_{e,j}(m)\right).$
(3.113)

With multiple parallel links in an edge $e\in E$, the probability of having at
least one active parallel link at time $t$ is

$\Pr[N_{e}(t)\geq 1]=1-\prod_{j=1}^{N_{e}^{\max}}(1-\Pr[X_{e,j}(t)=1]),$
(3.114)

where $X_{e,j}(t)$ is the link random variable for the $j^{\text{th}}$
parallel link. In the limit $t\to\infty$, using (3.52), this probability
becomes

$\lim_{t\to\infty}\Pr[N_{e}(t)\geq
1]=1-\prod_{j=1}^{N_{e}^{\max}}\frac{1-p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}.$
(3.115)

We can also determine the expected number of active parallel links at any
given time. Recalling that $N_{e}(t)=\sum_{j=1}^{N_{e}^{\max}}X_{e,j}(t)$ is
the random variable for the total number of parallel links at time $t\geq 1$,
we find that the expected number of parallel links is simply
$\sum_{j=1}^{N_{e}^{\max}}\mathbb{E}[X_{e,j}(t)]$, with
$\mathbb{E}[X_{e,j}(t)]$ given by (3.42) for each parallel link. In the limit
$t\to\infty$, the expected number of parallel links becomes

$\lim_{t\to\infty}\mathbb{E}[N_{e}(t)]=\sum_{j=1}^{N_{e}^{\max}}\frac{(t_{e,j}^{\star}+1)p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}.$
(3.116)

If all of the parallel links have the same success probability $p_{e}$ and the
same cutoff $t_{e}^{\star}$, then this reduces to

$\lim_{t\to\infty}\mathbb{E}[N_{e}(t)]=N_{e}^{\max}\frac{(t_{e}^{\star}+1)p_{e}}{1+t_{e}^{\star}p_{e}}$
(3.117)

parallel links on average in the $t\to\infty$ limit. Note that if all of the
parallel links have the same memory cutoff and the same success probability,
then $N_{e}(t)$ is simply a binomial random variable with parameter
$\Pr[X_{e}(t)=1]$; otherwise, $N_{e}(t)$ is a Poisson-binomial random variable
(see, e.g., [168]). Also, as mentioned in Remark 2.4, the quantity
$N_{e}^{\max}$ can be thought of as an edge capacity, because it is the
maximum number of entangled states that can be shared along an edge per unit
time. Then, $N_{e}(t)$ can be thought of as the edge flow, and
$\mathbb{E}[N_{e}(t)]$ the expected edge flow. In the case of bipartite links,
Menger’s theorem [169, 170] tells us that we can use the expected flow to
determine at any time step the expected number of edge-disjoint paths between
two given nodes in the network, which then gives us the number of entangled
states that they can share; see, e.g., [74]. In the case of multipartite
links, the expected edge flow can be used to determine the expected number of
edge-disjoint Steiner/spanning trees [171, 172, 173] for a given set of nodes
in the network in order to determine the number of multipartite entangled
states that they can share; see, e.g., [75, 78, 174].

Let us now consider the rate $R(t)$ for any edge under the memory cutoff
policy in the $t\to\infty$ limit. First, recall that

$R(t)=\frac{1}{t}\sum_{j=1}^{t}N(j)$ (3.118)

is the average number of active parallel links in an edge per unit time in $t$
time steps.

######  Theorem 3.3.

For any elementary link consisting of $N^{\max}$ parallel links, with
$\\{p_{j}\\}_{j=1}^{N^{\max}}$ being the success probabilities for the
parallel links and $\\{t_{j}^{\star}\\}_{j=1}^{N^{\max}}$ the memory cutoffs
for the parallel links, the expected rate $\mathbb{E}[R(t)]$ of elementary
link generation in the limit $t\to\infty$ is as follows:

$\lim_{t\to\infty}\mathbb{E}[R(t)]=\lim_{t\to\infty}\frac{1}{t}\sum_{j=1}^{t}\mathbb{E}[N(j)]=\sum_{j=1}^{N^{\max}}\frac{(t_{j}^{\star}+1)p_{j}}{1+t_{j}^{\star}p_{j}}.$
(3.119)

###### Proof.

The expected rate $\mathbb{E}[R(t)]$ is, by defintion, the Cesáro mean of the
sequence $(\mathbb{E}[N(j)])_{j=1}^{t}$ (see, e.g., [175]). Then, because
$\lim_{j\to\infty}\mathbb{E}[N(j)]$ exists and is given by (3.116), we use the
well-known result that the limit of Cesáro means is equal to the limit of the
original sequence [175], leading to the desired result. ∎

###  3.4 Total number of active links

Consider a subset $E$ of edges in a graph corresponding to a quantum network.
Then, for any time $t\geq 1$, the number of active links in the set $E$ is

$L_{E}(t)\coloneqq\sum_{e\in E}\sum_{j=1}^{N_{e}^{\max}}X_{e,j}(t),$ (3.120)

where $X_{e,j}(t)$ is the link status random variable for the $j^{\text{th}}$
parallel link of the edge $e\in E$. When only the number of edges/elementary
links is relevant, we use the notation $L_{M}(t)$ to refer to the number of
active links at time $t$, where $M=|E|$ is the number of edges/elementary
links under consideration.

The total number of active elementary links was introduced in [103] as a
figure of merit on the performance of an entanglement distribution network,
and it was shown that the quantity provides an upper bound on the average
largest cluster size (i.e., the size of the largest connected component) in
the network. In particular, for the case that all of the elementary links have
the same success probability $p$ and $N_{e}^{\max}=1$ for all $e\in E$, with
$M=|E|$, it was shown that $\frac{1}{M}\mathbb{E}[L_{M}(t)]\leq 1-(1-p)^{t}$
for all $t\geq 1$.

Figure 8: The expected total number $\mathbb{E}[L_{M}(t)]$ of active
elementary links when $M$ edges in total are being considered. We use the
notation
$\mathbb{E}[L_{M}(\infty)]\equiv\lim_{t\to\infty}\mathbb{E}[L_{M}(t)]$. (Left)
$M=2$ edges in the limit $t\to\infty$ with $N^{\max}=1$ parallel link for each
edge. One link has success probability $p_{1}$ and cutoff $t_{1}^{\star}=5$,
and the other link has success probability $p_{2}$ and cutoff
$t_{2}^{\star}=2$. (Right) $M=4$ edges after $t=50$ time steps, with
$N^{\max}=1$ parallel link for each edge. Two of the links have success
probability $p_{1}$ with cutoffs $5,15$, and the other two links have success
probability $p_{2}$ with cutoffs $10,20$.

Using the results of Section 3.1, we can now extend the result of [103]. In
particular,

$\mathbb{E}[L_{E}(t)]=\sum_{e\in
E}\sum_{j=1}^{N_{e}^{\max}}\mathbb{E}[X_{e,j}(t)],$ (3.121)

with $\mathbb{E}[X_{e,j}(t)]$ given by the expression in (3.42), i.e.,

$\Pr[X_{e,j}(t)=1]\\\ =\left\\{\begin{array}[]{l l}1-(1-p_{e,j})^{t},&t\leq
t_{e,j}^{\star}+1,\\\\[14.22636pt]
\displaystyle\sum_{x=0}^{\lfloor\frac{t-1}{t_{e,j}^{\star}+1}\rfloor}\sum_{k=1}^{t_{e,j}^{\star}+1}\binom{t-k-
xt_{e,j}^{\star}}{x}\boldsymbol{1}_{t-k-x(t_{e,j}^{\star}+1)\geq
0}p_{e,j}^{x+1}(1-p_{e,j})^{t-k-(t_{e,j}^{\star}+1)x},&t>t_{e,j}^{\star}+1\end{array}\right.$
(3.122)

where $\\{p_{e,j}:e\in E,1\leq j\leq N_{e}^{\max}\\}$ is the set of success
probabilities and $\\{t_{e,j}^{\star}:e\in E,1\leq j\leq N_{e}^{\max}\\}$ is
the set of cutoffs. In the $t\to\infty$ limit, this reduces to the following
simple expression using Theorem 3.1:

$\lim_{t\to\infty}\mathbb{E}[L_{E}(t)]=\sum_{e\in
E}\sum_{j=1}^{N_{e}^{\max}}\frac{(t_{e,j}^{\star}+1)p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}.$
(3.123)

See Figure 8 for plots of $\mathbb{E}[L_{M}(t)]$. Given a subset of elementary
links with given memory cutoffs, we can estimate the success probabilities
that need to be attained in order to achieve a desired expected number of
active elementary links after a given amount of time.

###  3.5 Collective link status

Consider a subset $E$ of edges in a graph corresponding to a quantum network.
Then, in the case that each edge has only one parallel edge, for any time
$t\geq 1$ we define the collective link status $X_{E}^{\text{tot}}$ to be

$X_{E}^{\text{tot}}(t)\coloneqq\prod_{e\in E}X_{e}(t)$ (3.124)

When only the number of edges/elementary links is relevant, we use the
notation $X_{M}^{\text{tot}}(t)$ to refer to the collective link status at
time $t$, where $M=|E|$ is the number of edges/elementary links under
consideration. Note that the collective link status is equal to one if and
only if all of the links are active at the given time. In other words,

$\Pr[X_{E}^{\text{tot}}(t)=1]=\mathbb{E}[X_{E}^{\text{tot}}(t)]=\prod_{e\in
E}\Pr[X_{e}(t)=1].$ (3.125)

In the limit $t\to\infty$,

$\lim_{t\to\infty}\mathbb{E}[X_{E}(t)]=\prod_{e\in
E}\frac{(t_{e}^{\star}+1)p_{e}}{1+t_{e}^{\star}p_{e}},$ (3.126)

where $\\{p_{e}\\}_{e\in E}$ and $\\{t_{e}^{\star}\\}_{e\in E}$ are the
success probabilities and cutoffs, respectively, of the links. The collective
link status can be used to estimate the probability of having a long-distance
entangled link between a collection of non-adjacent nodes that are connected
to each other along a path given by the subset $E$ of edges.

Figure 9: The expected collective link status
$\mathbb{E}[X_{M}^{\text{tot}}(t)]$ of a collection of $M$ edges. We use the
notation
$X_{M}^{\text{tot}}(\infty)\equiv\lim_{t\to\infty}\mathbb{E}[X_{M}^{\text{tot}}(t)]$.
(Left) $M=2$ edges in the limit $t\to\infty$ with $N^{\max}=1$ parallel link
for each edge. One link has success probability $p_{1}$ and cutoff
$t_{1}^{\star}=5$, and the other link has success probability $p_{2}$ and
cutoff $t_{2}^{\star}=2$. (Right) $M=4$ edges after $t=50$ time steps, with
$N^{\max}=1$ parallel link for each edge. Two of the links have success
probability $p_{1}$ with cutoffs $5,15$, and the other two links have success
probability $p_{2}$ with cutoffs $10,20$.

In general, if each edge $e\in E$ has a number $N_{e}^{\max}\geq 1$ of
parallel edges, then the probability that all corresponding elementary links
have at least one active parallel link at time $t\geq 1$ is given by

$\prod_{e\in E}\Pr[N_{e}(t)\geq 1]=\prod_{e\in
E}\left(1-\prod_{j=1}^{N_{e}^{\max}}(1-\Pr[X_{e,j}(t)=1])\right).$ (3.127)

In the limit $t\to\infty$, this becomes

$\prod_{e\in
E}\left(1-\prod_{j=1}^{N_{e}^{\max}}\frac{1-p_{e,j}}{1+t_{e,j}^{\star}p_{e,j}}\right).$
(3.128)

See Figure 9 for plots of $\mathbb{E}[X_{M}^{\text{tot}}]$. Given a subset of
elementary links with given memory cutoffs, we can estimate the success
probabilities that need to be attained in order to achieve a desired expected
collective link status after a given amount of time.

##  4 Finite-horizon policy optimization

Having analyzed the memory cutoff policy, let us now turn to obtaining optimal
policies. We stick to the finite-horizon case, meaning that the final time for
the link evolution is fixed at the outset and is finite, and the task is to
optimize the expected total reward up to the final time. In Theorem 4.1 below,
we show that policy optimization can be done using dynamic programming.

Recall from Section 2.1 that a policy is of the form
$\pi=(d_{1},d_{2},\dotsc)$, where the $d_{j}$ are decision functions, which in
general give conditional probability distributions over actions conditioned on
histories. Also, to each element of the policy $\pi$, recall from (2.23) that
we can associate the following density operator:

$\pi(j;h^{j})=\sum_{a=0}^{1}d_{j}(h^{j})(a)|a\rangle\langle a|,\quad j\geq
1,~{}h^{j}\in\\{0,1\\}^{2j-1}.$ (4.1)

Then, we can write the operator $\widetilde{\sigma}(t;h^{t})$ in (2.28) for
any $t\geq 1$ and any history $h^{t}=(x_{1},a_{1},x_{2},\allowbreak
a_{2},\dotsc,a_{t-1},x_{t})$ as follows:

$\displaystyle\widetilde{\sigma}(t;h^{t})$
$\displaystyle=\left(\prod_{j=1}^{t-1}\operatorname{Tr}[\pi(j;h_{j}^{t})|a_{j}\rangle\langle
a_{j}|]\right)(\mathcal{T}^{x_{t-1},a_{t-1},x_{t}}\circ\dotsb\circ\mathcal{T}^{x_{1},a_{1},x_{2}})(\widetilde{\sigma}(1;x_{1}))$
(4.2)
$\displaystyle=\left(\prod_{j=1}^{t-1}\operatorname{Tr}[\pi(j;h_{j}^{t})|a_{j}\rangle\langle
a_{j}|]\right)\widetilde{\sigma}^{\prime}(t;h^{t}),$ (4.3)

where

$\widetilde{\sigma}^{\prime}(t;h^{t})\coloneqq(\mathcal{T}^{x_{t-1},a_{t-1},x_{t}}\circ\dotsb\circ\mathcal{T}^{x_{1},a_{1},x_{2}})(\widetilde{\sigma}(1;x_{1})).$
(4.4)

Policy optimization is then the task of optimizing the reward up to a given
time $t$ with respect to the density operators $\\{\pi(j;h^{j})$: $1\leq j\leq
t-1,~{}h^{j}\in\\{0,1\\}^{2j-1}\\}$ that define a policy.

Now, before getting to Theorem 4.1, let us consider how policies for
elementary link generation should be evaluated. From Definition 2.1, Remark
2.1, and Theorem 2.2, we have that the quantity $\mathbb{E}[\widetilde{F}(t)]$
represents the expected total reward in the decision process corresponding to
elementary link generation. The objective function when optimizing over
policies would thus be the quantity $\mathbb{E}[\widetilde{F}(t)]$. Using this
quantity makes sense from the perspective of elementary link generation in a
quantum network, because with higher elementary link fidelities more joining
measurements can be performed in order to obtain high-fidelity entanglement
distribution over longer distances without having to perform entanglement
distillation. Another way to justify using $\mathbb{E}[\widetilde{F}(t)]$ as
the objective function is by considering two alternatives.

The first alternative to $\mathbb{E}[\widetilde{F}(t)]$ is the expected link
value $\mathbb{E}[X(t)]$. If we use $\mathbb{E}[X(t)]$ as the objective
function for policy optimization, then it is clear that the policy consisting
of the action “request” at every time step before the link is established, and
the action “wait” at every time step after the link is established, is
optimal, in the sense that it achieves the highest value of $\mathbb{E}[X(t)]$
for all $t\geq 1$. (Observe that this policy is simply the $t^{\star}=\infty$
memory cutoff policy.) A higher value of $\mathbb{E}[X(t)]$ comes, of course,
at the cost of a lower fidelity, since each “wait” action decreases the
fidelity of the quantum state stored in memory. If instead we consider
maximizing the expected fidelity $\mathbb{E}[F(t)]$ of the link given that the
link is active, then it is clear that the action “request” at each time step
is optimal, because then the quantity $\mathbb{E}[F(t)]$ is equal to the
initial fidelity $f_{0}$ at all time steps, which is the highest that can be
obtained (without entanglement distillation). (Observe that this policy is
simply the $t^{\star}=0$ memory cutoff policy.) This highest value of the
fidelity comes at the cost of a lower expected link value, since the
probability that the link is active stays at $p$ for all times under this
policy, i.e., $\Pr[X(t)=1]=p$ for all $t\geq 1$ if at every time step the
agent requests a link. The quantity
$\mathbb{E}[\widetilde{F}(t)]=\mathbb{E}[X(t)f_{M(t)}(\rho_{0})]$ by
definition incorporates the trade-off between the link value and the link
fidelity, and therefore it is a better figure of merit for elementary link
generation.

Having justified the use of $\mathbb{E}[\widetilde{F}(t)]$ as the objective
function for policy optimization, let us discuss one simple policy
optimization strategy, which is intuitive but not necessarily optimal, before
getting to our main result in Theorem 4.1. Since the agent, at each time step,
has to decide whether to keep the current link or to discard it and request a
new one, a simple policy is for the agent to deterministically pick the action
$a_{t}$ at time $t$ that maximizes the quantity
$\mathbb{E}[\widetilde{F}(t+1)]$ at the next time step. Recalling that the