\section{Introduction}\label{sec.intro}
\input{sections/1_introduction}

\section{Results}\label{sec.results}
\input{sections/2_1_model}
\input{sections/2_2_policies}

\section{Discussion}\label{sec.discussion}
\input{sections/3_discussion}

\section{Methods}\label{sec.methods}
\input{sections/4_methods}


\section{Data availability}\label{sec.data_availability}
The data shown in this paper can be found at \href{https://doi.org/10.4121/20402037.v1}{https://doi.org/10.4121/20402037.v1}.


\section{Code availability}\label{sec.code_availability}
Our code can be found in the following GitHub repository: \href{https://github.com/AlvaroGI/optimal-homogeneous-chain}{https://github.com/AlvaroGI/optimal-homogeneous-chain}.

\bibliographystyle{unsrt}













\subsection{Optimal entanglement distribution policies}
As described above, nodes always attempt entanglement generation if there are qubits available.
Cutoffs are always applied whenever an entangled state becomes too old.
Since nodes are free to attempt swaps as soon as entangled links are available or some time later, they must agree on an \emph{entanglement distribution policy}: a set of rules that indicate when to perform a swap.
The \emph{entanglement delivery time} of a policy is the time required to generate end-to-end entanglement when following said policy.
An \emph{optimal policy} minimizes the expected entanglement delivery time.
In a \emph{global-knowledge policy}, nodes have information about all the entangled links in the chain.
In a \emph{local-knowledge policy}, the nodes only need to know the state of the qubits they hold.
An example of local policy is the \emph{swap-asap policy}, in which each node performs a swap as soon as both entangled links are available.

We model the evolution of the state of the repeater chain as an MDP.
We then formulate the Bellman equations \cite{Sutton2018} and solve them using value iteration and policy iteration to find global-knowledge optimal policies.
More details and formal definitions are provided in Section \ref{sec.methods}.

Let us now describe the relation between the expected delivery time of an optimal policy, $T_\mathrm{opt}$, and the variables of the system ($n$, $p$, $p_\mathrm{s}$, and $t_\text{cut}$).
Repeater chains with a larger number of nodes $n$ yield a larger $T_\mathrm{opt}$, since more entangled links need to be generated probabilistically.
When $p$ is small, more entanglement generation attempts are required to succeed, yielding a larger $T_\mathrm{opt}$.
Decreasing $p_\text{s}$ also increases $T_\mathrm{opt}$, since more attempts at entanglement swapping are required on average.
When $\tc$ is small, all entangled states must be generated within a small time window and therefore $T_\mathrm{opt}$ is also larger.
Figure~\ref{fig.delivery-time-n5} shows the expected delivery time of an optimal policy in a five-node chain.
Interestingly, $p_\text{s}$ has a much stronger influence on $T_\mathrm{opt}$ than $p$ and $\tc$: decreasing $p_\text{s}$ from 1 to 0.5 in a five-node chain translates into an increase in $T_\mathrm{opt}$ of an order of magnitude.
Similar behavior is observed for other values of $n$, as shown in Appendix~\ref{app.optimal}.

\begin{figure}[t!]
\centering
\includegraphics[width=0.9\textwidth]{delivery-time_n5_tol1e-07.pdf}
\caption{\textbf{The expected delivery time increases with lower $p$, $p_\mathrm{s}$, and $t_\mathrm{cut}$.}
	Expected delivery time of an optimal policy, $T_\mathrm{opt}$, versus $p$ in a five-node chain, for different values of cutoff ($t_\text{cut}=2,5,10$). Solid lines correspond to deterministic swaps ($p_\text{s}=1$) and dashed lines correspond to probabilistic swaps with $p_\text{s}=0.5$.}
	\label{fig.delivery-time-n5}
\end{figure}

To evaluate the advantages of an optimal policy, we use the swap-asap policy as a baseline.
Early swaps can provide an advantage in terms of delivery time, since swapping earlier can free up qubits that can be used to generate backup entangled links, as displayed in the first transition in Figure~\ref{fig.chain_example}.
However, the age of a swapped link may reach the cutoff time earlier than one of the input links consumed in the swap, as the swapped link assumes the age of the oldest input link. Following the example in Figure~\ref{fig.chain_example} and assuming $\tc=1$, if no swaps are performed, the links between nodes two and three and between three and four will exist for one more time slot, while the link between nodes four and five will be removed immediately since it reached the cutoff time. If both swaps are performed, the swapped link between nodes two and five will be removed immediately since it reached the cutoff time.
Since we have arguments in favor of and against swapping early, it is not trivial to determine the scenarios in which the swap-asap policy is close to optimal. Next, we compare the expected delivery times of an optimal global-knowledge policy and the swap-asap policy.

\begin{figure}[t!]
\centering
\includegraphics[width=\textwidth]{FiveLinkChainEx}
\caption{\textbf{Swap-asap policies free up qubits, but swapped links expire earlier.}
Evolution of an example state when following a waiting policy versus the swap-asap policy during a single time slot.
Entangled links are represented as solid black lines, with occupied qubits in black and free qubits in white.
A waiting policy decides to not perform any swap, while the swap-asap policy decides to swap all three links.
The swap frees up qubits (marked in orange) that can be used to resume entanglement generation either if the swap is successful, as in the picture, or not.
After performing swaps, a cutoff $\tc=1$ is applied and links with age 1 are removed, causing the swapped link to expire.}
	\label{fig.chain_example}
\end{figure}

Figure~\ref{fig.advantage5} shows the relative difference between the expected delivery times of an optimal global-knowledge policy, $T_\text{opt}$, and that of the swap-asap policy, $T_\text{swap}$, in a five-node chain.
Increasing values of $(T_\text{swap}-T_\text{opt})/T_\text{opt}$ mean that the optimal policy is increasingly faster on average.
Note that we restrict our analysis to the parameter regime $p\geq0.3$ and $2\leq\tc\leq6$ due to the very large computational cost of calculating the solution for smaller $p$ and larger $\tc$ (for more details, see Section \ref{sec.methods}).
Let us first focus on deterministic swaps (Figure~\ref{fig.advantage5-ps1}).
The advantage provided by an optimal policy increases for decreasing $p$.
When $p$ is small, links are more valuable since they are harder to generate. Therefore, it is convenient to avoid early swaps, as they effectively increase the ages of the links involved and make them expire earlier.
When $\tc$ is small, a similar effect happens: all entangled links must be generated within a small time window and early swaps can make them expire too soon. For larger $\tc$, increasing the age of a link does not have a strong impact on the delivery time, since the time window is larger. Therefore, an optimal policy is increasingly better than swap-asap for decreasing $\tc$.
The maximum difference between expected delivery times in the parameter region explored is 5.25\%.

Interestingly, probabilistic swaps (Figure~\ref{fig.advantage5-ps05}) yield an opposite behavior in the parameter region explored: optimal policies are increasingly better than swap-asap for increasing $p$ and $\tc$ (except when $p\leq0.4$ and $\tc\leq3$), and the relative difference in expected delivery time can be as large as 13.2\% (achieved in a five-node chain with $p=0.9$ and $\tc=6$).
One reason for this may be the action that each policy decides to perform when the repeater chain is in a \emph{full state}, which is a situation where each pair of neighboring nodes shares an entangled link (see state at the top of Figure~\ref{fig.swapasap-vs-doubling}).
When swaps are deterministic, the optimal policy chooses to swap all links in a full state, since end-to-end entanglement will always be achieved.
However, when swaps are probabilistic, an optimal policy generally chooses to perform two separate swaps (see Figure~\ref{fig.swapasap-vs-doubling}), similar to the nested purification scheme proposed in \cite{Briegel1998}.
As an example, for $n=5$, $p=0.9$, $\tc=2$, and $p_\text{s}=0.5$, the swap-asap policy yields an expected delivery time of $T=9.35$.
If, in full states, the swap at the third node is withheld, $T$ drops to 8.34.
The swap-asap policy is on average slower than this modified policy by 12.1\%.
The action chosen in full states has a stronger influence on $T$ for increasing $p$. This is because full states are more frequent for large $p$: whenever a swap fails, a full state is soon recovered, since new entangled states are generated with high probability.
As a consequence, an optimal policy is increasingly better than swap-asap for higher $p$ when swaps are probabilistic.
A similar effect happens for large $\tc$.
Note however that the effect of the action chosen in full states is practically irrelevant in four-node chains (see Appendix~\ref{app.optimal}).
Note also that the advantage of an optimal policy in terms of delivery time is not always monotonic in $p$ and $t_\text{cut}$ (see Appendix~\ref{app.optimal}).

\begin{figure}[t!]
\captionsetup[subfigure]{justification=centering}
     \centering
     \begin{subfigure}[b]{0.9\textwidth}
         \centering
         \includegraphics[width=\textwidth]{advantage__n5_ps1.000_tolerance1e-07_randomseed2.pdf}
	\vspace{-1.5\baselineskip}
         \caption{Deterministic swaps ($p_\mathrm{s}=1$).}
	\label{fig.advantage5-ps1}
         \vspace{5pt}
     \end{subfigure}
     
     \begin{subfigure}[b]{0.9\textwidth}
         \centering
         \includegraphics[width=\textwidth]{advantage__n5_ps0.500_tolerance1e-07_randomseed2.pdf}
	\vspace{-1.5\baselineskip}
         \caption{Probabilistic swaps ($p_\mathrm{s}=0.5$).}
	\label{fig.advantage5-ps05}
         \vspace{5pt}
     \end{subfigure}
     
	\caption{\textbf{In a five-node chain, an optimal policy performs increasingly better than swap-asap for lower/higher values of $p$ and $t_\mathrm{cut}$ when swaps are deterministic/probabilistic.}
	Relative difference between the expected delivery times of an optimal policy, $T_\mathrm{opt}$, and the swap-asap policy, $T_\mathrm{swap}$, in a five-node chain, for different values of $p$ and $\tc$.
	}
	\label{fig.advantage5}
\end{figure}

\begin{figure}[t!]
	\centering
	\includegraphics[width=\textwidth]{figs/swapasap-vs-doubling}
	\caption{\textbf{All possible transitions after performing a swap-asap action or a nested action in a full state, depending on which swaps succeed.}
	In full states, every pair of neighbors shares an entangled link (solid black lines, with occupied qubits in black and free qubits in white).
	The swap-asap policy decides to swap all links, while the nested approach consists in swapping only at nodes 2 and 4.
	When swaps are probabilistic, the nested approach is generally optimal in terms of expected delivery time.}
	\label{fig.swapasap-vs-doubling}
\end{figure}

Optimal policies are also increasingly faster than swap-asap for increasing $n$, as shown in Figure~\ref{fig.advantage-n}.
For example, for $p=0.3$, $p_\text{s}=0.5$, and $t_\text{cut}=2$, the relative difference in expected delivery time is 1.7\%, 5.9\%, and 12.3\%, for $n=4$, 5, and 6, respectively. 
This is in line with the fact that, when the number of nodes grows, there are increasingly more states in which the optimal action is to perform a strict subset of all possible swaps, as shown in Appendix~\ref{app.swapasap-states}.
Note that, in three- and four-node chains, the relative difference in expected delivery time is generally below 1\%.

\begin{figure}[t]
\captionsetup[subfigure]{justification=centering}
     \centering
     \begin{subfigure}[b]{0.8\textwidth}
         \centering
         \includegraphics[width=\textwidth]{advantageVSn_p0.3-0.9_ps1_tcut2_randseed2.pdf}
	\vspace{-1.5\baselineskip}
         \caption{Deterministic swaps ($p_\mathrm{s}=1$).}
	\label{fig.advantage-n-ps1}
         \vspace{5pt}
     \end{subfigure}
     
     \begin{subfigure}[b]{0.8\textwidth}
         \centering
         \includegraphics[width=\textwidth]{advantageVSn_p0.3-0.9_ps0.5_tcut2_randseed2.pdf}
	\vspace{-1.5\baselineskip}
         \caption{Probabilistic swaps ($p_\mathrm{s}=0.5$).}
	\label{fig.advantage-n-ps05}
         \vspace{5pt}
     \end{subfigure}
     
	\caption{\textbf{An optimal policy performs increasingly better than swap-asap in longer chains.}
	Relative difference between the expected delivery times of an optimal policy, $T_\mathrm{opt}$, and the swap-asap policy, $T_\mathrm{swap}$, for $\tc=2$ and different values of $p$, as a function of the number of nodes $n$.
	Black lines correspond to $p=0.3$, and the value of $p$ increases in steps of $0.1$ with increasing line transparency up to $p=0.9$.
	}
	\label{fig.advantage-n}
\end{figure}






















\subsection{Network model}\label{subsec.model}
We analyze quantum repeater chains wherein nodes can store quantum states in the form of qubits and can perform three basic operations with them:
\\

\ssec{Entanglement generation.} Two adjacent nodes can attempt the heralded generation of an entangled link (i.e., a shared bipartite entangled state), succeeding with probability $p$. Generation of entanglement is heralded, meaning that the nodes receive a message stating whether they successfully generated an entangled link or not \cite{Barrett2005,Bernien2013}.
We assume that entanglement generation is noisy. Hence, the newly generated entangled links are not maximally entangled states but Werner states \cite{Werner1989}. Werner states are maximally entangled states that have been subjected to a depolarizing process, which is a worst-case noise model \cite{Dur2005}, and they can be written as follows:
\begin{equation}
    \rho = \frac{4F-1}{3}\ketbra{\phi^+} + \frac{1-F}{3} \mathbb{I}_4,
\end{equation}
where $\ket{\phi^+}=\frac{\ket{00}+\ket{11}}{\sqrt{2}}$ is a maximally entangled state, $F$ is the fidelity of the Werner state to the state $\ket{\phi^+}$, and $\mathbb{I}_d$ is the $d$-dimensional identity.
In our notation, the fidelity of a mixed state $\rho$ to a pure state $\ket{\phi}$ is defined as
\begin{equation}
    F(\rho,\ket{\phi}) \vcentcolon= \bra{\phi}\rho\ket{\phi}.
\end{equation}
We assume that the fidelity of newly generated entangled links is $F_\text{new}\leq1$.
\\

\ssec{Entanglement swap.} Two neighboring entangled links can be fused into a longer-distance entangled link. Consider a situation where node B shares an entangled link with node A, and another link with node C (see Figure~\ref{fig.swap}). Then, B can perform an entanglement swap to produce an entangled link between A and C while consuming both initial links \cite{Zukowski1993, Duan2001, Sangouard2011}. We refer to the link generated in a swap operation as a \emph{swapped link}.
This operation is also probabilistic: a new link is produced with probability $p_\text{s}$, and no link is produced (but both input links are still consumed) with probability $1-p_\text{s}$.

The generation of an entangled link between two end nodes without intermediate repeaters is limited by the distance between the end nodes \cite{Munro2015} -- e.g., the noise affecting a photon sent over an optical fiber grows exponentially with the length of the fiber \cite{Briegel1998}.
Therefore, a repeater chain that makes use of entanglement swapping is needed to generate end-to-end entanglement over long distances.
\\

\begin{figure}[t]
	\centering
	\includegraphics[width=0.6\textwidth]{figs/swap}
	\caption{\textbf{Entanglement swap.}
	When node B performs a swap, an entangled link between nodes A and B and an entangled link between nodes B and C are consumed to produce a single entangled link between A and C. This operation is essential for the generation of long-distance entanglement.}
	\label{fig.swap}
\end{figure}

\ssec{Cutoffs.} The fidelity of a quantum state decreases over time due to couplings to the environment \cite{Dur2005,Chirolli2008}.
These decoherence processes can be captured using a white noise model in which a depolarizing channel is applied to the entangled state at every instant. As a result, the fidelity of a Werner state at time $t$, $F(t)$, is given by
\begin{equation}\label{eq.ftT}
    F(t) = \frac{1}{4} + \Big( F(t-\Delta t) - \frac{1}{4}\Big) e^{-\Delta t/T_2},
\end{equation}
where $\Delta t$ is an arbitrary interval of time and $T_2$ is the coherence time of the qubits, a parameter that depends on the physical realization of the qubit. (\ref{eq.ftT}) is derived in Appendix \ref{app.decoherence}.


In general, quantum network applications require quantum states with fidelity above some threshold value $F_\text{min}$.
A common solution is to impose a cutoff time $\tc$ on the entangled links: all entangled links used to generate the final end-to-end link must be generated within a time window of size $\tc$ \cite{Rozpedek2018}.
Imposing memory cutoffs requires keeping track of the time passed since the creation of each entangled link. We call this time the \emph{age} of the link.
A link is discarded whenever it gets older than $\tc$.
Moreover, we assume that an entangled link generated as a result of entanglement swapping assumes the age of the oldest link that was involved in the swapping operation.
Another valid approach to calculate the age of a swapped link would be to re-compute the age based on the post-swap fidelity, although this would lead to a more complicated formulation to ensure that all the links that were used to produce a swapped link were generated within the time window of size $t_\text{cut}$.
To produce end-to-end links with fidelity above $F_\text{min}$ on a repeater chain that generates new links with fidelity $F_\text{new}$, it suffices to ensure that the worst policy, i.e., the policy that produces the lowest end-to-end fidelity, satisfies this requirement.
In Appendix \ref{app.cutoff}, we show that the policy that yields the lowest fidelity for the end-to-end link waits until the end of the $t_\text{cut}$ interval to perform all entanglement swaps.
Analyzing such a worst policy leads to the following condition for the cutoff time:
\begin{equation}\label{eq.cutoffcondition}
    \tc \leq -T_2 \ln\Bigg(\frac{3}{4F_\text{new}-1} \Big( \frac{4F_\text{min}-1}{3} \Big)^{\frac{1}{n-1}} \Bigg),
\end{equation}
where $n$ is the number of nodes.
For a full derivation of the previous condition, see Appendix \ref{app.cutoff}.
\\

In this paper, we consider quantum networks that operate with a limited number of qubits. Specifically, we use the following additional assumptions:
\begin{enumerate}[label=(\roman*)]
	\item The chain is \textbf{homogeneous}, i.e., the hardware is identical in all nodes. This means that all pairs of neighbors generate links with the same success probability $p$ and fidelity $F_\text{new}$, all swaps succeed with probability $p_\text{s}$, all states decohere according to some coherence time $T_2$, and all nodes apply the same cutoff time $t_\text{cut}$. This assumption may not hold for some long-distance quantum networks where each node is implemented using a different technology, but may be directly applicable to, e.g., small metropolitan-scale networks.
	\item We assume that each node has only \textbf{two storage qubits}, each of which is used to generate entanglement with one side of the chain. Each end node has a single storage qubit.
	This assumption is in line with the expectations for early quantum networks, in which nodes are likely to have a number of storage qubits on the order of the unit (e.g., in \cite{Pompili2021} the authors realized the first three-node quantum network using NV centers, each with a single storage qubit).
    	\item Time is discretized into non-overlapping \textbf{time slots}. During one time slot, the nodes first attempt entanglement generation; second, they can attempt entanglement swaps; and lastly they discard any entangled link that existed for longer than $\tc$ time slots.
    The unit of time used in this paper is the duration of a time slot, unless otherwise specified.
    	\item We also assume that classical communication between nodes is instantaneous. This means that every node has \textbf{global knowledge} of the state of the repeater chain in real time.
	In general, this is not a realistic assumption. However, given that classical communication delays decrease the performance of the network, our results constitute a lower bound on the expected delivery time of real setups and can be used as a benchmark.
\end{enumerate}

A repeater chain under the previous assumptions is characterized by four parameters:
\begin{itemize}
	\item[·] $n$: number of nodes in the chain, including end nodes.
	\item[·] $p$: probability of successful entanglement generation.
	\item[·] $p_\text{s}$: probability of successful swap.
	\item[·] $\tc$: cutoff time.
	Note that $F_\text{new}$, $F_\text{min}$, and $T_2$ are used to determine a proper value of cutoff time (see condition (\ref{eq.cutoffcondition})), but they are not needed after that.
\end{itemize}

In an experimental setup, the value of $p$ is determined by the inter-node distance and the type of hardware used, as quantum nodes can be realized using different technologies, such as NV centers \cite{Rozpedek2019, Bernien2013, Hensen2015, Humphreys2018, Pompili2021} and trapped ions \cite{Moehring2007,Slodicka2013}.
Linear optics setups generally perform swaps with probability $p_\text{s}=0.5$ \cite{Duan2001,Calsamiglia2001}, while other setups can perform deterministic swaps ($p_\text{s}=1$) at the cost of a slower speed of operation \cite{Pompili2021}.
The cutoff time $\tc$ can be chosen by the user, as long as condition (\ref{eq.cutoffcondition}) is satisfied. Note that (\ref{eq.cutoffcondition}) depends on $T_2$ (which depends on the hardware available), $F_\text{new}$ (which depends on the hardware and the choice of entanglement generation protocol), and $F_\text{min}$ (which is specified by the final application).
\\

The state of the repeater chain at the end of each time slot can be described using the age of every entangled link.
In Figure~\ref{fig.chain_evolution} we show an example of the evolution of the state of a chain with cutoff $t_\text{cut}=3$, over four time slots:
\begin{itemize}
	\item In the first time slot ($t\in [0,1)$), all pairs of neighbors attempt entanglement generation, but it only succeeds between nodes two and three.
	No swaps can be performed, and the only link present is younger than the cutoff, so it is not discarded.
	\item In the second time slot ($t\in [1,2)$), the age of the link between nodes two and three increases by one. All pairs of neighbors (except nodes two and three) attempt entanglement generation, which succeeds between nodes four and five.
	\item In the third time slot ($t\in [2,3)$), the age of both existing links increases by one.
	All pairs of neighbors (except nodes two and three and nodes four and five) attempt entanglement generation, and only nodes five and six succeed.
	A swap can be performed at node five but they decide to wait.
	\item In the fourth time slot ($t\in [3,4)$), the age of every existing link increases by one.
	Nodes one and two and nodes three and four attempt entanglement generation but none of the pairs succeeds.
	A swap is successfully performed at node five, and a new link between nodes four and six is generated. This new link assumes the age of the oldest link involved in the swap operation.
	Lastly, the entangled link between nodes two and three is discarded, as its age reached the cutoff time.
\end{itemize}

\begin{figure}[t]
	\centering
	\includegraphics[width=0.8\textwidth]{figs/chain_evolution}
	\caption{\textbf{Example of entangled link dynamics in a repeater chain.}
	Each row represents the state of the chain at the end of time slot $t$.
	Entangled links are represented as black solid lines, with occupied qubits as black circles. The number above each entangled link is the age of the link. We assume cutoff $t_\text{cut}=3$.}
	\label{fig.chain_evolution}
\end{figure}
















