text:
\section{Introduction}
This document is a model and instructions for \LaTeX.
Please observe the conference page limits.

\section{Ease of Use}

\subsection{Maintaining the Integrity of the Specifications}

The IEEEtran class file is used to format your paper and style the text. All margins,
column widths, line spaces, and text fonts are prescribed; please do not
alter them. You may note peculiarities. For example, the head margin
measures proportionately more than is customary. This measurement
and others are deliberate, using specifications that anticipate your paper
as one part of the entire proceedings, and not as an independent document.
Please do not revise any of the current designations.

\section{Prepare Your Paper Before Styling}
Before you begin to format your paper, first write and save the content as a
separate text file. Complete all content and organizational editing before
formatting. Please note sections \ref{AA}--\ref{SCM} below for more information on
proofreading, spelling and grammar.

Keep your text and graphic files separate until after the text has been
formatted and styled. Do not number text heads---{\LaTeX} will do that
for you.

\subsection{Abbreviations and Acronyms}\label{AA}
Define abbreviations and acronyms the first time they are used in the text,
even after they have been defined in the abstract. Abbreviations such as
IEEE, SI, MKS, CGS, ac, dc, and rms do not have to be defined. Do not use
abbreviations in the title or heads unless they are unavoidable.

\subsection{Units}
\begin{itemize}
\item Use either SI (MKS) or CGS as primary units. (SI units are encouraged.) English units may be used as secondary units (in parentheses). An exception would be the use of English units as identifiers in trade, such as ``3.5-inch disk drive''.
\item Avoid combining SI and CGS units, such as current in amperes and magnetic field in oersteds. This often leads to confusion because equations do not balance dimensionally. If you must use mixed units, clearly state the units for each quantity that you use in an equation.
\item Do not mix complete spellings and abbreviations of units: ``Wb/m\textsuperscript{2}'' or ``webers per square meter'', not ``webers/m\textsuperscript{2}''. Spell out units when they appear in text: ``. . . a few henries'', not ``. . . a few H''.
\item Use a zero before decimal points: ``0.25'', not ``.25''. Use ``cm\textsuperscript{3}'', not ``cc''.)
\end{itemize}

\subsection{Equations}
Number equations consecutively. To make your
equations more compact, you may use the solidus (~/~), the exp function, or
appropriate exponents. Italicize Roman symbols for quantities and variables,
but not Greek symbols. Use a long dash rather than a hyphen for a minus
sign. Punctuate equations with commas or periods when they are part of a
sentence, as in:
\begin{equation}
a+b=\gamma\label{eq}
\end{equation}

Be sure that the
symbols in your equation have been defined before or immediately following
the equation. Use ``\eqref{eq}'', not ``Eq.~\eqref{eq}'' or ``equation \eqref{eq}'', except at
the beginning of a sentence: ``Equation \eqref{eq} is . . .''

\subsection{\LaTeX-Specific Advice}

Please use ``soft'' (e.g., \verb|\eqref{Eq}|) cross references instead
of ``hard'' references (e.g., \verb|(1)|). That will make it possible
to combine sections, add equations, or change the order of figures or
citations without having to go through the file line by line.

Please don't use the \verb|{eqnarray}| equation environment. Use
\verb|{align}| or \verb|{IEEEeqnarray}| instead. The \verb|{eqnarray}|
environment leaves unsightly spaces around relation symbols.

Please note that the \verb|{subequations}| environment in {\LaTeX}
will increment the main equation counter even when there are no
equation numbers displayed. If you forget that, you might write an
article in which the equation numbers skip from (17) to (20), causing
the copy editors to wonder if you've discovered a new method of
counting.

{\BibTeX} does not work by magic. It doesn't get the bibliographic
data from thin air but from .bib files. If you use {\BibTeX} to produce a
bibliography you must send the .bib files.

{\LaTeX} can't read your mind. If you assign the same label to a
subsubsection and a table, you might find that Table I has been cross
referenced as Table IV-B3.

{\LaTeX} does not have precognitive abilities. If you put a
\verb|\label| command before the command that updates the counter it's
supposed to be using, the label will pick up the last counter to be
cross referenced instead. In particular, a \verb|\label| command
should not go before the caption of a figure or a table.

Do not use \verb|\nonumber| inside the \verb|{array}| environment. It
will not stop equation numbers inside \verb|{array}| (there won't be
any anyway) and it might stop a wanted equation number in the
surrounding equation.

\subsection{Some Common Mistakes}\label{SCM}
\begin{itemize}
\item The word ``data'' is plural, not singular.
\item The subscript for the permeability of vacuum $\mu_{0}$, and other common scientific constants, is zero with subscript formatting, not a lowercase letter ``o''.
\item In American English, commas, semicolons, periods, question and exclamation marks are located within quotation marks only when a complete thought or name is cited, such as a title or full quotation. When quotation marks are used, instead of a bold or italic typeface, to highlight a word or phrase, punctuation should appear outside of the quotation marks. A parenthetical phrase or statement at the end of a sentence is punctuated outside of the closing parenthesis (like this). (A parenthetical sentence is punctuated within the parentheses.)
\item A graph within a graph is an ``inset'', not an ``insert''. The word alternatively is preferred to the word ``alternately'' (unless you really mean something that alternates).
\item Do not use the word ``essentially'' to mean ``approximately'' or ``effectively''.
\item In your paper title, if the words ``that uses'' can accurately replace the word ``using'', capitalize the ``u''; if not, keep using lower-cased.
\item Be aware of the different meanings of the homophones ``affect'' and ``effect'', ``complement'' and ``compliment'', ``discreet'' and ``discrete'', ``principal'' and ``principle''.
\item Do not confuse ``imply'' and ``infer''.
\item The prefix ``non'' is not a word; it should be joined to the word it modifies, usually without a hyphen.
\item There is no period after the ``et'' in the Latin abbreviation ``et al.''.
\item The abbreviation ``i.e.'' means ``that is'', and the abbreviation ``e.g.'' means ``for example''.
\end{itemize}
An excellent style manual for science writers is \cite{b7}.

\subsection{Authors and Affiliations}
\textbf{The class file is designed for, but not limited to, six authors.} A
minimum of one author is required for all conference articles. Author names
should be listed starting from left to right and then moving down to the
next line. This is the author sequence that will be used in future citations
and by indexing services. Names should not be listed in columns nor group by
affiliation. Please keep your affiliations as succinct as possible (for
example, do not differentiate among departments of the same organization).

\subsection{Identify the Headings}
Headings, or heads, are organizational devices that guide the reader through
your paper. There are two types: component heads and text heads.

Component heads identify the different components of your paper and are not
topically subordinate to each other. Examples include Acknowledgments and
References and, for these, the correct style to use is ``Heading 5''. Use
``figure caption'' for your Figure captions, and ``table head'' for your
table title. Run-in heads, such as ``Abstract'', will require you to apply a
style (in this case, italic) in addition to the style provided by the drop
down menu to differentiate the head from the text.

Text heads organize the topics on a relational, hierarchical basis. For
example, the paper title is the primary text head because all subsequent
material relates and elaborates on this one topic. If there are two or more
sub-topics, the next level head (uppercase Roman numerals) should be used
and, conversely, if there are not at least two sub-topics, then no subheads
should be introduced.

\subsection{Figures and Tables}
\paragraph{Positioning Figures and Tables} Place figures and tables at the top and
bottom of columns. Avoid placing them in the middle of columns. Large
figures and tables may span across both columns. Figure captions should be
below the figures; table heads should appear above the tables. Insert
figures and tables after they are cited in the text. Use the abbreviation
``Fig.~\ref{fig}'', even at the beginning of a sentence.

\begin{table}[htbp]
\caption{Table Type Styles}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\textbf{Table}&\multicolumn{3}{|c|}{\textbf{Table Column Head}} \\
\cline{2-4}
\textbf{Head} & \textbf{\textit{Table column subhead}}& \textbf{\textit{Subhead}}& \textbf{\textit{Subhead}} \\
\hline
copy& More table copy$^{\mathrm{a}}$& &  \\
\hline
\multicolumn{4}{l}{$^{\mathrm{a}}$Sample of a Table footnote.}
\end{tabular}
\label{tab1}
\end{center}
\end{table}

\begin{figure}[htbp]
\centerline{\includegraphics{fig1.png}}
\caption{Example of a figure caption.}
\label{fig}
\end{figure}

Figure Labels: Use 8 point Times New Roman for Figure labels. Use words
rather than symbols or abbreviations when writing Figure axis labels to
avoid confusing the reader. As an example, write the quantity
``Magnetization'', or ``Magnetization, M'', not just ``M''. If including
units in the label, present them within parentheses. Do not label axes only
with units. In the example, write ``Magnetization (A/m)'' or ``Magnetization
\{A[m(1)]\}'', not just ``A/m''. Do not label axes with a ratio of
quantities and units. For example, write ``Temperature (K)'', not
``Temperature/K''.

\section*{Acknowledgment}

The preferred spelling of the word ``acknowledgment'' in America is without
an ``e'' after the ``g''. Avoid the stilted expression ``one of us (R. B.
G.) thanks $\ldots$''. Instead, try ``R. B. G. thanks$\ldots$''. Put sponsor
acknowledgments in the unnumbered footnote on the first page.

\section*{References}

Please number citations consecutively within brackets \cite{b1}. The
sentence punctuation follows the bracket \cite{b2}. Refer simply to the reference
number, as in \cite{b3}---do not use ``Ref. \cite{b3}'' or ``reference \cite{b3}'' except at
the beginning of a sentence: ``Reference \cite{b3} was the first $\ldots$''

Number footnotes separately in superscripts. Place the actual footnote at
the bottom of the column in which it was cited. Do not put footnotes in the
abstract or reference list. Use letters for table footnotes.

Unless there are six authors or more give all authors' names; do not use
``et al.''. Papers that have not been published, even if they have been
submitted for publication, should be cited as ``unpublished'' \cite{b4}. Papers
that have been accepted for publication should be cited as ``in press'' \cite{b5}.
Capitalize only the first word in a paper title, except for proper nouns and
element symbols.

For papers published in translation journals, please give the English
citation first, followed by the original foreign-language citation \cite{b6}.

\section{Introduction}

Quantum key distribution (QKD) allows for the establishment of information theoretically secure secret keys between two or more parties.  However, despite their great potential, these systems face several critical shortcomings when attempting to implement them in practice.  Of particular importance are improving the speed and distance of these systems.  To overcome these limitations, quantum networks are often used, consisting of \emph{trusted nodes} and, in the near future, \emph{quantum repeaters} \cite{repeater1,repeater2}.  Since quantum repeaters are still a developing technology, current QKD networks established in various metropolitan areas consist only of end-users and trusted nodes \cite{elliott2004darpa,chen2010metropolitan,peev2009secoqc,zhang2018large,sasaki2011field}.  However, progress in developing stable quantum repeaters has been accelerating of late and so it is vital to begin developing suitable routing algorithms for networks consisting of a mixture of both repeaters and trusted nodes.  Indeed, developing efficient routing algorithms to operate in this setting is vital to the future performance of such networks.

Numerous work has been done investigating the performance of quantum networks consisting only of quantum repeaters (in addition to end users) \cite{van2013path,azuma2016fundamental,hahn2019quantum,vardoyan2019stochastic,pirandola2016capacities,wallnofer2019multipartite,pirandola2019end,li2020effective}, including the development and analysis of new routing protocols specific to that scenario \cite{caleffi2017optimal,gyongyosi2017entanglement,sazim2015retrieving,pant2019routing,chakraborty2019distributed}.  Mostly, the goal of such networks is to establish end-to-end entanglement between end users (which may, then, be used for QKD for instance).  However, QKD is a more practical technology today and there are several methods to improve their performance, such as through trusted nodes.  Thus it is also important to study QKD-specific networks.  Such work has been done investigating practical QKD-specific networks consisting predominately of trusted nodes and end users \cite{dianati2008architecture,qkd-network-stack,yang2017qkd}.  However, as repeater technology progresses, the desire to move away from trusted node technology, and their inherent security concerns, will become stronger.

Thus, it is important to begin investigating near-future QKD-specific networks consisting predominately of quantum repeaters, however with a minority of trusted nodes.  Furthermore, these networks will allow for multiple paths to be established between both repeaters and trusted nodes (i.e., repeaters are not used only to extend the distance between trusted nodes, but will be an integral part of the network interior).  These are the networks we consider in this paper.  In particular, we consider a grid topology in which it is possible to establish multiple paths between Alice, Bob, and various trusted nodes though a complex network of repeaters. Our goal is to understand what routing protocols can lead to efficient key distribution rates between end users and to understand how the quality of the repeaters and the number of trusted nodes, affects the performance of this network.

In this paper, we devise and evaluate three different routing algorithms for this QKD network: one requires global state information and the other two are decentralized, distributed, algorithms requiring only local state information.
We perform a rigorous evaluation, through simulations, of the performance of our algorithms in a variety of scenarios considering network size; quantum repeater quality; distance between nodes; quantity and specific location of trusted nodes; and channel noise.  Our results show that the careful design of routing algorithms is vital to establishing efficient key-distribution rates between users.  Along the way, we discover several fascinating properties of these networks which may be of great importance to operators of this future network architecture.

\subsection{Quantum Key Distribution}
Quantum key distribution (QKD) protocols operate in two stages: In the \emph{quantum communication stage}, users Alice and Bob use the quantum channel and the authenticated classical channel to attempt to establish a \emph{raw key} which is a classical bit string that is partially correlated (there may be errors in the quantum channel leading to errors in the raw key) and partially secret (an adversary may have some information on the raw key).  Since this raw key cannot be used directly for cryptographic purposes, a second, purely classical, stage is performed, running an error correction protocol (leaking additional information to an adversary) followed by privacy amplification, which leads to the final secret key.  An important metric in any QKD protocol is the protocol's \emph{key-rate} defined to be the ratio of secret key bits to the size of the raw key.  For a general survey of QKD protocols, the reader is referred to \cite{QKD-survey-old,QKD-Survey}.

In this work, we are interested in the theoretical performance of a network of QKD systems.  As such, we consider ideal single-qubit sources (though potentially there is loss due to the fiber channel connecting nodes).  Furthermore, we do not consider finite key effects \cite{scarani2008quantum} or imperfect sampling, in an attempt to understand the theoretical behavior of the network.  Under this setting, the key-rate of the E91 \cite{QKD-E91} protocol, which we adopt as the QKD protocol used in our network, is found to be \cite{QKD-BB84-rate1,QKD-renner-keyrate}: $\texttt{rate} = 1-2h(Q)$, where $Q$ is the bit error rate in the raw key and $h(\cdot)$ is the binary entropy function.  Note that, if we did not assume single-qubit sources and, instead, weak coherent sources, we would need to use an alternative key-rate expression or, perhaps, the decoy state BB84 protocol \cite{lo2005decoy}; these are interesting issues we leave as future work.

Point-to-point QKD systems are often implemented over fiber channels (though free-space operation is also possible if one has direct line of sight).  One limitation to QKD protocols is their intolerance to qubit loss \cite{pirandola2017fundamental,QKD-Survey}; since loss over a fiber channel scales exponentially with distance, this is particularly problematic for ground operation.  To overcome this, one may use \emph{quantum repeaters} \cite{repeater1,repeater2} and \emph{trusted nodes}.  Both systems are placed between users, thus halving the total distance a qubit is required to travel; furthermore, multiple such nodes may be chained together thus further decreasing the distance.  Quantum repeaters utilize entanglement swapping to produce a shared entangled bit between two users.  Trusted nodes act as users in a QKD protocol, establishing a key $k_{AT}$ with Alice and a second, independent key, $k_{TB}$ with Bob.  The trusted node then sends to $B$ (using an authenticated classical channel) the value $k_{AT}\oplus k_{TB}$, where $\oplus$ is the bit-wise XOR.  This allows Alice and Bob to share a classical key, though the trusted node also shares this key.

The advantage to quantum repeaters is that the final key $A$ and $B$ produce is independent of the repeater's knowledge.  That is, if a repeater is controlled by an adversary, it cannot learn the final secret key.  However, the technology for repeaters requires short-term quantum memories which is a difficult engineering challenge (though the technology is rapidly advancing).  Trusted nodes have the advantage of simplicity as they are no different in technology than Alice or Bob.  However, they must remain trusted and safe from an adversary as they do have full knowledge of the secret key.

\subsection{Related Work}
There has been recent research in analyzing routing protocols, along with the general behavior and performance, of quantum networks consisting of end-users and quantum repeaters, but no trusted nodes; see for instance \cite{van2013path,azuma2016fundamental,caleffi2017optimal,gyongyosi2017entanglement,hahn2019quantum,pant2019routing,vardoyan2019stochastic,chakraborty2019distributed,pirandola2016capacities,wallnofer2019multipartite,pirandola2019end} with \cite{caleffi2017optimal,gyongyosi2017entanglement,pant2019routing,chakraborty2019distributed} giving particular focus on specific routing protocols for certain network topologies in generating shared entanglement between users, which is a stronger resource than QKD. However, QKD is, currently, a more practical and mature technology and, furthermore, there are numerous methods of improving the performance (speed and distance) of these systems that are unavailable to entanglement generation networks, namely the use of trusted nodes.  Thus, while routing protocols designed for an entanglement-generation quantum internet can be used also for QKD, more efficient systems may exist and, furthermore, solutions incorporating both trusted nodes and repeaters are vital for near-term deployment of this technology and are the networks we consider in this work.

Early work on QKD-specific networks focused on algorithms for optical-based switching networks \cite{toliver2003experimental}.  Such networks were used in practice, for instance the 2004 DARPA network in the Boston area \cite{elliott2004darpa,elliott2005current} and the 2009 network in Hefei \cite{chen2010metropolitan}, utilized such an architecture (the Hefei network also utilized trusted nodes).  These networks consisted of end-users and optical switches allowing users to route qubits to each other.

A more capable QKD network consists of end-users and trusted nodes and is the most common of network architectures for practical QKD networks in operation today such as the SECOQC network in Vienna \cite{peev2009secoqc}, the previously mentioned Hefei network \cite{chen2010metropolitan}, the Tokyo QKD network \cite{sasaki2011field} and the Beijing-Shanghai network \cite{zhang2018large}.  In terms of routing algorithms, the Vienna network used a variant of the OSPF routing algorithm \cite{dianati2008architecture}.  In \cite{tanizawa2016routing}, required functionalities of a QKD network routing algorithm were described for this form of network and a routing protocol was proposed, while \cite{yang2017qkd} began constructing routing protocols for larger scale networks evaluated through simulations. A novel quality of service model for these networks, and new routing protocols, were introduced in \cite{mehic2019novel}.  A complete QKD network stack for such networks was proposed in \cite{qkd-network-stack}, along with advanced routing functionalities through trusted nodes taking into account channel performance and key-rate demands, while in \cite{li2020mathematical}, a mathematical model was proposed for analyzing such trusted-node QKD networks.

The severe limitation to trusted nodes is that, as their name implies, they must be trusted.  Indeed, a trusted node is fully aware of the secret key which $A$ and $B$ distill (multi-path routing is one counter-measure to this, though still imperfect).  An advancement from this would be the use of quantum repeaters.  However, while the technology for these is advancing rapidly, it is more likely that in the near-future, any QKD network will consist of both repeaters and trusted nodes.  Thus, developing new and efficient routing algorithms specific for this network technology, is vital.  In this work, we consider networks that consist of a majority of repeaters with a minority of trusted nodes, attempting to discover optimal routing protocols for this scenario and to understand the behavior of such a network.  Note that in \cite{qkd-network-stack}, the use of quantum repeaters in a chain to link together different trusted nodes was considered an option; here, however, we are considering more complex networks of repeaters, allowing for potential multi-path routing options between both trusted nodes and multiple repeaters.

\section{Discussion}
\section{Summary and Insights}
The data suggests a number of interesting lessons regarding this sort of QKD network. Most glaringly, it is immediately evident that the addition of even a single trusted node into a network can greatly increase what key rates are achievable, even with ideal repeater technology. Further, we see that a small adjustment to the natural local routing algorithm, in the form of a tendency to avoid intersection of paths, can lead to increases in key rate comparable to, or even exceeding, that of the addition of a single trusted node, with a negligible increase in complexity. As we have seen, this increase in key rates generalizes to multiple trusted nodes, on larger grids, but there is some consideration that must be given to the placement of the additional trusted nodes. Indeed, a non-optimal placement of trusted nodes can in fact hinder the operation of the network, especially for the local algorithms.

The data further suggests some lessons regarding the limitations of such a network. We see that while fiber length plays an important role in determining key rate, it is the BSM success probability and the decoherence rate that are seemingly the largest obstacles to achieving a higher key rate. This relationship is no more evident than in Fig.~\ref{fig:FixedLength}, where we see that these factors play an important role in limiting the total distance the network can cover, as they make it infeasible to mitigate the effects of fiber length by simply adding additional nodes to the network. In fact  doing so can actually decrease key rates, if not counterbalanced with the addition of trusted nodes.

Finally, our analysis makes clear the important role trusted nodes will still have to play after quantum repeater networks become practical, or even perfect. As was shown in Fig.~\ref{fig:2TNGraphsB}, even with perfect quantum repeaters, the addition of trusted nodes can result in positive and significant key rates being achieved where they were otherwise not possible. Trusted nodes can be used in the networks to facilitate the establishment of efficient QKD networks reaching along far distances consisting of many nodes. In fact, one can even conceive of network models in which the trusted nodes also operate as part of a multi-party QKD system.

\section{Conclusion}
In this work we have proposed a novel model for analyzing the performance of quantum repeater QKD grid networks with the inclusion of a minority of trusted nodes. We proposed three routing algorithms, and evaluate the performance of the E91 QKD protocol when using them for a variety of channel and network configurations. We discuss general lessons that can be drawn from our results, including the importance of not only the inclusion of trusted nodes, but also their placement, and some general limitations inherent to working with such networks.  Note that our approach can also be used to determine network resources needed to achieve desired rates between users at given distances or with given repeater quality.  Our work in this paper can  serve as a baseline for future exploration of this area, and we leave open as future work issues such as the development of better local and global algorithms; analysis of mutli-party networks of this form; analysis of more complicated, potentially asymmetric networks; analytic results regarding the capabilities of these networks; the possibility of embedding Alice and Bob as part of a larger network, rather than at the corners; as well as the extension of this analysis to additional QKD protocols.

\balance
\bibliographystyle{ieeetr}

\section{Model and Simulator}\label{sec:model}

In this work we consider a grid network consisting of $N\times N$ nodes with each node connected to at most four others, their immediate neighbors up, down, left, and right.  These connections represent fiber links allowing for the direct transmission of qubits between neighboring nodes only.  We assume a classical communication network allowing any pair of nodes to send classical messages.  We do not assume this communication is secret; however for all user and trusted node communication we do assume it is authenticated.  Each node in this network may be either a User (Alice or Bob); a Trusted Node; or a Quantum Repeater.  We place Alice at the lower-left corner of the network and Bob in the upper-right (thus, these users have only two neighbors they are connected to).  Later, we will simulate alternative numbers and locations of the trusted nodes; however, predominately the other nodes will consist of quantum repeaters in contrast to current day QKD networks.

\triplefig{stage1.pdf}{Initial network}{stage2.pdf}{Stage 1}{stage3.pdf}{Stage 2}{(a) The initial network of a $5\times5$ grid, with a central trusted node ($T$) between Alice ($A$) and Bob ($B$). (b) A possible network configuration after stage 1, in which some nodes succeed in establishing a shared state of the form in Equation (\ref{eq:shared-state0}) with their neighbors over the fiber channels and some do not.
(c) Successful entanglement chaining and routing (depicted as the ``internal links'' at repeaters) as discussed in Stage 2. In this graph, routing has resulted in end-to-end paths being created between each pair of $A$, $B$ and $T$. These routes are successful only if every Bell state measurement along the path succeeds. Furthermore, the probability of decoherence increases with the path length in our model as discussed; thus minimizing the path lengths through effective routing algorithms and trusted nodes is advantageous.  See also Figure \ref{fig:guide}.}{stages1-3}

\begin{figure}
    \centering
    \includegraphics{sideguide.pdf}
    \caption{A legend for our network diagrams. Left: (a) denotes a node in the network, specifically a repeater with 4 (b) connection terminals from which entangled photons are sent and received over (c) fiber optic connections between other repeaters and (d) trusted nodes. Right: an entangled channel (e) connecting multiple trusted nodes through intra-node entanglement (f).}
    \label{fig:guide}
\end{figure}

Users and trusted nodes perform the E91 QKD protocol.  For notation, we assume there are $n$ trusted nodes denoted $T_1, \ldots, T_n$.  We label Alice as $T_0$ and Bob as $T_{n+1}$.  For every pair of users and trusted nodes there exists a private raw-key pool; that is, for every $i,j \in \{0,\cdots, n+1\}$, with $i < j$, there exists a buffer $\mathcal{RK}_{i,j}$, storing the raw key shared between nodes $T_i$ and $T_j$.  Note that repeaters do not have key buffers.  As we are using the entanglement based E91 protocol, the first goal of the network is to establish joint entanglement between these pairs of nodes $T_i$ and $T_j$, ideally the Bell state $\ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$.  This resource may be used to establish a secret key between users.

The quantum network we analyze operates in {\em rounds}, each round consisting of {\em three primary stages} (see examples in Figures \ref{fig:stages1-3} and \ref{fig:guide}).  The first stage, and part of the second stage, are standard in repeater-only quantum networks (see \cite{pant2019routing,chakraborty2019distributed}). As mentioned, nodes have at most four inputs into them (since the two users are at the corner of grid, they each only have two inputs); we assume that nodes have the capability of storing a single qubit in short-term memory for each of these inputs, through one complete round.  After the round is complete, any qubits not measured, are discarded.  That is, the memory capabilities of nodes are not sufficient to store a qubit through two or more rounds in our network.  Note that users in our network have the fewest demands on quantum memory.

In the first stage, adjacent nodes attempt to share an entangled pair, in particular the Bell state $\ket{\Phi^+}$, with one particle remaining at a local node and the other being transmitted to an adjacent node.  Due to fiber loss, this succeeds with a certain probability $p = 10^{-\alpha L/10}$ where $\alpha$ is the fiber attenuation coefficient (we use $\alpha = .15$ in our later simulations).  Furthermore, even if successful, the entangled pair may not be a Bell state $\ket{\Phi^+}$ but instead will, with probability $D$, depolarize and become completely mixed.  Ultimately, after this first stage, adjacent nodes $u$ and $v$ will either not have any qubit in their short-term memory (with probability $1-p$) or, with probability $p$, they will share a quantum state of the form:
\begin{equation}\label{eq:shared-state0}
\rho_{u,v} = (1-D)\kb{\Phi^+} + D \cdot \frac{I}{4},
\end{equation}
where $I$ is the identity operator on two qubits.  Note this $D$ may be used to model channel noise along with noise internal to the quantum memory of the repeater.  As is standard in repeater-network analyses \cite{pant2019routing,chakraborty2019distributed}, we assume that nodes are able to determine whether a qubit has arrived in their short-term quantum memory or if it is a vacuum.

In the second stage, a routing protocol, to be discussed (see Section~\ref{sec:routing}), is performed to decide how to
effectively route entanglement between nodes $T_i$ and $T_j$ for $i \ne j$.  This routing protocol can take into account whether nodes have a qubit in their short-term memory.  The goal of this stage, and in particular the routing algorithm, is to determine a set of paths, the end-points of which are either users or trusted nodes, while the interior nodes of each path are quantum repeaters.  Given these paths, the quantum repeaters will perform entanglement swapping operations on the qubits that are locally held in their short-term memory, which, if successful, create ``virtual'' entangled links between the end-points of each path.
The entanglement swapping operations at the repeaters, which themselves consist of Bell measurements, succeed only with a certain probability that we denote as $B$.  We assume the network is able to determine whether a successful entanglement swapping occurred or not.  Thus, at the end of this stage, end-nodes $T_i$ and $T_j$ on each path can determine whether the network was successful in creating an end-to-end  path between these nodes.  Note that they cannot tell if the state they share is the correct Bell state $\ket{\Phi^+}$ or the completely mixed state $I/4$ due to depolarization.  At this point, repeaters are no longer needed until the next round, and users and trusted nodes share a state of the form in Equation (\ref{eq:shared-state}), where the probabilities of the mixed state depend on $D$ and the path length -- in particular, on a path consisting of $k$ interior nodes, the shared state will either be:
\begin{equation}\label{eq:shared-state}
\rho_{T_iT_j} = (1-D)^{k+1}\kb{\phi^+} + (1-[1-D]^{k+1})\cdot\frac{I}{4},
\end{equation}
or a vacuum if one or more repeaters failed in their entanglement swapping operation.

Finally, in the third stage, all pairs $T_i$ and $T_j$ of users and trusted nodes which have a shared state, and not a vacuum, attempt to distill a raw-key bit using the E91 QKD protocol.  If successful (which depends on users choosing the correct basis, and as such it is successful with probability $1/2$), the key-bit is added to a local raw key-pool for those users $\mathcal{RK}_{i,j}$.  Any qubit that was not measured by now is discarded and the network repeats at stage 1, attempting to establish fresh entangled pairs between adjacent nodes.  Refer to Figures \ref{fig:stages1-3} and \ref{fig:guide}.

We wrote a custom simulator to simulate the behavior of this network and these three stages.  This simulator maintains a raw-key pool $\mathcal{RK}_{i,j}$ between each pair of users $T_i$ and $T_j$ as would be done in an actual operation of this network.  In practice, nodes $T_i$ and $T_j$ will, once the length of the raw key in $\mathcal{RK}_{i,j}$ is sufficiently large, perform error correction and privacy amplification, leading to a secret key of size $|\mathcal{K}_{i,j}|$.  In our simulations, we are interested in the theoretical performance of this network, and so we only do this process once at the end of the simulation and set $|\mathcal{K}_{i,j}| = |\mathcal{RK}_{i,j}|\cdot (1-2h(Q))$ where $Q$ is the error in the raw key pool $\mathcal{RK}_{i,j}$ and where $h(x)=x\log(x)-(1-x)\log(1-x)$ is the binary entropy function. Again, as we are only interested in theoretical behavior, we compute $Q$ based on the actual simulator data; in practice $Q$ may be estimated by sampling from $\mathcal{RK}_{i,j}$.

Of course, the ultimate goal of the network is to maximize the secret key pool between Alice and Bob (i.e., $T_0$ and $T_{n+1}$).  If $n=0$ (i.e., there is no trusted node), at this point, we are done.  However for $n\ge 1$, a final key-routing process is required of the trusted nodes who must attempt to ``push'' a maximal amount of key material to Alice and Bob.  For $n=1$, this is trivial: $T_1$ will simply broadcast $\mathcal{K}_{0,1}\oplus \mathcal{K}_{1,2}$ (here, $T_0$ is Alice and $T_2$ is Bob); if they are not of equal length, then only the left-portion is broadcast.  Alice and Bob already have a secret key of size $|\mathcal{K}_{0,2}|$ before this process.  Thus, finally, they end up with a secret key of total size $|\mathcal{K}_{0,2}| + \min(|\mathcal{K}_{0,1}|, |\mathcal{K}_{1,2}|)$.  When $n > 1$ the situation is more complicated; in this work we use the max-flow algorithm to determine how many additional bits are appended to $\mathcal{K}_{0,n+1}$.  Note that, at the end, not all key bits in trusted node pools may be usable if there is an insufficient amount of key material in ``matching'' nodes.  Later, when we evaluate performance of our routing protocols, we will look at the key-rate of the network, namely the size of the final secret key between Alice and Bob (after the trusted nodes perform this final key-routing process) divided by the total number of network rounds.

\subsection{Multiple Trusted Nodes} \label{sec:more-trusted-nodes}

\singlefig{TNs.pdf}{A $7\times7$ network with 3 different ways of placing the two trusted nodes. The nodes labeled with $A$ and $B$ are Alice and Bob in each type of placement; the two nodes labeled with $C$ are the trusted nodes in the {\em corner} placement; the two nodes labeled with $D$ are the trusted nodes in the {\em diagonal} placement; and  the two nodes labeled with $R$ are the two trusted nodes in the {\em asymmetric} placement.}{TNPlacement}

\triplefigbig{figs/2TN_g.pdf}{Global}{figs/2TN_IA.pdf}{Intersection Avoidant}{figs/2TN_NIA.pdf}{Non-Intersection Avoidant}{Key rate versus the decoherence rate for the three routing algorithms in a $7\times7$ grid with $L=1$ km and $B=.85$. We consider the No TN case, the Central TN case, and the 2 TN cases in which there are two trusted nodes in the network, following corner, diagonal or asymmetric placements. }{2TNGraphs}

\tydubfigsingle{figs/S_fixed_global.pdf}{Global}{figs/S_fixed_IA.pdf}{Intersection Avoidant}{Key rate versus the network size for the global and IA routing algorithms for a 10 km $\times$ 10 km network grid where the fiber length between each node decreases as the network size increases. Notably, we see some non-monotonicity as the diagonal configuration does not operate effectively at grid sizes that are not of the form $3x+1$ for some integer $x$, and the central case does not operate effectively at even grid sizes such as 10x10. }{FixedLength}

\tydubfigsingle{figs/B_all2E_global}{Global}{figs/B_all2E_IA}{Intersection Avoidant}{Key rate versus the BSM Success rate for the global and IA routing algorithms in a $7\times7$ grid with $L=1$ km and $D=.02$. We consider the no TN case, the central TN case, and the 2 TN cases in which there are two trusted nodes in the network, following corner, diagonal or asymmetric placements.}{2TNGraphsB}

We now consider having two trusted nodes in the network. Specifically, we investigate three methods of placing these two trusted nodes, referred to as {\em corner}, {\em diagonal}, and {\em asymmetric} placements. In the corner placement, the two trusted nodes are located at the two opposite corners of the graph (distinct from Alice and Bob's corners); in the diagonal placement, the two trusted nodes are placed evenly along the diagonal between Alice and Bob; in the asymmetric placement, one trusted node is located in the center, while the other is located one node along the diagonal closer to Alice. Fig.~\ref{fig:TNPlacement} illustrates the above three types of placement for a $7\times7$ grid (we use a $7\times7$ instead of a $5\times5$ grid as the diagonal placement only performs optimally for grid size $N =3x+1$ for some integer $x$).

Figures~\ref{fig:2TNGraphs}(a) through (c) plot the key rate as the decoherence rate increases for each of the above types of placement for the global, IA and NIA routing algorithms, respectively. For comparison, in each figure, the results with a single trusted node placed in the center and no trusted node are also plotted in the figure. We see that for the global routing algorithm (see Fig.~\ref{fig:2TNGraphs}(a)), the diagonal placement outperforms the other four cases (i.e., corner and asymmetric placement of two trusted nodes, as well as no trusted node and placing a single trusted node in the center) by a large margin.

The clustering of the non-diagonal configurations we attribute to two separate reasons. First, consider that in the central configuration, an optimal pathing results in two channels connecting Alice to the trusted node, and two more connecting the trusted node to Bob. Importantly, these channels will consist of 6 edges each. In the corner configuration, an optimal pathing results in one channel between Alice and each of the two trusted nodes, and likewise from Bob to the trusted nodes. Again, these channels will consist of 6 edges each. As a result, at least in the global case, the likelihood that these paths exist, that the channels are successfully established and that the entanglement remains coherent are all equivalent. It stands to reason then, and the data reflects that reasoning, that the corner configuration and the central configuration are equivalent, in terms of performance. In the other case, it is the asymmetry that causes the equality. Although the second trusted node does result in Alice and the central trusted node sharing a larger key, the central trusted node and Bob establish no more key-bits than if the second trusted node did not exist. As a result, in the final routing of key material, the overall capacity between Alice and Bob remains unchanged, and so the additional key-bits that Alice and the trusted node were able to establish go unused. Finally, the over-performance of the diagonal configuration is a result, as one would expect, from the further segmentation of the $7 \times 7$ network into 3 distinct sub-networks: between Alice and the first trusted node; the first and second trusted nodes; and finally the second trusted node and Bob. As shown in the figure, this additional trusted node can increase our key rate by almost a factor of 1.5 over the central trusted node configuration.

We repeat the above investigation for the IA algorithm (see Fig.~\ref{fig:2TNGraphs}(b)). Again, we see that the diagonal placement outperforms the others, and that the performance of the corner placement of two trusted nodes is very similar to that when placing a single trusted node in the center. We also see, however, that the redundant trusted node in the asymmetric case results in a large detriment to the key rate, dropping it almost a full .3 key-bits/round. This is likely due to the greedy nature of the routing algorithm -- having an additional node complicates the decision process of the repeaters near both trusted nodes, potentially wasting edges that otherwise could have been utilized in a more effective manner.

The differences in the performance of the different types of placement are even more dramatic for the NIA algorithm in Fig.~\ref{fig:2TNGraphs}(c). For each configuration we see a significant drop in performance, except for the corner placement, which remains relatively consistent with its performance in the other algorithms. This difference can be explained by the fact that that the NIA algorithm does not generally struggle with intersecting paths in the corner case, as the optimal paths themselves tend not to contain many right angles. The effect of this is so great, in fact, that at lower error rates the corner configuration in fact outperforms the diagonal configuration, until the shorter hop-length of the channels in the diagonal configuration becomes the dominating factor in determining key rate.

As physical distance between Alice and Bob increases, one might think that there is benefit to be had by adding additional repeaters and decreasing the distance between nodes themselves. We investigate whether or not this is feasible in Fig.~\ref{fig:FixedLength} in which the physical distance the network spans is fixed at $10$ km $\times$ $10$ km, while the number of nodes in the grid is increased (this is in contrast to our other simulations where the total width of the network was not fixed, but instead, the length and width are both $(N-1)\cdot L$ km). What we see is that the tendency for BSM failure chance and decoherence probability to increase as path sizes increase puts a damper on any benefit that can be achieved through this method. In some scenarios it is likely that there are trade-offs that can be made, depending on the target distance between Alice and Bob, BSM success probabilities, and decoherence probabilities, but evidently there are limitations inherent to trying to augment the key rate using this method.

It is clear, however, that this limitation can be alleviated in part by the addition of trusted nodes. As can be seen in Fig.~\ref{fig:FixedLength}, while the key rate of each configuration decreases as the size increases, even as the fiber length decreases, additional trusted nodes remain effective in boosting the key rate. As a result, it is still possible to increase network size to alleviate fiber length concerns, as long as the number of trusted nodes is also increased.  Additionally,
Fig.~\ref{fig:FixedLength} showcases the way in which non-optimal grid sizes affect key rate for the different TN configurations. Namely, we see that the key rate of the diagonal configuration actually increases between $N=5$ and $N=7$, or $N=9$ and $N=10$, as we move from grid sizes not of the form $3x+1$ to grid sizes of that form. We see the same for the central configuration at the even grid size of $N=10$, where the node is placed slightly off center, and as such actually increases at $N=11$.

Finally, in Fig.~\ref{fig:2TNGraphsB} we consider the performance of the global and IA algorithms on a number of TN configurations as the BSM success probability increases. Again, we see that the general trend is the same between the global and IA algorithms, with the global algorithm outperforming the IA algorithm in each configuration, and especially the asymmetric case. In the diagonal configuration, with perfect quantum repeaters (i.e. $B=1$), both are able to achieve a key rate of more than .45 key-bits/round with 2 TN in the diagonal configuration, and with 1 TN in the center, the IA algorithm and global algorithms achieve key rates of .3 and .33 key-bits/round, respectively.
The above results are notable, because they give some sense of the trends we might expect to see as quantum repeater technology advances. They also show the great benefit to using trusted nodes, even with perfect, ideal, repeaters.

\iffalse
one with the two trusted nodes located at the two opposite corners of the graph (distinct from Alice and Bob's corners), one with the two trusted nodes distributed evenly along the diagonal between Alice and Bob, and one with one trusted node located at the center, and the other located one node along the diagonal closer to Alice. We refer to the above three types of placements as the {\em corner}, {\em diagonal}, and {\em asymmetric} configurations, as illustrated in Fig.~\ref{fig:TNPlacement} for a $7\times7$ grid (we use a $7\times7$ instead of a $5\times5$ grid since the diagonal configuration only performs optimally for grid size $N =3x+1$ for some integer $x$). Fig.~\ref{fig:2TNGraphs} plots the key rate under the these three placements of two trusted nodes. For comparison, the results with a single trusted node placed in the center are also plotted in the figure.

What we find is that, in the global case (as shown in Fig.~\ref{fig:2TNGraphs}(a), the corner, central, and asymmetric configurations perform at essentially the same level, while the diagonal configuration outperforms the others by a large margin. The clustering of the non-diagonal configurations we attribute to two separate reasons. First, consider that in the central configuration, an optimal pathing results in two channels connection Alice to the trusted node, and two more connecting the trusted node to Bob. Importantly, these channels will consist of 6 edges each. In the corner configuration, an optimal pathing results in one channel between Alice and each of the two trusted nodes, and likewise from Bob to the trusted nodes. Again, these channels will consist of 6 edges each. As a result, at least in the global case, the likelihood that these paths exist, that the channels are successfully established and that the entanglement remains coherent are all equivalent. It stands to reason then, and the data reflects that reasoning, that the corner configuration and the central configuration are equivalent, in terms of performance. In the other case, it is the asymmetry that causes the equality. Although the second trusted node does result in Alice and the central trusted node to share a larger key, the central trusted node and Bob establish no more key-bits than if the second trusted node did not exist. As a result, in the final routing of key material, the overall capacity between Alice and Bob remains unchanged, and so the additional key-bits that Alice and the trusted node were able to establish go unused. Finally, the over-performance of the diagonal configuration is a result, as one would expect, from the further segmentation of the 7x7 network into 3 distinct sub-network between Alice and the first trusted node, the first and second trusted nodes, and the second trusted node and Bob. As shown in the figure, this additional trusted node can increase our key rate by almost a factor of 1.5 over the central trusted node configuration.

In the second figure, Fig. ~\ref{fig:2TNGraphs}(b), we repeat this investigation for the Intersection Avoidant algorithm. again we see that the diagonal configuration outperforms the others, and that the corner and central configurations are equivalent. We also see, however, that the redundant trusted node in the asymmetric case results in a large detriment to the key rate, dropping it almost a full .3 key-bits/round. This is likely due to the additional node complicating the decision of repeaters near both nodes, potentially wasting edges that otherwise could have been utilized in an effective manner.

The differences in performance are even more stark when we look at the Non-Intersection Avoidant algorithm in the third chart, Fig~\ref{fig:2TNGraphs}(c). For each configuration we see a significant drop in performance, save for the corner configuration which remains relatively consistent. This difference can be explained by the fact that that the NIA algorithm does not generally struggle with intersecting paths in the corner case, as the optimal paths themselves tend not to contain many right angles. The effect of this is so great, in fact, that at lower error rates the corner configuration in fact outperforms the diagonal configuration, until the shorter hop-length of the channels in the diagonal configuration becomes the dominating factor in determining key rate.
\fi

\subsection{Simulator}
\begin{figure}
    \centering
    \includegraphics{sideguide.pdf}
    \caption{A legend for Figure \#\ref{fig:stages1-3}. (a) denotes a node in the network, specifically a repeater with 4 (b) connection terminals from which entangled photons are sent and received over (c) fiber optic connections between other repeaters and (d) trusted nodes. Below the line, an entangled channel (e) connecting multiple trusted nodes through intra-node entanglement (f)}
    \label{fig:guide}
\end{figure}

\triplefig{stage1.pdf}{Stage 0}{stage2.pdf}{Stage 1}{stage3.pdf}{Stage 2}{(a) The initial network, in a 5x5 grid, with a central trusted node (T) between Alice (A) and Bob (B), as discussed in stage 0. (b) A possible network configuration after stage 1, in which some nodes succeed in establishing a shared EPR pair with their neighbors over the fiber channels and some do not. Note that there are a number of possible paths between A, B and T. (c) Successful entanglement chaining and routing (depicted as the intra-repeater connections) as discussed in stage 2. In this graph, routing has resulted in a channel being created between each pair of A, B and T. These routes are successful and coherent only if every bell state measurement along the path succeeds, and if no decohering occurs in the path, so minimizing the path lengths with effective routing algorithms and trusted node utilization is advantageous. For the purposes of this diagram we condition on the channels remaining coherent, but in practice any could have become decoherent.}{stages1-3}
To analyze the behavior of the QKD network we envision and to evaluate the performance of the various routing protocols we construct later, we wrote a custom simulator.  This simulator, following an initialization stage, operates in four steps, which each  take in as input the state of the network graph at the end of the state prior and outputting the resulting, evolved graph. \par
\textbf{0. Initialization:}
Consider an $N\times N$ (for an odd $N$) network graph with some number of trusted nodes and Alice and Bob at opposite corners of the network, Such a network begins in the state $G = \{V,E\}$ where $V = \{0,1, \dotso,N^2-2, N^2-1\}$ with Alice at node $A=0$ and Bob at node $B = N^2-1$, and trusted nodes $T \subseteq V$. Finally, without loss of generality we consider a grid network in which the nodes are ordered increasing from left to right and bottom to top, and so we have $E$ defined in the natural way. We show the steps describing the evolution of this graph in the following section, as well as the evolution of this example graph in Figs.~\ref{fig:stages1-3} and \ref{fig:stage5}, with a key provided in Fig.~\ref{fig:guide}. \par
\textbf{1. Entanglement Generation:} In the initial phase, each node attempts to share one half of a  Einstein–Podolsky–Rosen (EPR) \cite{EPR} pair with its neighbors over the fiber channel. The photon pair is successfully transmitted and received with probability $10^{-\alpha L/10}$ \cite{transmittance} where $\alpha$, also a characteristic of the network, is the transmittance of the fiber channel. As such the network evolves to $G_1 = \{V, E_1\}$ where $E_1 = \{(u,v) \forall (u,v) \in E  \; |\;  S(u,v) \}$  \OA{what is set notation for random sets?}, where $S(u,v)$ is a random binary function that returns true for any edge with probability $10^{-\alpha L/10}.$ \par
\textbf{2. Routing and Entanglement Chaining: } With the evolved network graph, the repeater nodes utilize a routing algorithm (we will discuss a number of candidate algorithms in the following section) to determine, at each repeater, which neighbors should be connected by entanglement. The routing algorithm, $R1$, takes $G_1$ as input and outputs $P = \{p_i\}_{i=0}^n$ where $p_i = (r_0^i, r_1^i, \dotso, r_{m_i}^i)$ describe paths originating from and ending at Alice, Bob, or a trusted node through a path of $m-2$ entanglement connected quantum repeaters. The quantum repeaters then use this pathing information and conduct bell state measurements on the photons they hold that are entangled with photons at the nodes before and after them in a path \bing{this sentence is a bit long; can we rephrase by using the notation?}, succeeding with probability $B$ and becoming decoherent with probability $D$. As a result of this action, the network evolves and is compromised of Alice, Bob, trusted nodes, and shared entanglement (which with some probability has decohered) between those parties. Specifically, we have $G_2 = \{V_2, E_2\}$ where $V_2 = T\cup \{A,B\}$ and $E_2 = \{(r_0^i,r_{m_i}^i,F(p_i)) \; \forall p_i \in P\}$ where $F(p_i)$ is a random binary function that decides whether or not the entangled channel has fidelity. Fidelity is maintained with probability $(1-d)^{m_i-2}$, as it must be the case that at each of the $m_i-2$ intermediate nodes, the bell state measurement did not fail. We note that as there can be multiple (up to two) paths between the same pair of entities, the elements in $E_2$ are not necessarily unique. \par
\textbf{3. Quantum Key Distribution:} In this stage, the entities in $G_2$ attempt to use the quantum channels established between them to conduct a round of an entanglement based QKD protocol --- in our case, E91. Here we will  introduce a secondary network structure, with weighted edges connecting Alice, Bob, and trusted nodes with weights representing the amount of key material shared between nodes. The edges additionally have associated with them a bit string, with length equal to their weight, representing whether there is a correlation in each bit of key material (though the value of the bits themselves, for the purpose of our simulation, is irrelevant). This graph, at the start of the protocol, is initialized to $G_3 = \{V_2, E_3\}$ where $E_3 = \{(u,v,0,\epsilon) \; \forall u,v \in V_2\},$ where $\epsilon$ is the empty string denoting the correlations in the amount of stored key material, which is 0 \bing{what does the `0' represent here?}.

On this stage, we build on $G_3$ based on the state of $G_2$. Specifically, if QKD succeeds between two linked nodes, which it does with probability $\frac{1}{4},$ then a bit is added to that that bank of key material, which is a correlated with full probability if the link was coherent \bing{rephrase?}. If the link was not coherent, then we assume that it became a fully mixed state, and that resulting measurements are random and therefore correlated with $\frac{1}{2}$ probability. Formally, this means that for each edge $(u,v,1) \in E_2$, with $\frac{1}{4}$ probability we update the corresponding edge $(u,v,k,c)$ in $E_3$ to $(u,v,k+1,c||0)$, and likewise for each edge $(u,v,0)$ we update the corresponding edge to $(u,v,k,c||0)$ or $(u,v,k,c||1)$  with equal probability, where $||$ denotes concatenation of bit strings.

\par
\textbf{4. Key Distillation}
Stages 1-3 repeat some $M$ times, building sufficiently sized key stores between each of the participating parties in our network until, on this stage, the final key-distillation and key-routing process occurs. On this stage, each pair of parties that share some amount of raw key material can conduct standard post-processing procedures, namely, error correction and privacy amplification, to transform their raw-key stores into secret-key stores. As we are limiting our analysis in this work to only consider the performance in the asymptotic key-length realm, we do not consider finite key effects, and so the simulator simply transforms the edges $(u,v,k,c)$ in $G_3$ to be $(u,v,(1-2h(Q))k, \epsilon)$, to signify the error correction and privacy amplification process according to the standard process, where Q is the quantum bit error rate of the key, calculated as $\frac{w(c)}{k}$, where $w(x)$ signifies the Hamming weight of the bit string $x$ and where $h(x)=x\log(x)-(1-x)\log(1-x)$ is the binary entropy function.
Following this process, the network conducts the final routing process on $G_4$, obtained through the above transformations of edges, in an effort to route the maximum amount of key material from Alice to Bob. To do this, we use a standard max-flow algorithm, in which any flow of $n$ key-bits from node $a$ to node $b$ going through node $c$ signifies node $c$ publishing the XOR of $n$ bits from its key stores shared with $a$ and $b$ respectively, and then discarding those $n$ bits. Nodes $a$ and $b$ can then of course recover this key material, pushing it through the network until we culminate with the maximal amount of key material being shared by Alice and Bob.

\begin{figure}
    \centering
    \includegraphics{stage5.pdf}
    \caption{$G_3$ being modified, as discussed in stage 3, where $k_i$ denotes the number of key bits already shared between two nodes, and $c_i$ denotes the correlation bit string. This diagram assumes that QKD was successful on each of the error free channels established in Figure \ref{fig:stages1-3}(c).}
    \label{fig:stage5}
\end{figure}

\subsection{Single Trusted Node} \label{sec:one-trusted-node}
We now consider the scenario where a single trusted node is placed at the center of the network grid, and investigate the impact of various parameters on key rate in this scenario. Figures~\ref{fig:1TNGraphs}(a)-(d) plot the key rate when varying the fiber length, decoherence rate, BSM success rate and network size, respectively. The results show that, under all three routing algorithms, having one trusted node leads to significantly higher key rate than the same setting with no trusted node (see Fig.~\ref{fig:NoTNGraphs}).
As an example, when there is no trusted node, as shown in Fig.~\ref{fig:NoTNGraphs}(a), the maximal key rate achieved for the global algorithm was .07 key-bits/round, while it is .3 key-bits/round, more than $3\times$ higher, as shown in Fig.~\ref{fig:1TNGraphs}(a) when there is one trusted node.

Comparing Fig.~\ref{fig:1TNGraphs}(a) and Fig.~\ref{fig:NoTNGraphs}(a), we see that for the global algorithm,  when varying the fiber length from 1 to 15 km, the key rates with one trusted node are $.08$-$.25$
higher than that with no trusted node under the same setting, corresponding to a $1.9$-$4.4\times$ increase; the corresponding increases in key rate for IA and NIA algorithms are $1.2$-$8.8\times$ and $2.1$ - $9.2\times$, respectively.
In fact, with one trusted node and in the same setting, the NIA algorithm achieves greater key rates than even the global algorithm could with no trusted nodes. This is because the trusted node essentially reduces the ``size'' of the network, allowing shorter paths to be constructed between Alice/Bob and the trusted node, As the local algorithms have information on a higher fraction of the total network for smaller networks, this reduction in the effective size of the network has a particularly strong effect on the local algorithms.
\iffalse
With a baseline set, we now move to consider what one can do by adding a single trusted node to the network. Specifically, we repeat the host of simulations discussed previously, now with a trusted node located at the center of the network grid. What we find is that, while trends between parameters, algorithms, and key rate all remain constant, in every case the key rate is greatly increased by the addition the trusted node. Contrasting each of the sub-figures in Fig.~\ref{fig:1TNGraphs} with their respective counterparts in Fig.~\ref{fig:NoTNGraphs}, this increase in evident. Where, in Fig.~\ref{fig:NoTNGraphs}(a) the maximal key rate achieved for the global algorithm was .07 key-bits/round, in Fig.~\ref{fig:1TNGraphs}(a) it is more than threefold that at .3 key-bits/round. In fact, with one trusted node the NIA algorithm achieves greater key-rates than even the global algorithm could with no trusted nodes.
\fi
This trend is also exhibited in Figs.~\ref{fig:1TNGraphs}(b)-(d). Where, again comparing with their counterparts in Fig.~\ref{fig:NoTNGraphs}, we see that the addition of a trusted node results in an almost two-fold increase in maximum achievable key-rate for the cases of decoherence, BSM success rate and network size.

\iffalse Interestingly, we see that the difference in performance between the global and IA algorithms becomes less pronounced in these cases, while it was not the case in the results when varying the fiber length as shown in Fig.~\ref{fig:1TNGraphs}(a). This is likely due to the fact that, when varying fiber length, the global algorithm is able to find longer paths that the local algorithms cannot find as the length (and therefore edge-sparsity) increases. On the other hand, when varying decoherence, BSM rate or network size, the optimal paths remain easy to find. And, as they are in general shorter (and therefore easier to find) when they are between Alice/Bob and a trusted node than when they are simply between Alice and Bob (i.e., when there is no trusted node), the difference between the global and IA algorithm is, understandably, less. \OA{This doesn't actually look to be true, or i'm confused by what I meant}
\fi

In Fig.~\ref{fig:NoiseLevels}, we show the performance of the three algorithms with no trusted nodes and one trusted node in two additional channel scenarios: perfect BSM success probability with 2\% decoherence and 85\% BSM success probability with 5\% decoherence. In  Fig.~\ref{fig:NoiseLevels}(a), we see that even with the elimination of BSM failures, as the length increases between nodes the key rate still drops significantly. We see that even the NIA algorithm with a central trusted node (TN) outperforms the global algorithm with no TN, as the shorter paths between the parties and the TN are simply more likely to exist than the longer paths that must exist to connect Alice and Bob in the no TN case. In  Fig.~\ref{fig:NoiseLevels}(b) we consider a less idealized scenario, in which the BSM probability is our default of $85\%$ and our decoherence rate is higher, at $5\%$. We see that for this scenario, not even the global algorithm can achieve a positive key rate for the no TN case (at least in $10^6$ rounds of the network), and that in general the key rates achieved by the central TN is significantly lower (between $5-10\times$) than was achieved with $2\%$ decoherence in Fig.~\ref{fig:1TNGraphs}(a). It is notable, however, that in Fig.~\ref{fig:NoiseLevels}(b) we see that using 1 TN, each algorithm is able to maintain a positive key rate even when there is a 5\% decoherence rate, and Alice and Bob  are separated by 113 km (when $L=20$ km, considering a $5\times5$ network grid).

\tydubfigsingle{figs/L_01_5x5.pdf}{100\% BSM Success Prob.}{figs/E5_1TN.pdf}{5\% decoherence rate}{(a) The capabilities of the network when operating in an idealized scenario with no BSM failures (i.e. perfect repeaters) and 2\% decoherence probability. (b) The capabilities of the network with 5\% decoherence probability and 85\% BSM success probability.}{NoiseLevels}

\section{Performance Evaluation} \label{sec:perf}

In this section, we evaluate the performance of quantum key distribution in quantum networks using the various routing algorithms. We will compare the performance of the algorithms in a number of settings and investigate the impact of various parameters on the performance.

\subsection{Evaluation Setup}
We consider the scenarios where Alice and Bob are placed at the two corners of an $N\times N$ grid.
The parameters related to network topology include the size of the grid ($N$) and the length of the fiber channel of each edge (horizontal or vertical) of the grid ($L$). The quality of the quantum network is represented by the probability of a successful Bell state measurement (BSM) at a repeater ($B$), and the probability of decoherence ($D$, see Equation \ref{eq:shared-state}).   Note that $L$ is the fiber length between neighboring two nodes.  Since Alice and Bob are at opposite corners of the entire grid network, the actual distance, therefore, between the two users is actually $\sqrt{2}(N-1) L$.
Table~\ref{tab:defaults} summarizes these parameters, with their default values and range of the values.

\begin{table}
    \centering

    \caption{Parameters explored in performance evaluation. }
        \begin{tabular}{| c | c | c | p{3.8cm}|}
        \hline
        \textbf{Parameter} &  \textbf{Default} & \textbf{Range} & \textbf{Description} \\ \hline
        $N$ & 5    & 5 - 15       & The network consists of $N^2$ nodes arranged in an $N \times N$ grid. \\ \hline
        $L$ & 1 km & 1 - 20 km & The length of the fiber connecting neighboring nodes. The distance between Alice and Bob scales with both $N$ and $L$.  \\ \hline
        $B$ & .85  & 0.65 - 1.00  & Represents the quality of the repeaters. A Bell state measurement succeeds at a repeater with probability $B$. \\ \hline
        $D$ & .02  & 0.00 - 0.06  & Represents the amount of noise in the channels. EPR pairs decohere with probability $D$. \\
        \hline
        \end{tabular}
    \label{tab:defaults}
\end{table}

The performance metric is {\em key rate}, i.e., the average number of secret key-bits generated between Alice and Bob per round of network use as discussed in Section \ref{sec:model}. Unless otherwise stated, the number of rounds we simulate for each test and for each setting is $10^6$. We also evaluate the network's performance when there are no trusted nodes; a single trusted node; and two trusted nodes, along with different location configurations.

\subsection{No Trusted Nodes}

\begin{figure}[t]
	\centering

	\subfigure[Impact of fiber length.]
		\includegraphics[width=0.24\textwidth]{figs/L_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Impact of decoherence rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/E_noTN.pdf}
	} \\

	\subfigure[Impact of BSM success rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/Q_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Impact of network size.]{%
		\includegraphics[width=0.24\textwidth]{figs/S_noTN.pdf}
	}

	\caption{Impact of various parameters on key rate when there is no trusted node in the network ($5 \times 5$ grid). Note, as discussed, ``fiber length'' $L$ is the length between nodes.  Thus, the actual distance between the two users is actually $\sqrt{2}(N-1) L$.}
	\label{fig:NoTNGraphs}
\end{figure}

\iffalse
\begin{figure}[t]
	\centering

	\subfigure[Key rate vs. fiber length.]
		\includegraphics[width=0.24\textwidth]{figs/L_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Key rate vs. decoherence rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/E_noTN.pdf}
	} \\

	\subfigure[Key rate vs. BSM success rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/Q_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Key rate vs. network size.]{%
		\includegraphics[width=0.24\textwidth]{figs/S_noTN.pdf}
	}

	\caption{Impact of various parameters on key rate when there is no trusted node in the network ($5 \times 5$ grid).}
	\label{fig:NoTNGraphs}
\end{figure}
\fi

We first investigate the scenario with no trusted node and only repeaters. These results serve as baselines to demonstrate the benefits of having trusted nodes in the network in Sections~\ref{sec:one-trusted-node} and \ref{sec:more-trusted-nodes}. Fig.~\ref{fig:NoTNGraphs}(a) plots the key rate when varying the fiber length, $L$, for a $5 \times 5$ grid. The results of the three routing algorithms are plotted in the figure. As expected, since increasing the fiber length leads to higher fiber loss, the key rate decreases with $L$. The global routing algorithm, also as expected, outperforms the two local algorithms. Between the two local algorithms, the intersection-avoidance (IA) algorithm significantly outperforms non-intersection-avoidance (NIA) algorithm, particularly for lower fiber lengths.
The difference between the global algorithm and IA algorithm is small for short fiber length, and increases when the fiber length increases, where having global knowledge allows the algorithm to find paths, even when they are longer and more complicated.

Fig.~\ref{fig:NoTNGraphs}(b) plots key rate when increasing the decoherence rate $D$. We again observe that the global routing algorithm outperforms the two local algorithms, and the IA algorithm significantly outperforms the NIA algorithm.
As expected, increasing the decoherence rate leads to lower key rates; the decrease is particularly dramatic when increasing the decoherence rate from 0 to 2\%. As an example, for the global routing algorithm, the key rate decreases from .3 key-bits/round to just over .07 key-bits/round when increasing the decoherence rate from 0 to 2\%.
We also note that, interestingly, while both the global and IA algorithms achieve a key rate around .07 at 2\% decoherence, the NIA algorithms, under the ideal condition of 0\% decoherence, achieves the same key rate of .07 key-bits/round.
The drastic advantage of the IA algorithm over the NIA algorithm highlights the importance of designing effective local routing algorithms.

Fig.~\ref{fig:NoTNGraphs}(c) plots key rate when varying $B$, the probability that the Bell state measurement at a repeater succeeds. The relative performance across the three routing algorithms is similar as the above two scenarios.
Of note, it is evident
that increasing the reliability of these measurements can lead to a significantly improved key rate. At a 75\% success rate, for example, the global algorithm achieves just under .026 key-bits/second, but an increase to 95\% or even 100\% success rates allows us to achieve key rates of approximately .153 and .216 respectively.

Last, Fig.~\ref{fig:NoTNGraphs}(d) demonstrates the impact of network size $N$ on key rate.  Note that, by increasing $N$ (the number of nodes in the network) but keeping the horizontal/vertical distance between two adjacent nodes fixed at 1 km, we are effectively increasing the total distance between Alice and Bob (they are at the two corners of the grid). For all the routing algorithms, the key rate decreases when the network size (i.e., total distance) increases. This is expected since, as the network size increases, the path between Alice and Bob becomes longer,
and therefore the overall error (see Equation \ref{eq:shared-state}) and probability of a path failing increases, leading to lower key rate. Of the three routing algorithms, the global algorithm is less affected compared with the other two algorithms since it is more capable of finding longer paths as the network size increases than the two local algorithms.

We observe that, as the distance between the end users $A$ and $B$ increases, even using quantum repeaters with perfect internal performance (i.e., $B = 1$), the efficiency of the entire network degrades rapidly (we shall discuss this further in in Fig.~\ref{fig:NoiseLevels}).  We show in the following sections how even a single trusted node can dramatically improve the performance of QKD, indicating that, even in the future as repeater technology becomes more prevalent, trusted nodes may still be necessary to ensure high key rate when the distance between end users is significant.

\input{one-trusted-node}

\input{more-trusted-node}

\subsection{Routing with Global Information}

The first routing algorithm makes use of global link level information, such that on each iteration the repeaters know which connections in the network have succeeded and which have failed. Towards this end, inspired by (CITE) for entanglement distribution, we propose a greedy algorithm which attempts to ensure that the shortest possible paths between trusted nodes are utilized, maximizing the probability that successful connections are established, and minimizing the expected error rate of those connections. To do this it simply outputs the shortest path between any two parties (choosing randomly between paths of equal length), removes those edges from the graph, and repeats until there are no new paths remaining. We will note here this in this work we do not make any claims to the optimality of this or the later routing algorithms we will discuss, we simply analyze their performance. \iffalse The psuedocode for this algorithm is provided in \ref{alg:global}.

\begin{algorithm}[H]
    \caption{Global Algorithm:}
	\begin{algorithmic}[1]
	\State Let $G$ be the network state, $T$ be the set of trusted nodes, and $A$,$B$ be the nodes at which Alice and Bob are located.
	\State Let $sp_G(u,v)$ be a routine that returns the shortest path in $G$ between nodes $u$ and $v$.
	\State Let $P = \{(t_1,t_2)\; \forall t_1,t_2 \in (T\cup \{A,B\})\;  | \; t_1>t_2\}$
	\State Let $x \overset{\$}{\leftarrow} A$ denote selecting an element $x$ from set $A$ with uniform probability.
	\While{True}
	    \State Let $S = \{sp_G(t_1,t_2) \; \forall (t_1,t_2) \in P\}$
	    \If{$S == \emptyset$}
	        \State Break.
	    \EndIf
	    \State Let $m_s = \underset{s \in S}{min} \; length(s)$.
	    \State Let $M = \{s \; \forall s \in S \; |  \;  length(s) == m_s\}$.
	    \State Let $p \overset{\$}{\leftarrow} M$.
	    \State Remove edges in $p$ from $G$.
	    \State Output path $p$ as a path to be attempted.
	 \EndWhile
    \end{algorithmic}
    \label{alg:global}
\end{algorithm}
\fi

Allowing the network to route with global network information is beneficial, but it is also impractical. Without perfect quantum memories, it is infeasible to store the entangled qubits at each repeater for a sufficiently long period of time to propagate network information to each repeater in the network --- even with perfect memories, the propagation would increase the complexity and latency of the network. The global algorithm still serves as a useful benchmark to compare with other algorithms that only utilize local link information.

\subsection{Routing with Local Information}

We analyze two such algorithms, closely related, in this work. The first algorithm is adapted from the local routing algorithm proposed in \cite{pant2019routing}, in which they solve a similar routing problem which for networks that do not include a concept of trusted nodes. Our extension of their algorithm, then, operates as follows:

Each repeater knows the number of hops each neighbor is from Alice, Bob, or a trusted node in the network (though, unlike the global algorithm, they do not know if all those links share an entanglement of course). On a given iteration, each repeater (only repeaters take action in this stage) will check how many of its four immediate neighbors it shares a quantum state with (of the form in Equation \ref{eq:shared-state}. If it connected with fewer than two: it does nothing (as it is only a ``dead-end''); if it connected with two neighboring nodes, it simply connects the two. If a repeater has established a quantum state with more than two of its neighbors, it connects the two neighbors that have the shortest distance (in terms of hops in the network) to two unique end-users (by which we mean Alice, Bob, or trusted nodes, and which have a distance of 0 from themselves). This is in an effort to ensure that the path consisting of two end-users is the shortest possible path between them, without the advantage of having global information. In the case when two potential sets of connections are equal in distance, the algorithm chooses randomly between them in the interests of symmetry.  Following this, if there remain two neighbors that have not been utilized (i.e., this node established a quantum state with all four of its neighbors initially), the repeater connects the remaining two neighbors. We call this the \emph{Non-Intersection Avoidant (NIA)} algorithm (the choice of name will become clear momentarily).

Our second proposed local routing algorithm operates similar to the first NIA, but with a single modification to one of the rules which, we will come to see later, has a tremendous effect on performance.  In the case that a repeater must choose between two sets of potential connections (that is, the repeater has established a quantum state with three or four of its neighbors), we bias towards connections that do not create a right-angle in the network graph, in favor of connections between nodes that are "in line" with each other. This has the effect of simplifying the paths that are created in our graph, and limiting the number of times one path utilizes an edge that was integral to the formation of another path, but not to the formation of itself. We call this second local algorithm "Intersection Avoidant" (IA).

In Fig. ~\ref{fig:Routing}, we show the resulting routes as chosen be each of the three algorithms, operating on the same set of EPR pairs. In Fig. ~\ref{fig:Routing}(a), the NIA algorithm makes two non-optimal decisions, at locations (i) ad (ii). At location (i), the repeater attempts to connect node A (as that node has a minimum distance of 0 from a party node, itself) with one of the other two neighbors of node (i). Each of the neighbors are equally close to the closest unique party node, and so the NIA selects one at random. In our example, the algorithm chooses to connect the neighbor to the right. While the algorithm still manages to connect A and T, this decision has two negative impacts. First, it renders a possible path between A and T beginning to the right of A useless, wasting those EPR pairs. At the same time, it also cuts off the any paths between A and B or T that go through nodes above (i). In (b), we see that this is remedied. Because the IA algorithm chooses "straight" paths when faced with two otherwise equal paths, node (i) makes the correct decision to path upwards, allowing that path to continue to node (ii), and the path to the right of A to still connect A and T. Unfortunately, both local algorithms can still make an incorrect choice at node (ii). Here,  the node can choose to connect two of the nodes below it, to the left, and to the right, Each of the options are valid, and so again the local algorithms choose randomly between them. In (b), the IA algorithm chooses to connect the bottom and right nodes at (ii), which does not complete the possible path between A and B. This would also be true if it connected the left and right nodes, as was done in (a). Conversely, the global algorithm in (c) makes the correct choice at both node (i), and node (ii), as it has global link information and always chooses the shortest possible path.

\section{Routing Protocols} \label{sec:routing}
In this section, we present three routing protocols that are used to form end-to-end paths for the second stage in a round.
These end-to-end paths have either users or trusted nodes as end nodes and have quantum repeaters as intermediary nodes.
We first present a high-level overview of these three protocols, and then describe each in detail.

\subsection{High-level Overview}
\iffalse
The three routing protocols are designed to (i) find short paths, and (ii) find as many paths as possible, so that these paths can lead to higher chances of shared state (see Equation (\ref{eq:shared-state})) and can be used in aggregation to lead to more key bits.
\fi
The three routing protocols are designed to (i) find short paths so that these paths can lead to higher chances of shared state (see Equation (\ref{eq:shared-state})), and (ii) find as many paths as possible to leverage the significant benefits of multipath routing over single-path routing~\cite{pirandola2016capacities,pirandola2019end} to lead to more key bits.

One of the three protocols relies on {\em global} link-state information, i.e., each node has the full knowledge of the external links in the network (i.e., the entanglement between pair of nodes that were created successfully in the first stage in a round). The other two protocols only require {\em local} link-state information, i.e., a node only knows
which neighbors it shares a quantum state with and knows nothing beyond its neighbors.
The network topology (including the locations of the users and the trusted nodes) is known for all protocols.  With the global knowledge, the global routing protocol is more likely to find better paths than the local routing protocols. On the other hand, gathering global information incurs longer latency since the link state information has to be propagated throughout the  network, while local link-state information is already available at the end of the first stage, and thus incurs no additional latency. As a result, the global routing protocol may only be applicable to small networks, while the local routing protocols can also be used in large networks.

Our routing protocols are inspired by work in \cite{pirandola2019end,pant2019routing}, where the authors consider routing between a pair of end users, without leveraging trusted nodes. We extend them to the scenarios with trusted nodes.
Of the two local routing protocols we develop, one significantly outperforms the other (see Section~\ref{sec:perf}), which can also be applied to scenarios with no trusted nodes in \cite{pant2019routing}.

\subsection{Global Routing Protocol}
The global routing protocol selects the shortest path (in hops) between any pair of nodes in $\{T_0, T_1,\ldots,T_{n+1}\}$, where $T_0$ is Alice, $T_{n+1}$ is Bob, and $T_1,\dots,T_n$ are trusted nodes. When two paths of equal length are found, one of them is selected randomly. Then all the links along the path are removed, and the procedure repeats for the remaining links until no path can be found. Fig.~\ref{fig:Routing}(a) illustrates this algorithm. In this example, there is only a single trusted node $T$ in the center of the network. The first shortest path found is the path (of 4 hops) between Bob and the trusted node $T$. After the links along this path are removed, the second shortest path (of 4 hops) found is the path between Alice and $T$. After that, a path (of 8 hops) between Alice and Bob is found.

\subsection{Local Routing Protocols}
The two local routing protocols are closely related. In both algorithms, each repeater makes its own decisions on forming an ``internal link'' (i.e., performing  entanglement  swapping on two qubits in its short-term memory). We next describe the action at an arbitrary repeater $u$. For ease of exposition, we assume there is only a single trusted node $T$ in the network (the description below can be extended easily to multiple trusted nodes). Furthermore, without loss of generality, we assume $u$ has four neighbors, denoted as $u_a$, $u_b$, $u_l$ and $u_r$, corresponding to the nodes that are above, below, to the left of, and to the right of $u$, respectively. Let $D_A(u_a)$, $D_B(u_a)$ and $D_T(u_a)$ denote the distance (in hops) from $u_a$ to Alice, Bob and trusted node $T$, respectively. Similarly, define the distances for $u$'s other neighbors.
Since each node knows the network topology, all the above distance values of $u$'s neighbors are known to $u$, which are used in $u$'s decision making. Specifically, in a given round, $u$ checks how many neighbors it shares quantum state with. If it shares quantum state with fewer than two neighbors, then it does nothing (i.e., no ``internal link'' can be created). If it shares quantum state with exactly two neighbors, it simply connects these two neighbors. Otherwise (i.e., it shares quantum state with more than two neighbors), it connects the two neighbors that have the shortest distances to two unique nodes including Alice, Bob and the trusted node. Afterwards, if there still remain two neighbors that $u$ shares quantum state with (i.e., $u$ established a quantum state with all four of its neighbors), then $u$ connects these two remaining neighbors.

The two local routing algorithms only differ in how they deal with ties. Specifically, if two potential sets of connections are equal in distance, the first local algorithm breaks the tie randomly, while the second algorithm favors horizontal or vertical ``internal links'', which has the effect of simplifying the paths that are created, and limiting the number of times one path utilizes a link that is integral to the formation of another path (see example below). We refer to the first local routing algorithm as \emph{Non-Intersection Avoidant (NIA)} algorithm, while we refer to the second one as \emph{Intersection Avoidant (IA)} algorithm. While these two algorithms only differ slightly, our simulation results in Section~\ref{sec:perf} demonstrate that the IA algorithm can significantly outperform the NIA algorithm. In fact, the performance of the IA algorithm approaches that of the global algorithm in some scenarios.

Fig.~\ref{fig:Routing}(b) illustrates the NIA algorithm. In the example, the algorithm finds two paths, one between Alice and the trusted node $T$, and the other between Bob and $T$. At location (i), the repeater attempts to connect node $A$ (which has a minimum distance of 0 from Alice) with one of the other two neighbors, which have equal distance to the trusted node $T$. The algorithm selects one at random, which happens to be the neighbor to its right. While this ``internal link'' becomes part of a path from $A$ to $T$, it has a negative impact in that it cuts off any paths between Alice and Bob (or between Alice and $T$) that go through the nodes above (i). The above problem does not happen in the IA algorithm (see Fig.~\ref{fig:Routing}(c)), where the repeater at location (i) connects  the node above with node $A$, leading to a vertical ``internal link'', which becomes part of the longer path leading to Bob while another path is established to connect Alice with $T$. In summary, in this example the IA algorithm is able to establish a path between Alice and $T$, Bob and $T$, and a link between Alice and Bob, just as the global algorithm does, while the NIA algorithm lacks the logic to enforce this outcome. Our large-scale simulation in Section~\ref{sec:perf} demonstrates that the IA algorithm leads to statistically
better performance than the NIA algorithm.

\iffalse The psuedocode for this algorithm is provided in \ref{alg:global}.

\begin{algorithm}[H]
    \caption{Global Algorithm:}
	\begin{algorithmic}[1]
	\State Let $G$ be the network state, $T$ be the set of trusted nodes, and $A$,$B$ be the nodes at which Alice and Bob are located.
	\State Let $sp_G(u,v)$ be a routine that returns the shortest path in $G$ between nodes $u$ and $v$.
	\State Let $P = \{(t_1,t_2)\; \forall t_1,t_2 \in (T\cup \{A,B\})\;  | \; t_1>t_2\}$
	\State Let $x \overset{\$}{\leftarrow} A$ denote selecting an element $x$ from set $A$ with uniform probability.
	\While{True}
	    \State Let $S = \{sp_G(t_1,t_2) \; \forall (t_1,t_2) \in P\}$
	    \If{$S == \emptyset$}
	        \State Break.
	    \EndIf
	    \State Let $m_s = \underset{s \in S}{min} \; length(s)$.
	    \State Let $M = \{s \; \forall s \in S \; |  \;  length(s) == m_s\}$.
	    \State Let $p \overset{\$}{\leftarrow} M$.
	    \State Remove edges in $p$ from $G$.
	    \State Output path $p$ as a path to be attempted.
	 \EndWhile
    \end{algorithmic}
    \label{alg:global}
\end{algorithm}
\fi

\iffalse
\subsection{Routing with Local Information}

We analyze two such algorithms, closely related, in this work. The first algorithm is adapted from the local routing algorithm proposed in \cite{pant2019routing}, in which they solve a similar routing problem which for networks that do not include a concept of trusted nodes. Our extension of their algorithm, then, operates as follows:

Each repeater knows the number of hops each neighbor is from Alice, Bob, or a trusted node in the network (though, unlike the global algorithm, they do not know if all those links share an entanglement of course). On a given round, each repeater (only repeaters take action in this stage) will check how many of its four immediate neighbors it shares a quantum state with (of the form in Equation \ref{eq:shared-state}. If it connected with fewer than two: it does nothing (as it is only a ``dead-end''); if it connected with two neighboring nodes, it simply connects the two. If a repeater has established a quantum state with more than two of its neighbors, it connects the two neighbors that have the shortest distance (in terms of hops in the network) to two unique end-users (by which we mean Alice, Bob, or trusted nodes, and which have a distance of 0 from themselves \WK{What does this mean 0 from themselves?}). This is in an effort to ensure that the path consisting of two end-users is the shortest possible path between them, without the advantage of having global information. In the case when two potential sets of connections are equal in distance, the algorithm chooses randomly between them in the interests of symmetry.  Following this, if there remain two neighbors that have not been utilized (i.e., this node established a quantum state with all four of its neighbors initially), the repeater connects the remaining two neighbors. We call this the \emph{Non-Intersection Avoidant (NIA)} algorithm (the choice of name will become clear momentarily).

Our second proposed local routing algorithm operates similar to the first NIA, but with a single modification to one of the rules which, we will come to see later, has a tremendous effect on performance.  In the case that a repeater must choose between two sets of potential connections (that is, the repeater has established a quantum state with three or four of its neighbors), we bias towards connections that do not create a right-angle in the network graph, in favor of connections between nodes that are "in line" with each other. This has the effect of simplifying the paths that are created in our graph, and limiting the number of times one path utilizes an edge that was integral to the formation of another path, but not to the formation of itself. We call this second local algorithm "Intersection Avoidant" (IA).

In Fig. ~\ref{fig:Routing}, we show the resulting routes as chosen be each of the three algorithms, operating on the same set of EPR pairs. In Fig. ~\ref{fig:Routing}(a), the NIA algorithm makes two non-optimal decisions, at locations (i) ad (ii). At location (i), the repeater attempts to connect node A (as that node has a minimum distance of 0 from a party node, itself) with one of the other two neighbors of node (i). Each of the neighbors are equally close to the closest unique party node, \WK{What is a party node?} and so the NIA selects one at random. In our example, the algorithm chooses to connect the neighbor to the right. While the algorithm still manages to connect A and T, this decision has two negative impacts. First, it renders a possible path between A and T beginning to the right of A useless, wasting those EPR pairs. At the same time, it also cuts off the any paths between A and B or T that go through nodes above (i). In (b), we see that this is remedied. Because the IA algorithm chooses "straight" paths when faced with two otherwise equal paths, node (i) makes the correct decision to path upwards, allowing that path to continue to node (ii), and the path to the right of A to still connect A and T. Unfortunately, both local algorithms can still make an incorrect choice at node (ii). Here,  the node can choose to connect two of the nodes below it, to the left, and to the right, Each of the options are valid, and so again the local algorithms choose randomly between them. In (b), the IA algorithm chooses to connect the bottom and right nodes at (ii), which does not complete the possible path between A and B. This would also be true if it connected the left and right nodes, as was done in (a). Conversely, the global algorithm in (c) makes the correct choice at both node (i), and node (ii), as it has global link information and always chooses the shortest possible path.
\fi

\section{Introduction}
This document is a model and instructions for \LaTeX.
Please observe the conference page limits.

\section{Ease of Use}

\subsection{Maintaining the Integrity of the Specifications}

The IEEEtran class file is used to format your paper and style the text. All margins,
column widths, line spaces, and text fonts are prescribed; please do not
alter them. You may note peculiarities. For example, the head margin
measures proportionately more than is customary. This measurement
and others are deliberate, using specifications that anticipate your paper
as one part of the entire proceedings, and not as an independent document.
Please do not revise any of the current designations.

\section{Prepare Your Paper Before Styling}
Before you begin to format your paper, first write and save the content as a
separate text file. Complete all content and organizational editing before
formatting. Please note sections \ref{AA}--\ref{SCM} below for more information on
proofreading, spelling and grammar.

Keep your text and graphic files separate until after the text has been
formatted and styled. Do not number text heads---{\LaTeX} will do that
for you.

\subsection{Abbreviations and Acronyms}\label{AA}
Define abbreviations and acronyms the first time they are used in the text,
even after they have been defined in the abstract. Abbreviations such as
IEEE, SI, MKS, CGS, ac, dc, and rms do not have to be defined. Do not use
abbreviations in the title or heads unless they are unavoidable.

\subsection{Units}
\begin{itemize}
\item Use either SI (MKS) or CGS as primary units. (SI units are encouraged.) English units may be used as secondary units (in parentheses). An exception would be the use of English units as identifiers in trade, such as ``3.5-inch disk drive''.
\item Avoid combining SI and CGS units, such as current in amperes and magnetic field in oersteds. This often leads to confusion because equations do not balance dimensionally. If you must use mixed units, clearly state the units for each quantity that you use in an equation.
\item Do not mix complete spellings and abbreviations of units: ``Wb/m\textsuperscript{2}'' or ``webers per square meter'', not ``webers/m\textsuperscript{2}''. Spell out units when they appear in text: ``. . . a few henries'', not ``. . . a few H''.
\item Use a zero before decimal points: ``0.25'', not ``.25''. Use ``cm\textsuperscript{3}'', not ``cc''.)
\end{itemize}

\subsection{Equations}
Number equations consecutively. To make your
equations more compact, you may use the solidus (~/~), the exp function, or
appropriate exponents. Italicize Roman symbols for quantities and variables,
but not Greek symbols. Use a long dash rather than a hyphen for a minus
sign. Punctuate equations with commas or periods when they are part of a
sentence, as in:
\begin{equation}
a+b=\gamma\label{eq}
\end{equation}

Be sure that the
symbols in your equation have been defined before or immediately following
the equation. Use ``\eqref{eq}'', not ``Eq.~\eqref{eq}'' or ``equation \eqref{eq}'', except at
the beginning of a sentence: ``Equation \eqref{eq} is . . .''

\subsection{\LaTeX-Specific Advice}

Please use ``soft'' (e.g., \verb|\eqref{Eq}|) cross references instead
of ``hard'' references (e.g., \verb|(1)|). That will make it possible
to combine sections, add equations, or change the order of figures or
citations without having to go through the file line by line.

Please don't use the \verb|{eqnarray}| equation environment. Use
\verb|{align}| or \verb|{IEEEeqnarray}| instead. The \verb|{eqnarray}|
environment leaves unsightly spaces around relation symbols.

Please note that the \verb|{subequations}| environment in {\LaTeX}
will increment the main equation counter even when there are no
equation numbers displayed. If you forget that, you might write an
article in which the equation numbers skip from (17) to (20), causing
the copy editors to wonder if you've discovered a new method of
counting.

{\BibTeX} does not work by magic. It doesn't get the bibliographic
data from thin air but from .bib files. If you use {\BibTeX} to produce a
bibliography you must send the .bib files.

{\LaTeX} can't read your mind. If you assign the same label to a
subsubsection and a table, you might find that Table I has been cross
referenced as Table IV-B3.

{\LaTeX} does not have precognitive abilities. If you put a
\verb|\label| command before the command that updates the counter it's
supposed to be using, the label will pick up the last counter to be
cross referenced instead. In particular, a \verb|\label| command
should not go before the caption of a figure or a table.

Do not use \verb|\nonumber| inside the \verb|{array}| environment. It
will not stop equation numbers inside \verb|{array}| (there won't be
any anyway) and it might stop a wanted equation number in the
surrounding equation.

\subsection{Some Common Mistakes}\label{SCM}
\begin{itemize}
\item The word ``data'' is plural, not singular.
\item The subscript for the permeability of vacuum $\mu_{0}$, and other common scientific constants, is zero with subscript formatting, not a lowercase letter ``o''.
\item In American English, commas, semicolons, periods, question and exclamation marks are located within quotation marks only when a complete thought or name is cited, such as a title or full quotation. When quotation marks are used, instead of a bold or italic typeface, to highlight a word or phrase, punctuation should appear outside of the quotation marks. A parenthetical phrase or statement at the end of a sentence is punctuated outside of the closing parenthesis (like this). (A parenthetical sentence is punctuated within the parentheses.)
\item A graph within a graph is an ``inset'', not an ``insert''. The word alternatively is preferred to the word ``alternately'' (unless you really mean something that alternates).
\item Do not use the word ``essentially'' to mean ``approximately'' or ``effectively''.
\item In your paper title, if the words ``that uses'' can accurately replace the word ``using'', capitalize the ``u''; if not, keep using lower-cased.
\item Be aware of the different meanings of the homophones ``affect'' and ``effect'', ``complement'' and ``compliment'', ``discreet'' and ``discrete'', ``principal'' and ``principle''.
\item Do not confuse ``imply'' and ``infer''.
\item The prefix ``non'' is not a word; it should be joined to the word it modifies, usually without a hyphen.
\item There is no period after the ``et'' in the Latin abbreviation ``et al.''.
\item The abbreviation ``i.e.'' means ``that is'', and the abbreviation ``e.g.'' means ``for example''.
\end{itemize}
An excellent style manual for science writers is \cite{b7}.

\subsection{Authors and Affiliations}
\textbf{The class file is designed for, but not limited to, six authors.} A
minimum of one author is required for all conference articles. Author names
should be listed starting from left to right and then moving down to the
next line. This is the author sequence that will be used in future citations
and by indexing services. Names should not be listed in columns nor group by
affiliation. Please keep your affiliations as succinct as possible (for
example, do not differentiate among departments of the same organization).

\subsection{Identify the Headings}
Headings, or heads, are organizational devices that guide the reader through
your paper. There are two types: component heads and text heads.

Component heads identify the different components of your paper and are not
topically subordinate to each other. Examples include Acknowledgments and
References and, for these, the correct style to use is ``Heading 5''. Use
``figure caption'' for your Figure captions, and ``table head'' for your
table title. Run-in heads, such as ``Abstract'', will require you to apply a
style (in this case, italic) in addition to the style provided by the drop
down menu to differentiate the head from the text.

Text heads organize the topics on a relational, hierarchical basis. For
example, the paper title is the primary text head because all subsequent
material relates and elaborates on this one topic. If there are two or more
sub-topics, the next level head (uppercase Roman numerals) should be used
and, conversely, if there are not at least two sub-topics, then no subheads
should be introduced.

\subsection{Figures and Tables}
\paragraph{Positioning Figures and Tables} Place figures and tables at the top and
bottom of columns. Avoid placing them in the middle of columns. Large
figures and tables may span across both columns. Figure captions should be
below the figures; table heads should appear above the tables. Insert
figures and tables after they are cited in the text. Use the abbreviation
``Fig.~\ref{fig}'', even at the beginning of a sentence.

\begin{table}[htbp]
\caption{Table Type Styles}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
\textbf{Table}&\multicolumn{3}{|c|}{\textbf{Table Column Head}} \\
\cline{2-4}
\textbf{Head} & \textbf{\textit{Table column subhead}}& \textbf{\textit{Subhead}}& \textbf{\textit{Subhead}} \\
\hline
copy& More table copy$^{\mathrm{a}}$& &  \\
\hline
\multicolumn{4}{l}{$^{\mathrm{a}}$Sample of a Table footnote.}
\end{tabular}
\label{tab1}
\end{center}
\end{table}

\begin{figure}[htbp]
\centerline{\includegraphics{fig1.png}}
\caption{Example of a figure caption.}
\label{fig}
\end{figure}

Figure Labels: Use 8 point Times New Roman for Figure labels. Use words
rather than symbols or abbreviations when writing Figure axis labels to
avoid confusing the reader. As an example, write the quantity
``Magnetization'', or ``Magnetization, M'', not just ``M''. If including
units in the label, present them within parentheses. Do not label axes only
with units. In the example, write ``Magnetization (A/m)'' or ``Magnetization
\{A[m(1)]\}'', not just ``A/m''. Do not label axes with a ratio of
quantities and units. For example, write ``Temperature (K)'', not
``Temperature/K''.

\section*{Acknowledgment}

The preferred spelling of the word ``acknowledgment'' in America is without
an ``e'' after the ``g''. Avoid the stilted expression ``one of us (R. B.
G.) thanks $\ldots$''. Instead, try ``R. B. G. thanks$\ldots$''. Put sponsor
acknowledgments in the unnumbered footnote on the first page.

\section*{References}

Please number citations consecutively within brackets \cite{b1}. The
sentence punctuation follows the bracket \cite{b2}. Refer simply to the reference
number, as in \cite{b3}---do not use ``Ref. \cite{b3}'' or ``reference \cite{b3}'' except at
the beginning of a sentence: ``Reference \cite{b3} was the first $\ldots$''

Number footnotes separately in superscripts. Place the actual footnote at
the bottom of the column in which it was cited. Do not put footnotes in the
abstract or reference list. Use letters for table footnotes.

Unless there are six authors or more give all authors' names; do not use
``et al.''. Papers that have not been published, even if they have been
submitted for publication, should be cited as ``unpublished'' \cite{b4}. Papers
that have been accepted for publication should be cited as ``in press'' \cite{b5}.
Capitalize only the first word in a paper title, except for proper nouns and
element symbols.

For papers published in translation journals, please give the English
citation first, followed by the original foreign-language citation \cite{b6}.

\section{Introduction}

Quantum key distribution (QKD) allows for the establishment of information theoretically secure secret keys between two or more parties.  However, despite their great potential, these systems face several critical shortcomings when attempting to implement them in practice.  Of particular importance are improving the speed and distance of these systems.  To overcome these limitations, quantum networks are often used, consisting of \emph{trusted nodes} and, in the near future, \emph{quantum repeaters} \cite{repeater1,repeater2}.  Since quantum repeaters are still a developing technology, current QKD networks established in various metropolitan areas consist only of end-users and trusted nodes \cite{elliott2004darpa,chen2010metropolitan,peev2009secoqc,zhang2018large,sasaki2011field}.  However, progress in developing stable quantum repeaters has been accelerating of late and so it is vital to begin developing suitable routing algorithms for networks consisting of a mixture of both repeaters and trusted nodes.  Indeed, developing efficient routing algorithms to operate in this setting is vital to the future performance of such networks.

Numerous work has been done investigating the performance of quantum networks consisting only of quantum repeaters (in addition to end users) \cite{van2013path,azuma2016fundamental,hahn2019quantum,vardoyan2019stochastic,pirandola2016capacities,wallnofer2019multipartite,pirandola2019end,li2020effective}, including the development and analysis of new routing protocols specific to that scenario \cite{caleffi2017optimal,gyongyosi2017entanglement,sazim2015retrieving,pant2019routing,chakraborty2019distributed}.  Mostly, the goal of such networks is to establish end-to-end entanglement between end users (which may, then, be used for QKD for instance).  However, QKD is a more practical technology today and there are several methods to improve their performance, such as through trusted nodes.  Thus it is also important to study QKD-specific networks.  Such work has been done investigating practical QKD-specific networks consisting predominately of trusted nodes and end users \cite{dianati2008architecture,qkd-network-stack,yang2017qkd}.  However, as repeater technology progresses, the desire to move away from trusted node technology, and their inherent security concerns, will become stronger.

Thus, it is important to begin investigating near-future QKD-specific networks consisting predominately of quantum repeaters, however with a minority of trusted nodes.  Furthermore, these networks will allow for multiple paths to be established between both repeaters and trusted nodes (i.e., repeaters are not used only to extend the distance between trusted nodes, but will be an integral part of the network interior).  These are the networks we consider in this paper.  In particular, we consider a grid topology in which it is possible to establish multiple paths between Alice, Bob, and various trusted nodes though a complex network of repeaters. Our goal is to understand what routing protocols can lead to efficient key distribution rates between end users and to understand how the quality of the repeaters and the number of trusted nodes, affects the performance of this network.

In this paper, we devise and evaluate three different routing algorithms for this QKD network: one requires global state information and the other two are decentralized, distributed, algorithms requiring only local state information.
We perform a rigorous evaluation, through simulations, of the performance of our algorithms in a variety of scenarios considering network size; quantum repeater quality; distance between nodes; quantity and specific location of trusted nodes; and channel noise.  Our results show that the careful design of routing algorithms is vital to establishing efficient key-distribution rates between users.  Along the way, we discover several fascinating properties of these networks which may be of great importance to operators of this future network architecture.

\subsection{Quantum Key Distribution}
Quantum key distribution (QKD) protocols operate in two stages: In the \emph{quantum communication stage}, users Alice and Bob use the quantum channel and the authenticated classical channel to attempt to establish a \emph{raw key} which is a classical bit string that is partially correlated (there may be errors in the quantum channel leading to errors in the raw key) and partially secret (an adversary may have some information on the raw key).  Since this raw key cannot be used directly for cryptographic purposes, a second, purely classical, stage is performed, running an error correction protocol (leaking additional information to an adversary) followed by privacy amplification, which leads to the final secret key.  An important metric in any QKD protocol is the protocol's \emph{key-rate} defined to be the ratio of secret key bits to the size of the raw key.  For a general survey of QKD protocols, the reader is referred to \cite{QKD-survey-old,QKD-Survey}.

In this work, we are interested in the theoretical performance of a network of QKD systems.  As such, we consider ideal single-qubit sources (though potentially there is loss due to the fiber channel connecting nodes).  Furthermore, we do not consider finite key effects \cite{scarani2008quantum} or imperfect sampling, in an attempt to understand the theoretical behavior of the network.  Under this setting, the key-rate of the E91 \cite{QKD-E91} protocol, which we adopt as the QKD protocol used in our network, is found to be \cite{QKD-BB84-rate1,QKD-renner-keyrate}: $\texttt{rate} = 1-2h(Q)$, where $Q$ is the bit error rate in the raw key and $h(\cdot)$ is the binary entropy function.  Note that, if we did not assume single-qubit sources and, instead, weak coherent sources, we would need to use an alternative key-rate expression or, perhaps, the decoy state BB84 protocol \cite{lo2005decoy}; these are interesting issues we leave as future work.

Point-to-point QKD systems are often implemented over fiber channels (though free-space operation is also possible if one has direct line of sight).  One limitation to QKD protocols is their intolerance to qubit loss \cite{pirandola2017fundamental,QKD-Survey}; since loss over a fiber channel scales exponentially with distance, this is particularly problematic for ground operation.  To overcome this, one may use \emph{quantum repeaters} \cite{repeater1,repeater2} and \emph{trusted nodes}.  Both systems are placed between users, thus halving the total distance a qubit is required to travel; furthermore, multiple such nodes may be chained together thus further decreasing the distance.  Quantum repeaters utilize entanglement swapping to produce a shared entangled bit between two users.  Trusted nodes act as users in a QKD protocol, establishing a key $k_{AT}$ with Alice and a second, independent key, $k_{TB}$ with Bob.  The trusted node then sends to $B$ (using an authenticated classical channel) the value $k_{AT}\oplus k_{TB}$, where $\oplus$ is the bit-wise XOR.  This allows Alice and Bob to share a classical key, though the trusted node also shares this key.

The advantage to quantum repeaters is that the final key $A$ and $B$ produce is independent of the repeater's knowledge.  That is, if a repeater is controlled by an adversary, it cannot learn the final secret key.  However, the technology for repeaters requires short-term quantum memories which is a difficult engineering challenge (though the technology is rapidly advancing).  Trusted nodes have the advantage of simplicity as they are no different in technology than Alice or Bob.  However, they must remain trusted and safe from an adversary as they do have full knowledge of the secret key.

\subsection{Related Work}
There has been recent research in analyzing routing protocols, along with the general behavior and performance, of quantum networks consisting of end-users and quantum repeaters, but no trusted nodes; see for instance \cite{van2013path,azuma2016fundamental,caleffi2017optimal,gyongyosi2017entanglement,hahn2019quantum,pant2019routing,vardoyan2019stochastic,chakraborty2019distributed,pirandola2016capacities,wallnofer2019multipartite,pirandola2019end} with \cite{caleffi2017optimal,gyongyosi2017entanglement,pant2019routing,chakraborty2019distributed} giving particular focus on specific routing protocols for certain network topologies in generating shared entanglement between users, which is a stronger resource than QKD. However, QKD is, currently, a more practical and mature technology and, furthermore, there are numerous methods of improving the performance (speed and distance) of these systems that are unavailable to entanglement generation networks, namely the use of trusted nodes.  Thus, while routing protocols designed for an entanglement-generation quantum internet can be used also for QKD, more efficient systems may exist and, furthermore, solutions incorporating both trusted nodes and repeaters are vital for near-term deployment of this technology and are the networks we consider in this work.

Early work on QKD-specific networks focused on algorithms for optical-based switching networks \cite{toliver2003experimental}.  Such networks were used in practice, for instance the 2004 DARPA network in the Boston area \cite{elliott2004darpa,elliott2005current} and the 2009 network in Hefei \cite{chen2010metropolitan}, utilized such an architecture (the Hefei network also utilized trusted nodes).  These networks consisted of end-users and optical switches allowing users to route qubits to each other.

A more capable QKD network consists of end-users and trusted nodes and is the most common of network architectures for practical QKD networks in operation today such as the SECOQC network in Vienna \cite{peev2009secoqc}, the previously mentioned Hefei network \cite{chen2010metropolitan}, the Tokyo QKD network \cite{sasaki2011field} and the Beijing-Shanghai network \cite{zhang2018large}.  In terms of routing algorithms, the Vienna network used a variant of the OSPF routing algorithm \cite{dianati2008architecture}.  In \cite{tanizawa2016routing}, required functionalities of a QKD network routing algorithm were described for this form of network and a routing protocol was proposed, while \cite{yang2017qkd} began constructing routing protocols for larger scale networks evaluated through simulations. A novel quality of service model for these networks, and new routing protocols, were introduced in \cite{mehic2019novel}.  A complete QKD network stack for such networks was proposed in \cite{qkd-network-stack}, along with advanced routing functionalities through trusted nodes taking into account channel performance and key-rate demands, while in \cite{li2020mathematical}, a mathematical model was proposed for analyzing such trusted-node QKD networks.

The severe limitation to trusted nodes is that, as their name implies, they must be trusted.  Indeed, a trusted node is fully aware of the secret key which $A$ and $B$ distill (multi-path routing is one counter-measure to this, though still imperfect).  An advancement from this would be the use of quantum repeaters.  However, while the technology for these is advancing rapidly, it is more likely that in the near-future, any QKD network will consist of both repeaters and trusted nodes.  Thus, developing new and efficient routing algorithms specific for this network technology, is vital.  In this work, we consider networks that consist of a majority of repeaters with a minority of trusted nodes, attempting to discover optimal routing protocols for this scenario and to understand the behavior of such a network.  Note that in \cite{qkd-network-stack}, the use of quantum repeaters in a chain to link together different trusted nodes was considered an option; here, however, we are considering more complex networks of repeaters, allowing for potential multi-path routing options between both trusted nodes and multiple repeaters.

\section{Discussion}
\section{Summary and Insights}
The data suggests a number of interesting lessons regarding this sort of QKD network. Most glaringly, it is immediately evident that the addition of even a single trusted node into a network can greatly increase what key rates are achievable, even with ideal repeater technology. Further, we see that a small adjustment to the natural local routing algorithm, in the form of a tendency to avoid intersection of paths, can lead to increases in key rate comparable to, or even exceeding, that of the addition of a single trusted node, with a negligible increase in complexity. As we have seen, this increase in key rates generalizes to multiple trusted nodes, on larger grids, but there is some consideration that must be given to the placement of the additional trusted nodes. Indeed, a non-optimal placement of trusted nodes can in fact hinder the operation of the network, especially for the local algorithms.

The data further suggests some lessons regarding the limitations of such a network. We see that while fiber length plays an important role in determining key rate, it is the BSM success probability and the decoherence rate that are seemingly the largest obstacles to achieving a higher key rate. This relationship is no more evident than in Fig.~\ref{fig:FixedLength}, where we see that these factors play an important role in limiting the total distance the network can cover, as they make it infeasible to mitigate the effects of fiber length by simply adding additional nodes to the network. In fact  doing so can actually decrease key rates, if not counterbalanced with the addition of trusted nodes.

Finally, our analysis makes clear the important role trusted nodes will still have to play after quantum repeater networks become practical, or even perfect. As was shown in Fig.~\ref{fig:2TNGraphsB}, even with perfect quantum repeaters, the addition of trusted nodes can result in positive and significant key rates being achieved where they were otherwise not possible. Trusted nodes can be used in the networks to facilitate the establishment of efficient QKD networks reaching along far distances consisting of many nodes. In fact, one can even conceive of network models in which the trusted nodes also operate as part of a multi-party QKD system.

\section{Conclusion}
In this work we have proposed a novel model for analyzing the performance of quantum repeater QKD grid networks with the inclusion of a minority of trusted nodes. We proposed three routing algorithms, and evaluate the performance of the E91 QKD protocol when using them for a variety of channel and network configurations. We discuss general lessons that can be drawn from our results, including the importance of not only the inclusion of trusted nodes, but also their placement, and some general limitations inherent to working with such networks.  Note that our approach can also be used to determine network resources needed to achieve desired rates between users at given distances or with given repeater quality.  Our work in this paper can  serve as a baseline for future exploration of this area, and we leave open as future work issues such as the development of better local and global algorithms; analysis of mutli-party networks of this form; analysis of more complicated, potentially asymmetric networks; analytic results regarding the capabilities of these networks; the possibility of embedding Alice and Bob as part of a larger network, rather than at the corners; as well as the extension of this analysis to additional QKD protocols.

\balance
\bibliographystyle{ieeetr}

\section{Model and Simulator}\label{sec:model}

In this work we consider a grid network consisting of $N\times N$ nodes with each node connected to at most four others, their immediate neighbors up, down, left, and right.  These connections represent fiber links allowing for the direct transmission of qubits between neighboring nodes only.  We assume a classical communication network allowing any pair of nodes to send classical messages.  We do not assume this communication is secret; however for all user and trusted node communication we do assume it is authenticated.  Each node in this network may be either a User (Alice or Bob); a Trusted Node; or a Quantum Repeater.  We place Alice at the lower-left corner of the network and Bob in the upper-right (thus, these users have only two neighbors they are connected to).  Later, we will simulate alternative numbers and locations of the trusted nodes; however, predominately the other nodes will consist of quantum repeaters in contrast to current day QKD networks.

\triplefig{stage1.pdf}{Initial network}{stage2.pdf}{Stage 1}{stage3.pdf}{Stage 2}{(a) The initial network of a $5\times5$ grid, with a central trusted node ($T$) between Alice ($A$) and Bob ($B$). (b) A possible network configuration after stage 1, in which some nodes succeed in establishing a shared state of the form in Equation (\ref{eq:shared-state0}) with their neighbors over the fiber channels and some do not.
(c) Successful entanglement chaining and routing (depicted as the ``internal links'' at repeaters) as discussed in Stage 2. In this graph, routing has resulted in end-to-end paths being created between each pair of $A$, $B$ and $T$. These routes are successful only if every Bell state measurement along the path succeeds. Furthermore, the probability of decoherence increases with the path length in our model as discussed; thus minimizing the path lengths through effective routing algorithms and trusted nodes is advantageous.  See also Figure \ref{fig:guide}.}{stages1-3}

\begin{figure}
    \centering
    \includegraphics{sideguide.pdf}
    \caption{A legend for our network diagrams. Left: (a) denotes a node in the network, specifically a repeater with 4 (b) connection terminals from which entangled photons are sent and received over (c) fiber optic connections between other repeaters and (d) trusted nodes. Right: an entangled channel (e) connecting multiple trusted nodes through intra-node entanglement (f).}
    \label{fig:guide}
\end{figure}

Users and trusted nodes perform the E91 QKD protocol.  For notation, we assume there are $n$ trusted nodes denoted $T_1, \ldots, T_n$.  We label Alice as $T_0$ and Bob as $T_{n+1}$.  For every pair of users and trusted nodes there exists a private raw-key pool; that is, for every $i,j \in \{0,\cdots, n+1\}$, with $i < j$, there exists a buffer $\mathcal{RK}_{i,j}$, storing the raw key shared between nodes $T_i$ and $T_j$.  Note that repeaters do not have key buffers.  As we are using the entanglement based E91 protocol, the first goal of the network is to establish joint entanglement between these pairs of nodes $T_i$ and $T_j$, ideally the Bell state $\ket{\Phi^+} = \frac{1}{\sqrt{2}}(\ket{00} + \ket{11})$.  This resource may be used to establish a secret key between users.

The quantum network we analyze operates in {\em rounds}, each round consisting of {\em three primary stages} (see examples in Figures \ref{fig:stages1-3} and \ref{fig:guide}).  The first stage, and part of the second stage, are standard in repeater-only quantum networks (see \cite{pant2019routing,chakraborty2019distributed}). As mentioned, nodes have at most four inputs into them (since the two users are at the corner of grid, they each only have two inputs); we assume that nodes have the capability of storing a single qubit in short-term memory for each of these inputs, through one complete round.  After the round is complete, any qubits not measured, are discarded.  That is, the memory capabilities of nodes are not sufficient to store a qubit through two or more rounds in our network.  Note that users in our network have the fewest demands on quantum memory.

In the first stage, adjacent nodes attempt to share an entangled pair, in particular the Bell state $\ket{\Phi^+}$, with one particle remaining at a local node and the other being transmitted to an adjacent node.  Due to fiber loss, this succeeds with a certain probability $p = 10^{-\alpha L/10}$ where $\alpha$ is the fiber attenuation coefficient (we use $\alpha = .15$ in our later simulations).  Furthermore, even if successful, the entangled pair may not be a Bell state $\ket{\Phi^+}$ but instead will, with probability $D$, depolarize and become completely mixed.  Ultimately, after this first stage, adjacent nodes $u$ and $v$ will either not have any qubit in their short-term memory (with probability $1-p$) or, with probability $p$, they will share a quantum state of the form:
\begin{equation}\label{eq:shared-state0}
\rho_{u,v} = (1-D)\kb{\Phi^+} + D \cdot \frac{I}{4},
\end{equation}
where $I$ is the identity operator on two qubits.  Note this $D$ may be used to model channel noise along with noise internal to the quantum memory of the repeater.  As is standard in repeater-network analyses \cite{pant2019routing,chakraborty2019distributed}, we assume that nodes are able to determine whether a qubit has arrived in their short-term quantum memory or if it is a vacuum.

In the second stage, a routing protocol, to be discussed (see Section~\ref{sec:routing}), is performed to decide how to
effectively route entanglement between nodes $T_i$ and $T_j$ for $i \ne j$.  This routing protocol can take into account whether nodes have a qubit in their short-term memory.  The goal of this stage, and in particular the routing algorithm, is to determine a set of paths, the end-points of which are either users or trusted nodes, while the interior nodes of each path are quantum repeaters.  Given these paths, the quantum repeaters will perform entanglement swapping operations on the qubits that are locally held in their short-term memory, which, if successful, create ``virtual'' entangled links between the end-points of each path.
The entanglement swapping operations at the repeaters, which themselves consist of Bell measurements, succeed only with a certain probability that we denote as $B$.  We assume the network is able to determine whether a successful entanglement swapping occurred or not.  Thus, at the end of this stage, end-nodes $T_i$ and $T_j$ on each path can determine whether the network was successful in creating an end-to-end  path between these nodes.  Note that they cannot tell if the state they share is the correct Bell state $\ket{\Phi^+}$ or the completely mixed state $I/4$ due to depolarization.  At this point, repeaters are no longer needed until the next round, and users and trusted nodes share a state of the form in Equation (\ref{eq:shared-state}), where the probabilities of the mixed state depend on $D$ and the path length -- in particular, on a path consisting of $k$ interior nodes, the shared state will either be:
\begin{equation}\label{eq:shared-state}
\rho_{T_iT_j} = (1-D)^{k+1}\kb{\phi^+} + (1-[1-D]^{k+1})\cdot\frac{I}{4},
\end{equation}
or a vacuum if one or more repeaters failed in their entanglement swapping operation.

Finally, in the third stage, all pairs $T_i$ and $T_j$ of users and trusted nodes which have a shared state, and not a vacuum, attempt to distill a raw-key bit using the E91 QKD protocol.  If successful (which depends on users choosing the correct basis, and as such it is successful with probability $1/2$), the key-bit is added to a local raw key-pool for those users $\mathcal{RK}_{i,j}$.  Any qubit that was not measured by now is discarded and the network repeats at stage 1, attempting to establish fresh entangled pairs between adjacent nodes.  Refer to Figures \ref{fig:stages1-3} and \ref{fig:guide}.

We wrote a custom simulator to simulate the behavior of this network and these three stages.  This simulator maintains a raw-key pool $\mathcal{RK}_{i,j}$ between each pair of users $T_i$ and $T_j$ as would be done in an actual operation of this network.  In practice, nodes $T_i$ and $T_j$ will, once the length of the raw key in $\mathcal{RK}_{i,j}$ is sufficiently large, perform error correction and privacy amplification, leading to a secret key of size $|\mathcal{K}_{i,j}|$.  In our simulations, we are interested in the theoretical performance of this network, and so we only do this process once at the end of the simulation and set $|\mathcal{K}_{i,j}| = |\mathcal{RK}_{i,j}|\cdot (1-2h(Q))$ where $Q$ is the error in the raw key pool $\mathcal{RK}_{i,j}$ and where $h(x)=x\log(x)-(1-x)\log(1-x)$ is the binary entropy function. Again, as we are only interested in theoretical behavior, we compute $Q$ based on the actual simulator data; in practice $Q$ may be estimated by sampling from $\mathcal{RK}_{i,j}$.

Of course, the ultimate goal of the network is to maximize the secret key pool between Alice and Bob (i.e., $T_0$ and $T_{n+1}$).  If $n=0$ (i.e., there is no trusted node), at this point, we are done.  However for $n\ge 1$, a final key-routing process is required of the trusted nodes who must attempt to ``push'' a maximal amount of key material to Alice and Bob.  For $n=1$, this is trivial: $T_1$ will simply broadcast $\mathcal{K}_{0,1}\oplus \mathcal{K}_{1,2}$ (here, $T_0$ is Alice and $T_2$ is Bob); if they are not of equal length, then only the left-portion is broadcast.  Alice and Bob already have a secret key of size $|\mathcal{K}_{0,2}|$ before this process.  Thus, finally, they end up with a secret key of total size $|\mathcal{K}_{0,2}| + \min(|\mathcal{K}_{0,1}|, |\mathcal{K}_{1,2}|)$.  When $n > 1$ the situation is more complicated; in this work we use the max-flow algorithm to determine how many additional bits are appended to $\mathcal{K}_{0,n+1}$.  Note that, at the end, not all key bits in trusted node pools may be usable if there is an insufficient amount of key material in ``matching'' nodes.  Later, when we evaluate performance of our routing protocols, we will look at the key-rate of the network, namely the size of the final secret key between Alice and Bob (after the trusted nodes perform this final key-routing process) divided by the total number of network rounds.

\subsection{Multiple Trusted Nodes} \label{sec:more-trusted-nodes}

\singlefig{TNs.pdf}{A $7\times7$ network with 3 different ways of placing the two trusted nodes. The nodes labeled with $A$ and $B$ are Alice and Bob in each type of placement; the two nodes labeled with $C$ are the trusted nodes in the {\em corner} placement; the two nodes labeled with $D$ are the trusted nodes in the {\em diagonal} placement; and  the two nodes labeled with $R$ are the two trusted nodes in the {\em asymmetric} placement.}{TNPlacement}

\triplefigbig{figs/2TN_g.pdf}{Global}{figs/2TN_IA.pdf}{Intersection Avoidant}{figs/2TN_NIA.pdf}{Non-Intersection Avoidant}{Key rate versus the decoherence rate for the three routing algorithms in a $7\times7$ grid with $L=1$ km and $B=.85$. We consider the No TN case, the Central TN case, and the 2 TN cases in which there are two trusted nodes in the network, following corner, diagonal or asymmetric placements. }{2TNGraphs}

\tydubfigsingle{figs/S_fixed_global.pdf}{Global}{figs/S_fixed_IA.pdf}{Intersection Avoidant}{Key rate versus the network size for the global and IA routing algorithms for a 10 km $\times$ 10 km network grid where the fiber length between each node decreases as the network size increases. Notably, we see some non-monotonicity as the diagonal configuration does not operate effectively at grid sizes that are not of the form $3x+1$ for some integer $x$, and the central case does not operate effectively at even grid sizes such as 10x10. }{FixedLength}

\tydubfigsingle{figs/B_all2E_global}{Global}{figs/B_all2E_IA}{Intersection Avoidant}{Key rate versus the BSM Success rate for the global and IA routing algorithms in a $7\times7$ grid with $L=1$ km and $D=.02$. We consider the no TN case, the central TN case, and the 2 TN cases in which there are two trusted nodes in the network, following corner, diagonal or asymmetric placements.}{2TNGraphsB}

We now consider having two trusted nodes in the network. Specifically, we investigate three methods of placing these two trusted nodes, referred to as {\em corner}, {\em diagonal}, and {\em asymmetric} placements. In the corner placement, the two trusted nodes are located at the two opposite corners of the graph (distinct from Alice and Bob's corners); in the diagonal placement, the two trusted nodes are placed evenly along the diagonal between Alice and Bob; in the asymmetric placement, one trusted node is located in the center, while the other is located one node along the diagonal closer to Alice. Fig.~\ref{fig:TNPlacement} illustrates the above three types of placement for a $7\times7$ grid (we use a $7\times7$ instead of a $5\times5$ grid as the diagonal placement only performs optimally for grid size $N =3x+1$ for some integer $x$).

Figures~\ref{fig:2TNGraphs}(a) through (c) plot the key rate as the decoherence rate increases for each of the above types of placement for the global, IA and NIA routing algorithms, respectively. For comparison, in each figure, the results with a single trusted node placed in the center and no trusted node are also plotted in the figure. We see that for the global routing algorithm (see Fig.~\ref{fig:2TNGraphs}(a)), the diagonal placement outperforms the other four cases (i.e., corner and asymmetric placement of two trusted nodes, as well as no trusted node and placing a single trusted node in the center) by a large margin.

The clustering of the non-diagonal configurations we attribute to two separate reasons. First, consider that in the central configuration, an optimal pathing results in two channels connecting Alice to the trusted node, and two more connecting the trusted node to Bob. Importantly, these channels will consist of 6 edges each. In the corner configuration, an optimal pathing results in one channel between Alice and each of the two trusted nodes, and likewise from Bob to the trusted nodes. Again, these channels will consist of 6 edges each. As a result, at least in the global case, the likelihood that these paths exist, that the channels are successfully established and that the entanglement remains coherent are all equivalent. It stands to reason then, and the data reflects that reasoning, that the corner configuration and the central configuration are equivalent, in terms of performance. In the other case, it is the asymmetry that causes the equality. Although the second trusted node does result in Alice and the central trusted node sharing a larger key, the central trusted node and Bob establish no more key-bits than if the second trusted node did not exist. As a result, in the final routing of key material, the overall capacity between Alice and Bob remains unchanged, and so the additional key-bits that Alice and the trusted node were able to establish go unused. Finally, the over-performance of the diagonal configuration is a result, as one would expect, from the further segmentation of the $7 \times 7$ network into 3 distinct sub-networks: between Alice and the first trusted node; the first and second trusted nodes; and finally the second trusted node and Bob. As shown in the figure, this additional trusted node can increase our key rate by almost a factor of 1.5 over the central trusted node configuration.

We repeat the above investigation for the IA algorithm (see Fig.~\ref{fig:2TNGraphs}(b)). Again, we see that the diagonal placement outperforms the others, and that the performance of the corner placement of two trusted nodes is very similar to that when placing a single trusted node in the center. We also see, however, that the redundant trusted node in the asymmetric case results in a large detriment to the key rate, dropping it almost a full .3 key-bits/round. This is likely due to the greedy nature of the routing algorithm -- having an additional node complicates the decision process of the repeaters near both trusted nodes, potentially wasting edges that otherwise could have been utilized in a more effective manner.

The differences in the performance of the different types of placement are even more dramatic for the NIA algorithm in Fig.~\ref{fig:2TNGraphs}(c). For each configuration we see a significant drop in performance, except for the corner placement, which remains relatively consistent with its performance in the other algorithms. This difference can be explained by the fact that that the NIA algorithm does not generally struggle with intersecting paths in the corner case, as the optimal paths themselves tend not to contain many right angles. The effect of this is so great, in fact, that at lower error rates the corner configuration in fact outperforms the diagonal configuration, until the shorter hop-length of the channels in the diagonal configuration becomes the dominating factor in determining key rate.

As physical distance between Alice and Bob increases, one might think that there is benefit to be had by adding additional repeaters and decreasing the distance between nodes themselves. We investigate whether or not this is feasible in Fig.~\ref{fig:FixedLength} in which the physical distance the network spans is fixed at $10$ km $\times$ $10$ km, while the number of nodes in the grid is increased (this is in contrast to our other simulations where the total width of the network was not fixed, but instead, the length and width are both $(N-1)\cdot L$ km). What we see is that the tendency for BSM failure chance and decoherence probability to increase as path sizes increase puts a damper on any benefit that can be achieved through this method. In some scenarios it is likely that there are trade-offs that can be made, depending on the target distance between Alice and Bob, BSM success probabilities, and decoherence probabilities, but evidently there are limitations inherent to trying to augment the key rate using this method.

It is clear, however, that this limitation can be alleviated in part by the addition of trusted nodes. As can be seen in Fig.~\ref{fig:FixedLength}, while the key rate of each configuration decreases as the size increases, even as the fiber length decreases, additional trusted nodes remain effective in boosting the key rate. As a result, it is still possible to increase network size to alleviate fiber length concerns, as long as the number of trusted nodes is also increased.  Additionally,
Fig.~\ref{fig:FixedLength} showcases the way in which non-optimal grid sizes affect key rate for the different TN configurations. Namely, we see that the key rate of the diagonal configuration actually increases between $N=5$ and $N=7$, or $N=9$ and $N=10$, as we move from grid sizes not of the form $3x+1$ to grid sizes of that form. We see the same for the central configuration at the even grid size of $N=10$, where the node is placed slightly off center, and as such actually increases at $N=11$.

Finally, in Fig.~\ref{fig:2TNGraphsB} we consider the performance of the global and IA algorithms on a number of TN configurations as the BSM success probability increases. Again, we see that the general trend is the same between the global and IA algorithms, with the global algorithm outperforming the IA algorithm in each configuration, and especially the asymmetric case. In the diagonal configuration, with perfect quantum repeaters (i.e. $B=1$), both are able to achieve a key rate of more than .45 key-bits/round with 2 TN in the diagonal configuration, and with 1 TN in the center, the IA algorithm and global algorithms achieve key rates of .3 and .33 key-bits/round, respectively.
The above results are notable, because they give some sense of the trends we might expect to see as quantum repeater technology advances. They also show the great benefit to using trusted nodes, even with perfect, ideal, repeaters.

\iffalse
one with the two trusted nodes located at the two opposite corners of the graph (distinct from Alice and Bob's corners), one with the two trusted nodes distributed evenly along the diagonal between Alice and Bob, and one with one trusted node located at the center, and the other located one node along the diagonal closer to Alice. We refer to the above three types of placements as the {\em corner}, {\em diagonal}, and {\em asymmetric} configurations, as illustrated in Fig.~\ref{fig:TNPlacement} for a $7\times7$ grid (we use a $7\times7$ instead of a $5\times5$ grid since the diagonal configuration only performs optimally for grid size $N =3x+1$ for some integer $x$). Fig.~\ref{fig:2TNGraphs} plots the key rate under the these three placements of two trusted nodes. For comparison, the results with a single trusted node placed in the center are also plotted in the figure.

What we find is that, in the global case (as shown in Fig.~\ref{fig:2TNGraphs}(a), the corner, central, and asymmetric configurations perform at essentially the same level, while the diagonal configuration outperforms the others by a large margin. The clustering of the non-diagonal configurations we attribute to two separate reasons. First, consider that in the central configuration, an optimal pathing results in two channels connection Alice to the trusted node, and two more connecting the trusted node to Bob. Importantly, these channels will consist of 6 edges each. In the corner configuration, an optimal pathing results in one channel between Alice and each of the two trusted nodes, and likewise from Bob to the trusted nodes. Again, these channels will consist of 6 edges each. As a result, at least in the global case, the likelihood that these paths exist, that the channels are successfully established and that the entanglement remains coherent are all equivalent. It stands to reason then, and the data reflects that reasoning, that the corner configuration and the central configuration are equivalent, in terms of performance. In the other case, it is the asymmetry that causes the equality. Although the second trusted node does result in Alice and the central trusted node to share a larger key, the central trusted node and Bob establish no more key-bits than if the second trusted node did not exist. As a result, in the final routing of key material, the overall capacity between Alice and Bob remains unchanged, and so the additional key-bits that Alice and the trusted node were able to establish go unused. Finally, the over-performance of the diagonal configuration is a result, as one would expect, from the further segmentation of the 7x7 network into 3 distinct sub-network between Alice and the first trusted node, the first and second trusted nodes, and the second trusted node and Bob. As shown in the figure, this additional trusted node can increase our key rate by almost a factor of 1.5 over the central trusted node configuration.

In the second figure, Fig. ~\ref{fig:2TNGraphs}(b), we repeat this investigation for the Intersection Avoidant algorithm. again we see that the diagonal configuration outperforms the others, and that the corner and central configurations are equivalent. We also see, however, that the redundant trusted node in the asymmetric case results in a large detriment to the key rate, dropping it almost a full .3 key-bits/round. This is likely due to the additional node complicating the decision of repeaters near both nodes, potentially wasting edges that otherwise could have been utilized in an effective manner.

The differences in performance are even more stark when we look at the Non-Intersection Avoidant algorithm in the third chart, Fig~\ref{fig:2TNGraphs}(c). For each configuration we see a significant drop in performance, save for the corner configuration which remains relatively consistent. This difference can be explained by the fact that that the NIA algorithm does not generally struggle with intersecting paths in the corner case, as the optimal paths themselves tend not to contain many right angles. The effect of this is so great, in fact, that at lower error rates the corner configuration in fact outperforms the diagonal configuration, until the shorter hop-length of the channels in the diagonal configuration becomes the dominating factor in determining key rate.
\fi

\subsection{Simulator}
\begin{figure}
    \centering
    \includegraphics{sideguide.pdf}
    \caption{A legend for Figure \#\ref{fig:stages1-3}. (a) denotes a node in the network, specifically a repeater with 4 (b) connection terminals from which entangled photons are sent and received over (c) fiber optic connections between other repeaters and (d) trusted nodes. Below the line, an entangled channel (e) connecting multiple trusted nodes through intra-node entanglement (f)}
    \label{fig:guide}
\end{figure}

\triplefig{stage1.pdf}{Stage 0}{stage2.pdf}{Stage 1}{stage3.pdf}{Stage 2}{(a) The initial network, in a 5x5 grid, with a central trusted node (T) between Alice (A) and Bob (B), as discussed in stage 0. (b) A possible network configuration after stage 1, in which some nodes succeed in establishing a shared EPR pair with their neighbors over the fiber channels and some do not. Note that there are a number of possible paths between A, B and T. (c) Successful entanglement chaining and routing (depicted as the intra-repeater connections) as discussed in stage 2. In this graph, routing has resulted in a channel being created between each pair of A, B and T. These routes are successful and coherent only if every bell state measurement along the path succeeds, and if no decohering occurs in the path, so minimizing the path lengths with effective routing algorithms and trusted node utilization is advantageous. For the purposes of this diagram we condition on the channels remaining coherent, but in practice any could have become decoherent.}{stages1-3}
To analyze the behavior of the QKD network we envision and to evaluate the performance of the various routing protocols we construct later, we wrote a custom simulator.  This simulator, following an initialization stage, operates in four steps, which each  take in as input the state of the network graph at the end of the state prior and outputting the resulting, evolved graph. \par
\textbf{0. Initialization:}
Consider an $N\times N$ (for an odd $N$) network graph with some number of trusted nodes and Alice and Bob at opposite corners of the network, Such a network begins in the state $G = \{V,E\}$ where $V = \{0,1, \dotso,N^2-2, N^2-1\}$ with Alice at node $A=0$ and Bob at node $B = N^2-1$, and trusted nodes $T \subseteq V$. Finally, without loss of generality we consider a grid network in which the nodes are ordered increasing from left to right and bottom to top, and so we have $E$ defined in the natural way. We show the steps describing the evolution of this graph in the following section, as well as the evolution of this example graph in Figs.~\ref{fig:stages1-3} and \ref{fig:stage5}, with a key provided in Fig.~\ref{fig:guide}. \par
\textbf{1. Entanglement Generation:} In the initial phase, each node attempts to share one half of a  Einstein–Podolsky–Rosen (EPR) \cite{EPR} pair with its neighbors over the fiber channel. The photon pair is successfully transmitted and received with probability $10^{-\alpha L/10}$ \cite{transmittance} where $\alpha$, also a characteristic of the network, is the transmittance of the fiber channel. As such the network evolves to $G_1 = \{V, E_1\}$ where $E_1 = \{(u,v) \forall (u,v) \in E  \; |\;  S(u,v) \}$  \OA{what is set notation for random sets?}, where $S(u,v)$ is a random binary function that returns true for any edge with probability $10^{-\alpha L/10}.$ \par
\textbf{2. Routing and Entanglement Chaining: } With the evolved network graph, the repeater nodes utilize a routing algorithm (we will discuss a number of candidate algorithms in the following section) to determine, at each repeater, which neighbors should be connected by entanglement. The routing algorithm, $R1$, takes $G_1$ as input and outputs $P = \{p_i\}_{i=0}^n$ where $p_i = (r_0^i, r_1^i, \dotso, r_{m_i}^i)$ describe paths originating from and ending at Alice, Bob, or a trusted node through a path of $m-2$ entanglement connected quantum repeaters. The quantum repeaters then use this pathing information and conduct bell state measurements on the photons they hold that are entangled with photons at the nodes before and after them in a path \bing{this sentence is a bit long; can we rephrase by using the notation?}, succeeding with probability $B$ and becoming decoherent with probability $D$. As a result of this action, the network evolves and is compromised of Alice, Bob, trusted nodes, and shared entanglement (which with some probability has decohered) between those parties. Specifically, we have $G_2 = \{V_2, E_2\}$ where $V_2 = T\cup \{A,B\}$ and $E_2 = \{(r_0^i,r_{m_i}^i,F(p_i)) \; \forall p_i \in P\}$ where $F(p_i)$ is a random binary function that decides whether or not the entangled channel has fidelity. Fidelity is maintained with probability $(1-d)^{m_i-2}$, as it must be the case that at each of the $m_i-2$ intermediate nodes, the bell state measurement did not fail. We note that as there can be multiple (up to two) paths between the same pair of entities, the elements in $E_2$ are not necessarily unique. \par
\textbf{3. Quantum Key Distribution:} In this stage, the entities in $G_2$ attempt to use the quantum channels established between them to conduct a round of an entanglement based QKD protocol --- in our case, E91. Here we will  introduce a secondary network structure, with weighted edges connecting Alice, Bob, and trusted nodes with weights representing the amount of key material shared between nodes. The edges additionally have associated with them a bit string, with length equal to their weight, representing whether there is a correlation in each bit of key material (though the value of the bits themselves, for the purpose of our simulation, is irrelevant). This graph, at the start of the protocol, is initialized to $G_3 = \{V_2, E_3\}$ where $E_3 = \{(u,v,0,\epsilon) \; \forall u,v \in V_2\},$ where $\epsilon$ is the empty string denoting the correlations in the amount of stored key material, which is 0 \bing{what does the `0' represent here?}.

On this stage, we build on $G_3$ based on the state of $G_2$. Specifically, if QKD succeeds between two linked nodes, which it does with probability $\frac{1}{4},$ then a bit is added to that that bank of key material, which is a correlated with full probability if the link was coherent \bing{rephrase?}. If the link was not coherent, then we assume that it became a fully mixed state, and that resulting measurements are random and therefore correlated with $\frac{1}{2}$ probability. Formally, this means that for each edge $(u,v,1) \in E_2$, with $\frac{1}{4}$ probability we update the corresponding edge $(u,v,k,c)$ in $E_3$ to $(u,v,k+1,c||0)$, and likewise for each edge $(u,v,0)$ we update the corresponding edge to $(u,v,k,c||0)$ or $(u,v,k,c||1)$  with equal probability, where $||$ denotes concatenation of bit strings.

\par
\textbf{4. Key Distillation}
Stages 1-3 repeat some $M$ times, building sufficiently sized key stores between each of the participating parties in our network until, on this stage, the final key-distillation and key-routing process occurs. On this stage, each pair of parties that share some amount of raw key material can conduct standard post-processing procedures, namely, error correction and privacy amplification, to transform their raw-key stores into secret-key stores. As we are limiting our analysis in this work to only consider the performance in the asymptotic key-length realm, we do not consider finite key effects, and so the simulator simply transforms the edges $(u,v,k,c)$ in $G_3$ to be $(u,v,(1-2h(Q))k, \epsilon)$, to signify the error correction and privacy amplification process according to the standard process, where Q is the quantum bit error rate of the key, calculated as $\frac{w(c)}{k}$, where $w(x)$ signifies the Hamming weight of the bit string $x$ and where $h(x)=x\log(x)-(1-x)\log(1-x)$ is the binary entropy function.
Following this process, the network conducts the final routing process on $G_4$, obtained through the above transformations of edges, in an effort to route the maximum amount of key material from Alice to Bob. To do this, we use a standard max-flow algorithm, in which any flow of $n$ key-bits from node $a$ to node $b$ going through node $c$ signifies node $c$ publishing the XOR of $n$ bits from its key stores shared with $a$ and $b$ respectively, and then discarding those $n$ bits. Nodes $a$ and $b$ can then of course recover this key material, pushing it through the network until we culminate with the maximal amount of key material being shared by Alice and Bob.

\begin{figure}
    \centering
    \includegraphics{stage5.pdf}
    \caption{$G_3$ being modified, as discussed in stage 3, where $k_i$ denotes the number of key bits already shared between two nodes, and $c_i$ denotes the correlation bit string. This diagram assumes that QKD was successful on each of the error free channels established in Figure \ref{fig:stages1-3}(c).}
    \label{fig:stage5}
\end{figure}

\subsection{Single Trusted Node} \label{sec:one-trusted-node}
We now consider the scenario where a single trusted node is placed at the center of the network grid, and investigate the impact of various parameters on key rate in this scenario. Figures~\ref{fig:1TNGraphs}(a)-(d) plot the key rate when varying the fiber length, decoherence rate, BSM success rate and network size, respectively. The results show that, under all three routing algorithms, having one trusted node leads to significantly higher key rate than the same setting with no trusted node (see Fig.~\ref{fig:NoTNGraphs}).
As an example, when there is no trusted node, as shown in Fig.~\ref{fig:NoTNGraphs}(a), the maximal key rate achieved for the global algorithm was .07 key-bits/round, while it is .3 key-bits/round, more than $3\times$ higher, as shown in Fig.~\ref{fig:1TNGraphs}(a) when there is one trusted node.

Comparing Fig.~\ref{fig:1TNGraphs}(a) and Fig.~\ref{fig:NoTNGraphs}(a), we see that for the global algorithm,  when varying the fiber length from 1 to 15 km, the key rates with one trusted node are $.08$-$.25$
higher than that with no trusted node under the same setting, corresponding to a $1.9$-$4.4\times$ increase; the corresponding increases in key rate for IA and NIA algorithms are $1.2$-$8.8\times$ and $2.1$ - $9.2\times$, respectively.
In fact, with one trusted node and in the same setting, the NIA algorithm achieves greater key rates than even the global algorithm could with no trusted nodes. This is because the trusted node essentially reduces the ``size'' of the network, allowing shorter paths to be constructed between Alice/Bob and the trusted node, As the local algorithms have information on a higher fraction of the total network for smaller networks, this reduction in the effective size of the network has a particularly strong effect on the local algorithms.
\iffalse
With a baseline set, we now move to consider what one can do by adding a single trusted node to the network. Specifically, we repeat the host of simulations discussed previously, now with a trusted node located at the center of the network grid. What we find is that, while trends between parameters, algorithms, and key rate all remain constant, in every case the key rate is greatly increased by the addition the trusted node. Contrasting each of the sub-figures in Fig.~\ref{fig:1TNGraphs} with their respective counterparts in Fig.~\ref{fig:NoTNGraphs}, this increase in evident. Where, in Fig.~\ref{fig:NoTNGraphs}(a) the maximal key rate achieved for the global algorithm was .07 key-bits/round, in Fig.~\ref{fig:1TNGraphs}(a) it is more than threefold that at .3 key-bits/round. In fact, with one trusted node the NIA algorithm achieves greater key-rates than even the global algorithm could with no trusted nodes.
\fi
This trend is also exhibited in Figs.~\ref{fig:1TNGraphs}(b)-(d). Where, again comparing with their counterparts in Fig.~\ref{fig:NoTNGraphs}, we see that the addition of a trusted node results in an almost two-fold increase in maximum achievable key-rate for the cases of decoherence, BSM success rate and network size.

\iffalse Interestingly, we see that the difference in performance between the global and IA algorithms becomes less pronounced in these cases, while it was not the case in the results when varying the fiber length as shown in Fig.~\ref{fig:1TNGraphs}(a). This is likely due to the fact that, when varying fiber length, the global algorithm is able to find longer paths that the local algorithms cannot find as the length (and therefore edge-sparsity) increases. On the other hand, when varying decoherence, BSM rate or network size, the optimal paths remain easy to find. And, as they are in general shorter (and therefore easier to find) when they are between Alice/Bob and a trusted node than when they are simply between Alice and Bob (i.e., when there is no trusted node), the difference between the global and IA algorithm is, understandably, less. \OA{This doesn't actually look to be true, or i'm confused by what I meant}
\fi

In Fig.~\ref{fig:NoiseLevels}, we show the performance of the three algorithms with no trusted nodes and one trusted node in two additional channel scenarios: perfect BSM success probability with 2\% decoherence and 85\% BSM success probability with 5\% decoherence. In  Fig.~\ref{fig:NoiseLevels}(a), we see that even with the elimination of BSM failures, as the length increases between nodes the key rate still drops significantly. We see that even the NIA algorithm with a central trusted node (TN) outperforms the global algorithm with no TN, as the shorter paths between the parties and the TN are simply more likely to exist than the longer paths that must exist to connect Alice and Bob in the no TN case. In  Fig.~\ref{fig:NoiseLevels}(b) we consider a less idealized scenario, in which the BSM probability is our default of $85\%$ and our decoherence rate is higher, at $5\%$. We see that for this scenario, not even the global algorithm can achieve a positive key rate for the no TN case (at least in $10^6$ rounds of the network), and that in general the key rates achieved by the central TN is significantly lower (between $5-10\times$) than was achieved with $2\%$ decoherence in Fig.~\ref{fig:1TNGraphs}(a). It is notable, however, that in Fig.~\ref{fig:NoiseLevels}(b) we see that using 1 TN, each algorithm is able to maintain a positive key rate even when there is a 5\% decoherence rate, and Alice and Bob  are separated by 113 km (when $L=20$ km, considering a $5\times5$ network grid).

\tydubfigsingle{figs/L_01_5x5.pdf}{100\% BSM Success Prob.}{figs/E5_1TN.pdf}{5\% decoherence rate}{(a) The capabilities of the network when operating in an idealized scenario with no BSM failures (i.e. perfect repeaters) and 2\% decoherence probability. (b) The capabilities of the network with 5\% decoherence probability and 85\% BSM success probability.}{NoiseLevels}

\section{Performance Evaluation} \label{sec:perf}

In this section, we evaluate the performance of quantum key distribution in quantum networks using the various routing algorithms. We will compare the performance of the algorithms in a number of settings and investigate the impact of various parameters on the performance.

\subsection{Evaluation Setup}
We consider the scenarios where Alice and Bob are placed at the two corners of an $N\times N$ grid.
The parameters related to network topology include the size of the grid ($N$) and the length of the fiber channel of each edge (horizontal or vertical) of the grid ($L$). The quality of the quantum network is represented by the probability of a successful Bell state measurement (BSM) at a repeater ($B$), and the probability of decoherence ($D$, see Equation \ref{eq:shared-state}).   Note that $L$ is the fiber length between neighboring two nodes.  Since Alice and Bob are at opposite corners of the entire grid network, the actual distance, therefore, between the two users is actually $\sqrt{2}(N-1) L$.
Table~\ref{tab:defaults} summarizes these parameters, with their default values and range of the values.

\begin{table}
    \centering

    \caption{Parameters explored in performance evaluation. }
        \begin{tabular}{| c | c | c | p{3.8cm}|}
        \hline
        \textbf{Parameter} &  \textbf{Default} & \textbf{Range} & \textbf{Description} \\ \hline
        $N$ & 5    & 5 - 15       & The network consists of $N^2$ nodes arranged in an $N \times N$ grid. \\ \hline
        $L$ & 1 km & 1 - 20 km & The length of the fiber connecting neighboring nodes. The distance between Alice and Bob scales with both $N$ and $L$.  \\ \hline
        $B$ & .85  & 0.65 - 1.00  & Represents the quality of the repeaters. A Bell state measurement succeeds at a repeater with probability $B$. \\ \hline
        $D$ & .02  & 0.00 - 0.06  & Represents the amount of noise in the channels. EPR pairs decohere with probability $D$. \\
        \hline
        \end{tabular}
    \label{tab:defaults}
\end{table}

The performance metric is {\em key rate}, i.e., the average number of secret key-bits generated between Alice and Bob per round of network use as discussed in Section \ref{sec:model}. Unless otherwise stated, the number of rounds we simulate for each test and for each setting is $10^6$. We also evaluate the network's performance when there are no trusted nodes; a single trusted node; and two trusted nodes, along with different location configurations.

\subsection{No Trusted Nodes}

\begin{figure}[t]
	\centering

	\subfigure[Impact of fiber length.]
		\includegraphics[width=0.24\textwidth]{figs/L_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Impact of decoherence rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/E_noTN.pdf}
	} \\

	\subfigure[Impact of BSM success rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/Q_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Impact of network size.]{%
		\includegraphics[width=0.24\textwidth]{figs/S_noTN.pdf}
	}

	\caption{Impact of various parameters on key rate when there is no trusted node in the network ($5 \times 5$ grid). Note, as discussed, ``fiber length'' $L$ is the length between nodes.  Thus, the actual distance between the two users is actually $\sqrt{2}(N-1) L$.}
	\label{fig:NoTNGraphs}
\end{figure}

\iffalse
\begin{figure}[t]
	\centering

	\subfigure[Key rate vs. fiber length.]
		\includegraphics[width=0.24\textwidth]{figs/L_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Key rate vs. decoherence rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/E_noTN.pdf}
	} \\

	\subfigure[Key rate vs. BSM success rate.]{%
		\includegraphics[width=0.24\textwidth]{figs/Q_noTN.pdf}
	}
	\hspace{-.148in}
	\subfigure[Key rate vs. network size.]{%
		\includegraphics[width=0.24\textwidth]{figs/S_noTN.pdf}
	}

	\caption{Impact of various parameters on key rate when there is no trusted node in the network ($5 \times 5$ grid).}
	\label{fig:NoTNGraphs}
\end{figure}
\fi

We first investigate the scenario with no trusted node and only repeaters. These results serve as baselines to demonstrate the benefits of having trusted nodes in the network in Sections~\ref{sec:one-trusted-node} and \ref{sec:more-trusted-nodes}. Fig.~\ref{fig:NoTNGraphs}(a) plots the key rate when varying the fiber length, $L$, for a $5 \times 5$ grid. The results of the three routing algorithms are plotted in the figure. As expected, since increasing the fiber length leads to higher fiber loss, the key rate decreases with $L$. The global routing algorithm, also as expected, outperforms the two local algorithms. Between the two local algorithms, the intersection-avoidance (IA) algorithm significantly outperforms non-intersection-avoidance (NIA) algorithm, particularly for lower fiber lengths.
The difference between the global algorithm and IA algorithm is small for short fiber length, and increases when the fiber length increases, where having global knowledge allows the algorithm to find paths, even when they are longer and more complicated.

Fig.~\ref{fig:NoTNGraphs}(b) plots key rate when increasing the decoherence rate $D$. We again observe that the global routing algorithm outperforms the two local algorithms, and the IA algorithm significantly outperforms the NIA algorithm.
As expected, increasing the decoherence rate leads to lower key rates; the decrease is particularly dramatic when increasing the decoherence rate from 0 to 2\%. As an example, for the global routing algorithm, the key rate decreases from .3 key-bits/round to just over .07 key-bits/round when increasing the decoherence rate from 0 to 2\%.
We also note that, interestingly, while both the global and IA algorithms achieve a key rate around .07 at 2\% decoherence, the NIA algorithms, under the ideal condition of 0\% decoherence, achieves the same key rate of .07 key-bits/round.
The drastic advantage of the IA algorithm over the NIA algorithm highlights the importance of designing effective local routing algorithms.

Fig.~\ref{fig:NoTNGraphs}(c) plots key rate when varying $B$, the probability that the Bell state measurement at a repeater succeeds. The relative performance across the three routing algorithms is similar as the above two scenarios.
Of note, it is evident
that increasing the reliability of these measurements can lead to a significantly improved key rate. At a 75\% success rate, for example, the global algorithm achieves just under .026 key-bits/second, but an increase to 95\% or even 100\% success rates allows us to achieve key rates of approximately .153 and .216 respectively.

Last, Fig.~\ref{fig:NoTNGraphs}(d) demonstrates the impact of network size $N$ on key rate.  Note that, by increasing $N$ (the number of nodes in the network) but keeping the horizontal/vertical distance between two adjacent nodes fixed at 1 km, we are effectively increasing the total distance between Alice and Bob (they are at the two corners of the grid). For all the routing algorithms, the key rate decreases when the network size (i.e., total distance) increases. This is expected since, as the network size increases, the path between Alice and Bob becomes longer,
and therefore the overall error (see Equation \ref{eq:shared-state}) and probability of a path failing increases, leading to lower key rate. Of the three routing algorithms, the global algorithm is less affected compared with the other two algorithms since it is more capable of finding longer paths as the network size increases than the two local algorithms.

We observe that, as the distance between the end users $A$ and $B$ increases, even using quantum repeaters with perfect internal performance (i.e., $B = 1$), the efficiency of the entire network degrades rapidly (we shall discuss this further in in Fig.~\ref{fig:NoiseLevels}).  We show in the following sections how even a single trusted node can dramatically improve the performance of QKD, indicating that, even in the future as repeater technology becomes more prevalent, trusted nodes may still be necessary to ensure high key rate when the distance between end users is significant.

\input{one-trusted-node}

\input{more-trusted-node}

redpajama_set_name: RedPajamaArXiv