Entanglement-Gradient Routing for Quantum Networks

Abstract

We define the entanglement-gradient routing scheme for quantum repeater networks. The routing framework fuses the fundamentals of swarm intelligence and quantum Shannon theory. Swarm intelligence provides nature-inspired solutions for problem solving. Motivated by models of social insect behavior, the routing is performed using parallel threads to determine the shortest path via the entanglement gradient coefficient, which describes the feasibility of the entangled links and paths of the network. The routing metrics are derived from the characteristics of entanglement transmission and relevant measures of entanglement distribution in quantum networks. The method allows a moderate complexity decentralized routing in quantum repeater networks. The results can be applied in experimental quantum networking, future quantum Internet, and long-distance quantum communications.

Introduction

Finding the shortest path in an entangled quantum network is desired for improving the efficiency of quantum repeater networks of the quantum Internet, and of long-distance quantum communications^{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}. By definition, in an entangled quantum network, the quantum nodes share quantum entanglement. A transmitter and receiver node is separated by several intermediate quantum repeaters, and a chain of entangled links forms a path (entangled path) between the source and destination^{16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33}. The level of an entangled link between the quantum nodes determines the achievable hop distance and the number of spanned intermediate nodes. Since quantum networks integrate different levels of entangled links, a shortest path between a source and destination quantum node has to be found in a multi-level quantum network architecture^{19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34}. An entangled link has several relevant attributes, such as the level of entanglement (number of nodes spanned by a source-destination path), the entanglement throughput of the link that quantifies the number of entangled states transmitted at a particular fidelity^1,2,3,4. The quantum nodes receive and store the entangled states in their local quantum memories for further extension of the range of entanglement. In the quantum nodes, the number of incoming entangled states represents a crucial parameter from the modeling perspective, along with the mean number of received states (observation rate), and with the reduction in the amount of received entangled states (decay rate).

In this work, we define the entanglement-gradient routing scheme for quantum repeater networks. The proposed routing framework fuses the fundamentals of swarm intelligence^{35,36,37,38,39,40} and the results of quantum Shannon theory. Swarm intelligence provides nature-inspired solutions for problem solving. In general, it refers to some population-based meta-heuristics that are motivated by the behavior of living entities (ant colony, bee colony, flock of birds, particle swarm, bacteria foraging, etc.) interacting locally both with each other and the environment. Swarm intelligence has a wide range of applications in real-world problems, ranging from optimization tasks, data mining, computer science, database searching and knowledge discovery to bioinformatics and social networks^{35,36,37,38,39,40}.

Our entanglement-gradient routing scheme uses finds the shortest path in a decentralized manner. Motivated by the models of social insect behavior, the routing is relying on several parallel threads, where the threads represent simple, locally interacting individual swarms.

The routing and path selection for quantum repeater networks has been studied in different works^{1,2,3,4,5,23,24,25,26,27,41,42,43,44,45}. Without loss of generality, most of these approaches utilized a variance of the well-known Dijsktra’s algorithm⁴⁵ for the determination of the shortest path in the quantum network. On the other hand, these works have successfully confirmed that a shortest path algorithm from the traditional context is implementable and works well in a quantum environment. In our work we step further, and inject significant novelties to the procedures of routing and path selection in quantum networks. Our framework breaks with the practice of implementing a Dijsktra-variant algorithm or other, well-known traditional routing protocol in a quantum environment. In our solution, the shortest paths are determined by a biologically-inspired, decentralized algorithm that takes into account the physical-layer attributes of the entanglement establishment and the quantum transmission.

The entanglement gradient coefficient quantifies the attractiveness of entangled links and paths for the threads in the quantum repeater network. Each thread acts in a localized manner and the threads are attracted by the entanglement gradients of the paths. The routing is based on metrics that use the tools of quantum Shannon theory. The metrics are derived from the characteristics of entanglement transmission and relevant physical and statistical measures of entanglement distribution. To measure the relevance of a particular entangled link, we define the entanglement utility coefficient. Using the entanglement throughput characteristic extractable from the quantum network, we define the link entanglement gradient coefficient. We then extend the entanglement gradient for entangled paths (path entanglement gradient coefficient), which refers to a path formulated by entangled links.

The aim of using the threads is to find the most attractive path in the quantum network with a highest entanglement gradient (i.e., lowest inverse entanglement gradient) similar to the methods of swarm intelligence. The entanglement gradient evolves in time, decaying as the entanglement throughput deviates from a mean value (decay rate coefficient).

The threads build probabilistic paths between the quantum nodes using simple processing steps to keep minimal the complexity of the scheme. We also include a performance analysis of the routing scheme. The proposed routing method supports a moderate-complexity routing in quantum repeater networks.

Since the proposed framework has no additional physical-layer requirements, the scheme is straightforwardly applicable by current physical devices in an experimental quantum networking scenario. A physical implication of a stationary node in our quantum network model can integrate standard photonics devices^{23,24,25,26,27}, quantum memories, optical cavities and other fundamental physical devices^1,41,42. The quantum transmission between the nodes can be realized via noisy quantum links (e.g., optical fibers, wireless quantum channels, free-space optical channels, etc) and fundamental quantum transmission protocols⁴².

Since the method is based on the fundamentals of swarm intelligence theory, the proposed framework allows a fusion with the elements of quantum machine learning^43,44. By utilizing additional functions in the quantum nodes, the model provides a ground for a direct application of a distributed secure quantum machine learning method⁴⁸.

The novel contributions of this paper are as follows:

• We provide a nature-inspired, decentralized routing scheme for quantum repeater networks.

• The routing metric utilizes the attributes of entangled links, the properties of entanglement transmission and the statistical distribution of the entangled states in the quantum network.

• The method supports an efficient and moderate-complexity routing in quantum repeater networks by fusing the relevant characteristics of entanglement distribution and swarm intelligence theory.

• The scheme provides an easy experimental implementation by standard photonics devices, provides a useful tool for shortest path finding in quantum Internet and in practical long-distance quantum communications.

This paper is organized as follows. In Section 2, the preliminaries and definitions are introduced. Section 3 discusses the entanglement gradient of entangled paths, while Section 4 details the entanglement-gradient routing proposed for quantum repeater networks. In Section 5, a numerical analysis is provided. Finally, Section 6 concludes the paper. Some supplemental information is included in the Appendix.

Preliminaries

In this preliminary section, we summarize the terms and definitions.

Entanglement Utility

In the proposed model, the relevance of a particular entangled link is characterized by the entanglement utility coefficient, ${\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}$ of an entangled link ${E}_{{{\rm{L}}}_{l}}(x,y)$ between nodes $x$ and $y$, where ${{\rm{L}}}_{l}$ is the level of the entangled link (By definition, for an ${{\rm{L}}}_{l}$-level entangled link, the hop distance between quantum nodes x and y is ${2}^{l-1}$).

This amount is equivalent to the utility of the entangled link ${E}_{{{\rm{L}}}_{{\rm{l}}}}(x,y)$ that it has taken in order to arrive at the current node y from $x$ (see Fig. 1), and initialized without loss of generality as

$${\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}\ge 0$$

(1)

Figure 1

A quantum network with source node $A$ and destination node $B$, and $m$ entangled paths ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$ between them. Each path is formulated by a chain of entangled links between quantum repeater nodes. The actual network topology between $A$ and $B$ is unknown (depicted by the cloud) and paths ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$ abstract all entangled links and noise between $A$ and $B$. A section of path ${{\mathscr{P}}}_{1}$ is illustrated by an ${{\rm{L}}}_{l}$-level entangled link ${E}_{{{\rm{L}}}_{l}}(x,y)$ between nodes(x, y) of the particular path.

Let $A$ be the source quantum node and $B$ the target repeater node. Let $y$ be the current node with a direct neighbor $x$ and an established entangled link ${E}_{{{\rm{L}}}_{{\rm{l}}}}(x,y)$ between $x$ and $y$.

Let ${B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))$ refer to the entanglement throughput of a given ${{\rm{L}}}_{l}$-level entangled link ${E}_{{{\rm{L}}}_{{\rm{l}}}}(x,y)$ between nodes (x, y) measured in the number of $d$-dimensional entangled states per sec at a particular entanglement fidelity $F$ ^1,3,4.

In our scheme, at a given ${B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))$, the update of an initial ${\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}$ entanglement utility of link ${E}_{{{\rm{L}}}_{{\rm{l}}}}(x,y)$ to ${\lambda ^{\prime} }_{{E}_{{{\rm{L}}}_{l}}(x,y)}$ ^{24,25,26,32,33} is defined as

$$\begin{array}{l}\lambda {\text{'}}_{{E}_{{{\rm{L}}}_{l}}(x,y)}={(\frac{1}{{\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}}+{B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y)))}^{-1}\\ \quad \quad \quad =\frac{{\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}}{1+{B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y)){\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}},\end{array}$$

(2)

where ${B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))$ serves as a cost function between node pair (x, y) which is added to the inverse of the current entanglement utility, i.e., $1/{\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}$. The update mechanism of (2) is therefore formulates the evolution of entanglement utility in the destination node $y$. Utilizing the fundamental updating methods of swarm intelligence^38,39,40,46, (2) provides a solution to take into account not just the characteristic of entanglement transmission, but also the physical attributes of quantum links.

Link Entanglement Gradient

The attractiveness of a particular quantum node is characterized by the link entanglement gradient coefficient. Let ${{\mathscr{G}}}_{A,x}^{y}$ be the amount of entanglement gradient from source node $A$, on the neighbor node $x$ at $y$, initialized as ${{\mathscr{G}}}_{A,x}^{y}\ge 0$. The entanglement gradient is updated in a particular quantum node $y$, as follows.

Motivated by the fundamentals of swarm intelligence theory^{38,39,40,46,47}, using (2) the entanglement gradient ${{\mathscr{G}}}_{A,x}^{y}$ (link entanglement gradient) at current node $y$ and entangled link ${E}_{{{\rm{L}}}_{l}}(x,y)$ is updated to ${\mathscr{G}}{\text{'}}_{A,x}^{y}$ as

$${\mathscr{G}}{\text{'}}_{A,x}^{y}={{\mathscr{G}}}_{A,x}^{y}f(-\tau ({\rm{\Delta }}{B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))))+\lambda {\text{'}}_{{E}_{{{\rm{L}}}_{l}}(x,y)},$$

(3)

where $\tau \ge 0$ is a decay rate of entanglement gradient, function $f(x)$ provides a probability distribution, while the entanglement throughput deviation parameter, $\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))$, is defined as

$$\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))=|\frac{{\sum }_{h=1}^{n}{B}_{F}({E}_{{{\rm{L}}}_{l}}(y,h))}{n}-{B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))|,$$

(4)

where $n$ is the number of direct connections of node $y$, $\sum _{h=1}^{n}{B}_{F}({E}_{{{\rm{L}}}_{l}}(y,h))$ is the total entanglement throughput of all $n$ direct links of node $y$, while ${B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y))$ is the entanglement throughput of link ${E}_{{{\rm{L}}}_{l}}(x,y)$ between nodes $y$ and $x$.

For all other neighbors $j$, $j=1,\ldots ,n$, $j\in V-x$, the entanglement gradient ${{\mathscr{G}}}_{A,i}^{y}$ is only decreased by a factor $f(-\tau ({\rm{\Delta }}{B}_{F}({E}_{{{\rm{L}}}_{l}}(j,y))))$, thus

$${\mathscr{G}}{\text{'}}_{A,j}^{y}={{\mathscr{G}}}_{A,j}^{y}f(-\tau (\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(j,y)))),$$

(5)

where

$$\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(j,y))=|\frac{{\sum }_{h=1}^{n}{B}_{F}({E}_{{{\rm{L}}}_{l}}(y,h))}{n}-{B}_{F}({E}_{{{\rm{L}}}_{l}}(j,y))|$$

(6)

where ${B}_{F}({E}_{{{\rm{L}}}_{l}}(y,i))$ is the entanglement throughput of link ${E}_{{{\rm{L}}}_{l}}(y,i)$ between nodes $y$ and $i$.

By some fundamental theory on swarm intelligence^{35,36,37,38,39,40,46,47}, we set the exponential distribution function for $f(x)$, as

$$f(x)={e}^{x},$$

(7)

from which (3) is as

$${\mathscr{G}}{\text{'}}_{A,x}^{y}={{\mathscr{G}}}_{A,x}^{y}{e}^{-\tau (\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y)))}+\lambda {\text{'}}_{{E}_{{{\rm{L}}}_{l}}(x,y)},$$

(8)

while (5) can be rewritten as

$${\mathscr{G}}{\text{'}}_{A,j}^{y}={{\mathscr{G}}}_{A,j}^{y}{e}^{-\tau (\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(j,y)))}$$

(9)

Stochastic Model of Entanglement Utility

Let focus on the ${{\mathscr{G}}}_{A,x}^{y}$ evolution (see (3)) at a given ${\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}$ entanglement utility of link ${E}_{{{\rm{L}}}_{l}}(x,y)$ between a current node $y$, and a previous node $x$. Since the entanglement utility of a given link ${E}_{{{\rm{L}}}_{l}}(x,y)$ evolves in time (see (2)) for ${E}_{{{\rm{L}}}_{l}}(x,y)$, the ${\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}$ entanglement utility can be modeled as a non-negative, non-stationary random^38,39 process ${X}_{{E}_{{{\rm{L}}}_{l}}(x,y)}^{y}(t)$, with mean ${\mu }_{{E}_{{{\rm{L}}}_{l}}(x,y)}^{y}(t)$. As follows, ${\lambda }_{{E}_{{{\rm{L}}}_{l}}(x,y)}$ provides a sample of process ${X}_{{E}_{{{\rm{L}}}_{l}}(x,y)}^{y}(t)$.

Let $E[{X}_{{E}_{{{\rm{L}}}_{l}}(x,y)}^{y}(t)]$ be the estimate of ${X}_{{E}_{{{\rm{L}}}_{l}}(x,y)}^{y}(t)$, defined as

$$E[{X}_{({E}_{({L}_{l})}(x,y)}^{y}(t)]={X}_{({E}_{({L}_{l})}(x,y)}^{y}(t){\ast {\rm{\Omega }}}_{{{\mathscr{G}}}_{(A,x)}^{y}(t)},$$

(10)

where * is the convolution operator, while function ${{\rm{\Omega }}}_{{{\mathscr{G}}}_{A,x}^{y}}(t)$ is defined as

$${{\rm{\Omega }}}_{{{\mathscr{G}}}_{A,x}^{y}}(t)={e}^{-\tau (\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(x,y)))}U(t),$$

(11)

where $U(t)$ is the unit step function.

Assuming that the individual samples of ${X}_{{E}_{{{\rm{L}}}_{l}}(x,y)}^{y}(t)$ within a time period ${\rm{\Delta }}T$ are determined, a ${\perp }_{{{\mathscr{G}}}_{A,x}^{y}}({\rm{\Delta }}T)$ correlation function can be defined as

$${\perp }_{{{\mathscr{G}}}_{A,x}^{y}}({\rm{\Delta }}T)={e}^{-\tau |{\rm{\Delta }}T|}.$$

(12)

Link Selection Probability

Using the entanglement gradient ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{z,B}^{y}$ in a current node $y$ with neighbor node $z$, the ${\rm{P}}{{\rm{r}}}_{{E}_{{{\rm{L}}}_{l}}(y,z)}^{y}$ probability that from node $y$ the entangled link ${E}_{{{\rm{L}}}_{l}}(y,z)$ is selected to reach destination $B$ is defined as

$${{\rm{\Pr }}}_{{E}_{{{\rm{L}}}_{l}}(y,z)}^{y}=\frac{{({\mathscr{G}}{\text{'}}_{z,B}^{y}+\partial )}^{\chi }}{{\sum }_{k}{({\mathscr{G}}{\text{'}}_{k,B}^{y}+\partial )}^{\chi }}=\frac{{(({{\mathscr{G}}}_{z,B}^{y}{e}^{-\tau (\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(y,z)))}+\lambda {^{\prime} }_{{E}_{{{\rm{L}}}_{l}}(y,z)})+\partial )}^{\chi }}{{\sum }_{k}{(({{\mathscr{G}}}_{k,B}^{y}{e}^{-\tau (\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(y,k)))})+\partial )}^{\chi }},$$

(13)

where $k\in V-y$, $V$ is the set of nodes of the entangled quantum network $N$, $\partial \ge 0$ is a threshold parameter, while X ≥ 0 is a tuning parameter. A source-dependent link selection model is discussed in Section S.1.

Path Entanglement-Gradient

The relevance of a particular path of the network is characterized by the path entanglement gradient coefficient.

In this section, we extend the entanglement gradient to entangled paths, which refers to the paths between source and target nodes in the quantum network that are formed by a chain of entangled links between quantum repeaters (i.e., paths of entangled links).

The network model used for the entanglement-gradient routing scheme is illustrated in Fig. 1. There are $m$ entangled paths, ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$ between a source node $A$ and destination node $B$. Each entangled path ${{\mathscr{P}}}_{i}$, $i=1,\ldots ,m$, is formulated by a chain of entangled links between quantum repeaters.

Path Metrics

In this section, we focus on the entanglement gradients of the $m$ entangled paths ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$ between a source node $A$ and target node $B$.

Let ${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A}$ refer to the path entanglement gradient of a given entangled path ${{\mathscr{P}}}_{i}$, i = 1$,\ldots ,\,m$ at source node $A$. Let ${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{B}$ be the initial path entanglement gradient of ${{\mathscr{P}}}_{i}$ at destination node B ^24,25,26,32. Let ${\kappa }_{A}$ be the mean number of $d$-dimensional entangled states arriving at $A$ and ${\kappa }_{B}$ be the mean number arriving at $B$; therefore, the total observation rate is

$${\kappa }_{AB}={\kappa }_{A}+{\kappa }_{B}.$$

(14)

Note that, assuming a symmetrical arrival of the entangled states, ${\kappa }_{A}={\kappa }_{B}={\kappa }_{{AB}}/2$.

The derivation of updated ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{A}$ at the source node $A$ for a given path ${{\mathscr{P}}}_{i}$ is as follows. Let ${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A}$ be the initial gradient in $A$ and let ${{\mathscr{P}}}_{i}$, characterized by a ${X}_{{{\mathscr{P}}}_{i}}^{A}(t)$, be the non-stationary random process with mean ${\mu }_{{{\mathscr{P}}}_{i}}^{A}$ (average value of received entanglement gradient).

First, ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{A}$ is decomposed to

$${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{A}={{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({\kappa }_{A},{\tau }_{A})}+{{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({{\mathscr{P}}}_{i})}+{{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({{\mathscr{P}}}_{j})},$$

(15)

where the first term, ${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({\kappa }_{A},{\tau }_{A})}$, is the entanglement gradient update in $A$, evaluated as

$${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({\kappa }_{A},{\tau }_{A})}=\frac{{\kappa }_{A}}{{\kappa }_{AB}}(\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{A}}){{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A},$$

(16)

where ${\tau }_{A}$ is the decay rate of $A$.

The second term ${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({{\mathscr{P}}}_{i})}$ models the entanglement gradient update for the given path ${{\mathscr{P}}}_{i}$ as

$${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({{\mathscr{P}}}_{i})}={{\rm{\Pr }}}_{{{\mathscr{P}}}_{i}}^{B}(\frac{{\kappa }_{B}}{{\kappa }_{AB}}((\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{A}}){{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A}+({\mu }_{{{\mathscr{P}}}_{i}}^{A}))),$$

(17)

where ${\mu }_{{{\mathscr{P}}}_{i}}^{A}$ is the average value of received entanglement gradient from path ${{\mathscr{P}}}_{i}$ at node $A$, while ${\rm{P}}{{\rm{r}}}_{{{\mathscr{P}}}_{i}}^{B}$ is the probability that path ${{\mathscr{P}}}_{i}$ will be used by $B$, ${\rm{P}}{{\rm{r}}}_{{{\mathscr{P}}}_{i}}^{B}={({{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{B}+\partial )}^{\chi }/{\sum _{m}({{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{B}+\partial )}^{\chi }$.

The third term, ${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({{\mathscr{P}}}_{j})}$ models the path entanglement gradient update for a different path ${{\mathscr{P}}}_{j}$, $j\ne i$ as

$${{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A,({{\mathscr{P}}}_{j})}={{\rm{\Pr }}}_{{{\mathscr{P}}}_{j}}^{B}(\frac{{\kappa }_{B}}{{\kappa }_{AB}}((\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{A}}){{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A})),$$

(18)

where ${\rm{P}}{{\rm{r}}}_{{{\mathscr{P}}}_{j}}^{B}$ is the probability that ${{\mathscr{P}}}_{j}$ will be used by $B$, ${\rm{P}}{{\rm{r}}}_{{{\mathscr{P}}}_{j}}^{B}={({{\mathscr{G}}}_{{{\mathscr{P}}}_{j}}^{B}+\partial )}^{\chi }/{\sum _{m}({{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{B}+\partial )}^{\chi }$.

From (16), (17), and (18), ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{A}$ in (15) can be rewritten for a particular path ${{\mathscr{P}}}_{i}$ as

$${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{A}=(\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{A}}){{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A}+(\frac{{\kappa }_{B}}{{\kappa }_{AB}}){{\rm{\Pr }}}_{{{\mathscr{P}}}_{i}}^{B}({\mu }_{{{\mathscr{P}}}_{i}}^{A}).$$

(19)

Following the same steps for path ${{\mathscr{P}}}_{j}$, $j\ne i$, ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{j}}^{A}$ is evaluated at node $A$, for all instances of $j$, as

$${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{j}}^{A}=(\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{A}}){{\mathscr{G}}}_{{{\mathscr{P}}}_{j}}^{A}+(\frac{{\kappa }_{B}}{{\kappa }_{AB}}){{\rm{\Pr }}}_{{{\mathscr{P}}}_{j}}^{B}({\mu }_{{{\mathscr{P}}}_{j}}^{A}).$$

(20)

At target node $B$, the corresponding formula for path ${{\mathscr{P}}}_{i}$, ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{B}$ is therefore yielded as

$${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{B}=(\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{B}}){{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{B}+(\frac{{\kappa }_{A}}{{\kappa }_{AB}}){{\rm{\Pr }}}_{{{\mathscr{P}}}_{i}}^{A}({\mu }_{{{\mathscr{P}}}_{i}}^{B}),$$

(21)

where ${\mu }_{{{\mathscr{P}}}_{i}}^{B}$ is the average value of received entanglement gradient from path ${{\mathscr{P}}}_{i}$ at node $B$, ${\rm{P}}{{\rm{r}}}_{{{\mathscr{P}}}_{i}}^{A}$ is the probability that path ${{\mathscr{P}}}_{i}$ will be used by $A$, and ${\rm{P}}{{\rm{r}}}_{{{\mathscr{P}}}_{i}}^{A}={({{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A}+\partial )}^{\chi }/{\sum _{m}({{\mathscr{G}}}_{{{\mathscr{P}}}_{i}}^{A}+\partial )}^{\chi }$.

The formula of ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{j}}^{B}$ for path ${{\mathscr{P}}}_{j}$, $j\ne i$ at target node $B$ is therefore

$${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{j}}^{B}=(\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{B}}){{\mathscr{G}}}_{{{\mathscr{P}}}_{j}}^{B}+(\frac{{\kappa }_{A}}{{\kappa }_{AB}}){{\rm{\Pr }}}_{{{\mathscr{P}}}_{j}}^{A}({\mu }_{{{\mathscr{P}}}_{j}}^{B}),$$

(22)

where ${{\rm{\Pr }}}_{({P}_{j})}^{A}\,{\rm{is}}\,{{\rm{\Pr }}}_{({P}_{j})}^{A}={({{\mathscr{G}}}_{({P}_{j})}^{A}+\partial )}^{\chi }/{\sum }_{m}{({{\mathscr{G}}}_{({P}_{i})}^{A}+\partial )}^{\chi }$.

For the ${{\mathscr{P}}}^{\ast }$ optimal shortest path, the entanglement gradient is maximal, thus ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}^{\ast }}^{A}$ is determined as

$$\begin{array}{rcl}{\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}^{\ast }}^{A} & = & \mathop{{\rm{\max }}}\limits_{\forall i}{\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{A}\\ & = & (\frac{{\kappa }_{AB}}{{\kappa }_{AB}+{\tau }_{A}}){{\mathscr{G}}}_{{{\mathscr{P}}}^{\ast }}^{A}+(\frac{{\kappa }_{B}}{{\kappa }_{AB}}){{\rm{\Pr }}}_{{{\mathscr{P}}}^{\ast }}^{B}({\mu }_{{{\mathscr{P}}}^{\ast }}^{A}),\end{array}$$

(23)

Mean of path entanglement gradient

After some calculations, the mean entanglement gradient ${\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{A})$ of a particular path ${{\mathscr{P}}}_{i}$ at ${A}$ is obtainable if the path ${{\mathscr{P}}}_{i}$ is selected with unit probability in $A$, ${{\rm{\Pr }}}_{{{\mathscr{P}}}_{i}}^{A}=1$, yielding ${\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{A})$ as

$${\mathbb{E}}({\mathscr{G}}{^{\prime} }_{{{\mathscr{P}}}_{i}}^{A})=\frac{({\kappa }_{AB}+{\tau }_{A}){\kappa }_{B}}{{\kappa }_{AB}{\tau }_{A}}{\mu }_{{{\mathscr{P}}}_{i}}^{A}.$$

(24)

By similar assumptions, the ${\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{B})$ mean entanglement gradient of a particular path ${{\mathscr{P}}}_{i}$ at $B$, obtainable at ${\rm{P}}{{\rm{r}}}_{{{\mathscr{P}}}_{i}}^{B}=1$, is

$${\mathbb{E}}({\mathscr{G}}{^{\prime} }_{{{\mathscr{P}}}_{i}}^{B})=\frac{({\kappa }_{AB}+{\tau }_{B}){\kappa }_{A}}{{\kappa }_{AB}{\tau }_{B}}{\mu }_{{{\mathscr{P}}}_{i}}^{B}.$$

(25)

Decay Rate of Mean Path Entanglement Gradient

A crucial parameter for the optimization of the entanglement-gradient routing is the ${\tau }_{{{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{n}}$ decay rate of mean path entanglement gradient ${\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{n})$.

Without loss of generality, at a given expected amount of entanglement gradient ${\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{n})$ at node $n$ for path ${{\mathscr{P}}}_{i}$, the threshold ${\partial }_{{\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{n})}$ can be rewritten as:

$${\partial }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}={\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}){e}^{-\phi ({{\mathscr{P}}}_{i}){\tau }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}},$$

(26)

where $\phi ({{\mathscr{P}}}_{i})$ characterizes the deviation of a current ${B}_{F}({{\mathscr{P}}}_{i})$ entanglement throughput (measured in $d$-dimensional entangled states of a particular fidelity $F$ per sec) of path ${{\mathscr{P}}}_{i}$ from an expected ${\widetilde{B}}_{F}({{\mathscr{P}}}_{i})$ entanglement throughput of path ${{\mathscr{P}}}_{i}$ as

$$\phi ({{\mathscr{P}}}_{i})=|{\tilde{B}}_{F}({{\mathscr{P}}}_{i})-{B}_{F}({{\mathscr{P}}}_{i})|.$$

(27)

and therefore ${\tau }_{{\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{n})}$ is^38,39,40,46

$${\tau }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}=-\mathrm{ln}\,\frac{{\partial }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}}{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})\phi ({{\mathscr{P}}}_{i})}=-\mathrm{ln}\,\frac{{\partial }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}}{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})|{\tilde{B}}_{F}({{\mathscr{P}}}_{i})-{B}_{F}({{\mathscr{P}}}_{i})|}.$$

(28)

Optimal estimator

The ${\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{^{\prime} }_{{{\mathscr{P}}}_{i}}^{n})}$ optimal estimator of ${\tau }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}$ is derived as follows. Using (12) with (27) allows us to evaluate a variable $Y$ as

$$Y=\,{\perp }_{{\mathbb{E}}({\mathscr{G}}{^{\prime} }_{{{\mathscr{P}}}_{i}}^{n})}(\phi ({{\mathscr{P}}}_{i}))={e}^{-{\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}\phi ({{\mathscr{P}}}_{i})},$$

(29)

from which the ${\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}$ optimal estimate of the ${\tau }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}$ of ${\mathbb{E}}({{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{n})$ is yielded as^38,39,40,46

$${\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}=-\frac{\mathrm{ln}\,Y}{\phi ({{\mathscr{P}}}_{i})}=-\frac{\mathrm{ln}({e}^{-{\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}\phi ({{\mathscr{P}}}_{i})})}{\phi ({{\mathscr{P}}}_{i})}.$$

(30)

At a given optimal decay rate ${\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}$ (30), using (24) in (26) results in ${\partial }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}$ as

$${\partial }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}=\frac{({\kappa }_{AB}+{\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})})}{2{\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}}{\mu }_{{{\mathscr{P}}}_{i}}^{n}{e}^{-{\tilde{\tau }}_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})}\phi ({{\mathscr{P}}}_{i})}.$$

(31)

Path Selection

A brief description of the method to determine the entanglement gradient of the paths for characterization of an optimal path ${{\mathscr{P}}}^{\ast }$ is as follows.

Method

Step 1. Let $n-1$ and $n$ be a pair of neighbor quantum repeaters of a path between source node $A$ and target node $B$. Let $n$ be the current node, $n-1$ be the previous node, and $n+1$ be a next node.

Step 2. Apply (2) to increase the entanglement utility of the entangled link between $n-1$ and $n$. For node $n-1$, increase entanglement gradient via (3). For all other neighboring nodes, decrease entanglement gradient via (5).

Step 3. From the updated entanglement gradients, compute ${\rm{P}}{{\rm{r}}}_{{E}_{{{\rm{L}}}_{l}}(n,n+1)}^{n}$ of entangled link ${E}_{{{\rm{L}}}_{l}}(n,n+1)$ via (13).

Step 4. Apply steps 1–3 for all nodes and paths, ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$. Determine optimal $\widetilde{\tau }$ via (30) to set $\tau$.

Step 5. Using (23), output optimal path ${{\mathscr{P}}}^{\ast }$ for which the entanglement gradient is maximal is ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}^{\ast }}^{A}=\mathop{\max }\limits_{\forall i}{{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{i}}^{A}$.

Entanglement-Gradient Routing

In this section, we define a decentralized routing scheme that merges the results of the previous sections on the quantities of entanglement gradient. The routing is executed through parallel threads that simultaneously explore the quantum network. A given thread operates in a localized manner.

Link Selection

For a given path ${{\mathscr{P}}}_{i}$ between a source node $s$ and current node $n$, a quantity ${{\rm{\Phi }}}_{{{\mathscr{P}}}_{i}}^{s,n}$ is defined as

$${{\rm{\Phi }}}_{{{\mathscr{P}}}_{i}}^{s,n}=\sum _{x=s}^{n}\,\alpha {\sigma }_{{{\mathscr{P}}}_{i}}^{x},$$

(32)

where

$${\sigma }_{{{\mathscr{P}}}_{i}}^{x}=\,\mathrm{log}(\frac{{\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{x+1\in {{\mathscr{P}}}_{i}}}{{\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{x\in {{\mathscr{P}}}_{i}}}),$$

(33)

where ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{k}}^{x\in {{\mathscr{P}}}_{i}}$ is the entanglement gradient of node $x\in {{\mathscr{P}}}_{i}$, ${{\mathscr{G}}{\mathscr{^{\prime} }}}_{{{\mathscr{P}}}_{k}}^{x+1\in {{\mathscr{P}}}_{i}}$ is the entanglement gradient at node $x+1\in {{\mathscr{P}}}_{i}$, and $\alpha$ is

$$\alpha =\{\begin{array}{l}1,if|{\sigma }_{{{\mathscr{P}}}_{i}}^{x}| > \vartheta \\ 0,if|{\sigma }_{{{\mathscr{P}}}_{i}}^{x}|\le \vartheta \end{array},$$

(34)

where $\vartheta$ is a threshold⁴⁰.

Using (32), a mean ${\mu }^{n}({{\rm{\Phi }}}_{{\mathscr{P}}}^{s,n})$ for the $m$ paths ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$ between a source node $s$ and a current node $n$ is

$${\mu }^{n}({{\rm{\Phi }}}_{{\mathscr{P}}}^{s,n})=\frac{{\sum }_{i=1}^{m}\,{{\rm{\Phi }}}_{{{\mathscr{P}}}_{i}}^{s,n}}{m}.$$

(35)

A model of a node $n$ with next node $z$ and $m$ paths ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$ between a source node $s$ is depicted in Fig. 2. The entanglement gradients are ${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}$, $i=1,\ldots ,m$. Nodes $n$ and $z$ are elements of a current path ${{\mathscr{P}}}_{i}$, with corresponding entanglement gradients ${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n\in {{\mathscr{P}}}_{i}}$ and ${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{z\in {{\mathscr{P}}}_{i}}$. From the path gradients, the quantities of ${\sigma }_{{{\mathscr{P}}}_{i}}^{x}$ (33) and $\alpha$ (34) are derived to evaluate ${{\rm{\Phi }}}_{{{\mathscr{P}}}_{i}}^{s,n}$ in (32).

Figure 2

A model of $m$ paths ${{\mathscr{P}}}_{1},\ldots ,{{\mathscr{P}}}_{m}$ between a source node $s$ and a current node $n$. The paths have entanglement gradients ${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}$, $i=1,\ldots ,m$. Current node $n$ and next node $z$ are elements of a current path ${{\mathscr{P}}}_{i}$ (blue), with ${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n\in {{\mathscr{P}}}_{i}}$ in $n$ and ${\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{z\in {{\mathscr{P}}}_{i}}$ in $z$.

Let $z$ be the next node from actual node $n$ on a current path ${{\mathscr{P}}}_{i}$ with entangled connection ${E}_{{{\rm{L}}}_{l}}(n,z)$. Then, for ${E}_{{{\rm{L}}}_{l}}(n,z)$, the distance function $\psi (n,z)$ between $n$ and $z$ is defined as

$$\begin{array}{l}\psi (n,z)=(\frac{1}{{{\rm{\Pr }}}_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{n}})|{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})-{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{z})|\\ =(\frac{{\sum }_{k}{({\mathscr{G}}{\text{'}}_{k,B}^{n}+\partial )}^{\chi }}{{({\mathscr{G}}{\text{'}}_{z,B}^{n}+\partial )}^{\chi }})|{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})-{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{z})|,\end{array}$$

(36)

where ${{\rm{\Pr }}}_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{n}$ is (13), while ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})$ and ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{z})$ are the mean entanglement gradients at nodes $n\in {{\mathscr{P}}}_{i}$ and $z\in {{\mathscr{P}}}_{i}$, evaluated via (24) and (25) as

$${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})=\frac{({\kappa }_{nz}+{\tau }_{n}){\kappa }_{z}}{{\kappa }_{nz}{\tau }_{n}}{\mu }_{{{\mathscr{P}}}_{i}}^{n},$$

(37)

where ${\mu }_{{{\mathscr{P}}}_{i}}^{n}$ is the average value of the received entanglement gradient from path ${{\mathscr{P}}}_{i}$ at node $n$, and

$${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{z})=\frac{({\kappa }_{nz}+{\tau }_{z}){\kappa }_{n}}{{\kappa }_{nz}{\tau }_{z}}{\mu }_{{{\mathscr{P}}}_{i}}^{z},$$

(38)

where ${\mu }_{{{\mathscr{P}}}_{i}}^{z}$ is the average value of the received entanglement gradient from path ${{\mathscr{P}}}_{i}$ at node $z$, respectively.

The decentralized routing is accomplished via $t$ parallel threads, ${{\mathscr{T}}}_{1},\ldots ,{{\mathscr{T}}}_{t}$. For all threads, a threshold ${\ell }_{{\mathscr{T}}}$ is defined, which determines the maximal number of nodes to be explored. Using the ${\mathscr{G}}{\text{'}}_{A,n}^{z}$ entanglement link gradient (see (8)), with the entanglement utility $\lambda {\text{'}}_{{E}_{{{\rm{L}}}_{l}}(n,z)}$ (2) of link ${E}_{{{\rm{L}}}_{l}}(n,z)$ between nodes $n$ and $z$, an inverse link entanglement gradient ${\theta }_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{z}$ is defined as

$${\theta }_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{z}=\frac{1}{{\mathscr{G}}{\text{'}}_{A,n}^{z}}=\frac{1}{{{\mathscr{G}}}_{A,n}^{z}{e}^{-\tau (\Delta {B}_{F}({E}_{{{\rm{L}}}_{l}}(n,z)))}+\lambda {^{\prime} }_{{E}_{{{\rm{L}}}_{l}}(n,z)}},$$

(39)

where $\lambda {\text{'}}_{{E}_{{{\rm{L}}}_{l}}(n,z)}$ is

$$\lambda {^{\prime} }_{{E}_{{{\rm{L}}}_{l}}(n,z)}=\frac{{\lambda }_{{E}_{{{\rm{L}}}_{l}}(n,z)}}{1+{B}_{F}({E}_{{{\rm{L}}}_{l}}(n,z)){\lambda }_{{E}_{{{\rm{L}}}_{l}}(n,z)}}.$$

(40)

Then, for a given $i$-th thread ${{\mathscr{T}}}_{i}$, the ${p}_{{{\mathscr{T}}}_{i}}(n,z)$ link selection probability is defined as

$${p}_{{{\mathscr{T}}}_{i}}(n,z)=\{\begin{array}{l}{{\rm{\Pr }}}_{{{\mathscr{T}}}_{i}}(n,z),ifz\notin {{\rm{S}}}_{{{\mathscr{T}}}_{i}}\\ 0,{\rm{otherwise}},\end{array}$$

(41)

where ${{\rm{S}}}_{{{\mathscr{T}}}_{i}}$ is a set of nodes already visited by the $i$-th thread ${{\mathscr{T}}}_{i}$ ⁴⁰ $,$ while ${{\rm{\Pr }}}_{{{\mathscr{T}}}_{i}}(n,z)$ is

$${{\rm{\Pr }}}_{{{\mathscr{T}}}_{i}}(n,z)=\frac{{({\theta }_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{z})}^{{C}_{1}}{(\psi (n,z))}^{{C}_{2}}}{{\sum }_{k\notin {{\rm{S}}}_{{{\mathscr{T}}}_{i}}}{({\theta }_{{E}_{{{\rm{L}}}_{l}}(n,k)}^{k})}^{{C}_{1}}{(\psi (n,k))}^{{C}_{2}}},$$

(42)

where $k\notin {{\rm{S}}}_{{{\mathscr{T}}}_{i}}$, ${C}_{1}$, and ${C}_{2}$ are weighting parameters to balance the relevance between inverse entanglement gradient function $\theta (\cdot )$ and distance function $\psi (\cdot )$.

The remaining quantities of (42) are evaluated as

$${\theta }_{{E}_{{{\rm{L}}}_{l}}(n,k)}^{k}=\frac{1}{{\mathscr{G}}{\text{'}}_{A,n}^{k}},$$

(43)

and

$$\psi (n,k)={{\rm{\Pr }}}_{{E}_{{{\rm{L}}}_{l}}(n,k)}^{n}|{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n})-{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{k})|.$$

(44)

Algorithm

A brief description of the entanglement-gradient routing algorithm ${{\mathscr{A}}}_{{\mathscr{G}}}$ for finding the shortest path via the entanglement gradient is as follows.

Algorithm (entanglement-gradient routing)

Step 1. Set $t$ and ${\ell }_{{\mathscr{T}}}$ for threads ${{\mathscr{T}}}_{1},\ldots ,{{\mathscr{T}}}_{t}$, where ${\ell }_{{\mathscr{T}}}$ is a thread-threshold that limits the maximal number of nodes to be explored to ${\ell }_{{\mathscr{T}}}$ by a given ${{\mathscr{T}}}_{i}$. For a given ${{\mathscr{T}}}_{i}$, let ${{\rm{S}}}_{{{\mathscr{T}}}_{i}}$ be a set of already visited nodes.

Step 2. For a thread ${{\mathscr{T}}}_{i}$, given node $n\,$and next node $z$, determine ${p}_{{{\mathscr{T}}}_{i}}(n,z)$ via (41). If $z\notin {{\rm{S}}}_{{{\mathscr{T}}}_{i}}$, set ${p}_{{{\mathscr{T}}}_{i}}(n,z)=0$; otherwise, calculate ${{\rm{\Pr }}}_{{{\mathscr{T}}}_{i}}(n,z)$ via (42).

Step 3. As a next node $n+1$ is determined, update inverse link entanglement gradient ${\theta }_{{E}_{{{\rm{L}}}_{l}}(n,n+1)}^{n+1}$ via (39).

Step 4. Apply steps 1–3 for all threads, ${{\mathscr{T}}}_{1},\ldots ,{{\mathscr{T}}}_{t}$.

Discussion

In ${{\mathscr{A}}}_{{\mathscr{G}}}$, any thread ${{\mathscr{T}}}_{i}$ at a given step selects that node for which the entanglement gradient is high, i.e., the inverse link entanglement gradient of the entangled connection is low. When the inverse link entanglement gradient is high, the threads choose a different direction and entangled links. The thread threshold ${\ell }_{{\mathscr{T}}}$ allows for focus on a particular subset of the network for an optimal parallel realization. The distance function of (36) takes into consideration not just the absolute entanglement-gradient difference but also the inverse of the probability of the selection of a given entangled link. The threads also change their behavior as the entanglement-gradients evolve in the network, which yields dynamically changing adaptive searching.

For a given thread ${{\mathscr{T}}}_{i}$, the ${C}_{1}$ and ${C}_{2}$ weighting coefficients are crucial in the probability function of (42) for determining the local behavior of a given thread (e.g., the routing is decentralized). The selection method of these weights is discussed next.

Computational Complexity

The computational complexity of the entanglement-gradient routing at $|N|$ nodes, with $t$ parallel threads and a thread-threshold ${\ell }_{{\mathscr{T}}}$, is at most

$${\mathscr{O}}(|N|t\,{\ell }_{{\mathscr{T}}}).$$

(45)

The result of (45) can be verified easily, since the maximal number of nodes visited by a given thread ${{\mathscr{T}}}_{i}$ is at most ${\ell }_{{\mathscr{T}}}$.

Numerical Evidence

In this section, we analyze the performance metrics of the link and path selection phases and the entanglement-gradient routing.

Link and Path Metrics

In this section, the proposed link and path metrics are analyzed. The decay rate ${\tau }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})}$ (28) of entanglement gradient ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})$ for various $\phi ({{\mathscr{P}}}_{i})$ at ${\partial }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})}=1$ and ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})=2$ is depicted in Fig. 3(a). The ${\tau }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})}$ decay rate of entanglement gradient increases with the $\phi ({{\mathscr{P}}}_{i})$ parameter of the given path ${{\mathscr{P}}}_{i}$. As the ${B}_{F}({{\mathscr{P}}}_{i})$ entanglement throughput of that path ${{\mathscr{P}}}_{i}$ significantly deviates from the expected average ${\tilde{B}}_{F}({{\mathscr{P}}}_{i})$, the entanglement gradient of ${{\mathscr{P}}}_{i}$ decreases more significantly.

Figure 3

(a) The decay rate ${\tau }_{{\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})}$ (log-scale) of entanglement gradient ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})$ for path ${{\mathscr{P}}}_{i}$, $\phi ({{\mathscr{P}}}_{i})={10}^{0},\ldots ,{10}^{8}$, and $\partial =1$, ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}})=2$. (b) The ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{A})$ of a path ${{\mathscr{P}}}_{i}$ at node $A$ as a function of ${\tau }_{A}$ at ${\kappa }_{AB}=4,{\kappa }_{B}=2$ and ${\mu }_{{{\mathscr{P}}}_{i}}^{A}=1$.

In Fig. 3(b), the ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{A})$ (see (24)) of a particular path ${{\mathscr{P}}}_{i}$ at node $A$, as a function of ${\tau }_{A}$ at ${\kappa }_{AB}=4,{\kappa }_{B}=2$ and ${\mu }_{{{\mathscr{P}}}_{i}}^{A}=1$, is depicted.

Without loss of generality, at a given ${\kappa }_{n}$ in a node $n$, let ${\nu }_{n}$ be defined as

$$\frac{-2\pi }{{\kappa }_{n}}\le {\nu }_{n}\le \frac{2\pi }{{\kappa }_{n}}.$$

(46)

Then, rewrite ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}({\nu }_{n}))$ as

$${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}({\nu }_{n}))={\mu }_{{{\mathscr{P}}}_{i}}^{n}\varsigma ({\gamma }_{n}),$$

(47)

where $\varsigma ({\gamma }_{n})$ is a peak of function $\rho ({\nu }_{n})$ and $\rho ({\nu }_{n})$ is

$$\rho ({\nu }_{n})=\frac{1}{\sqrt{1+{\gamma }_{n}^{2}-2{\gamma }_{n}\,\cos ({\nu }_{n})}},$$

(48)

where ${\gamma }_{n}$ is

$${\gamma }_{n}=\frac{{\kappa }_{n}}{{\kappa }_{n}+{\tau }_{n}}={(1+\frac{\tau }{{\kappa }_{n}})}^{-1},$$

(49)

where ${\kappa }_{n}$ is the observation rate in node $n\,$and ${\tau }_{n}$ is the decay rate of the entanglement gradient in node $n$.

The quantity of $\varsigma ({\gamma }_{n})$ is derived as follows. The formula of $\rho ({\nu }_{n})$ (see (48)) can be rewritten as a magnitude

$$\rho ({\nu }_{n})=| {\mathcal F} ({\nu }_{n})|.$$

(50)

where ${\mathcal F} ({\nu }_{n})$ is defined as

$$ {\mathcal F} ({\nu }_{n})=\frac{1}{1-{\gamma }_{n}{e}^{-i{\nu }_{n}}}.$$

(51)

Thus, the peak $\varsigma ({\gamma }_{n})$ of $\rho ({\nu }_{n})$ at a given ${\gamma }_{n}$ is yielded as

$$\varsigma ({\gamma }_{n})=\frac{1}{(1-{\gamma }_{n})}.$$

(52)

At a given ${\gamma }_{n}$ and mean ${\mu }_{{{\mathscr{P}}}_{i}}^{n}$ (average value of received entanglement gradient) at node $n$ for path ${{\mathscr{P}}}_{i}$, the mean of the received entanglement gradient can be rewritten from $\varsigma ({\gamma }_{n})$ (see (52)) as

$${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}({\nu }_{n}))={\mu }_{{{\mathscr{P}}}_{i}}^{n}\varsigma ({\gamma }_{n})=\frac{{\mu }_{{{\mathscr{P}}}_{i}}^{n}}{(1-{\gamma }_{n})}.$$

(53)

The value of $\rho ({\nu }_{n})$ as a function of ${\nu }_{n}$ for various ${\gamma }_{n}$ is depicted in Fig. 4(a). The resulting mean entanglement gradient ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}({\nu }_{n}))$, as a function of ${\mu }_{{{\mathscr{P}}}_{i}}^{n}$ for various ${\gamma }_{n}$ of path ${{\mathscr{P}}}_{i}$ at node $n$, is depicted in Fig. 4(b). As the ${\mu }_{{{\mathscr{P}}}_{i}}^{n}$ average value of the received entanglement gradient increases, the mean entanglement gradient ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}({\nu }_{n}))$ becomes more significant, specifically for high values of ${\gamma }_{n}$.

Figure 4

(a) The values of $\rho ({\nu }_{n})$ as a function of ${\nu }_{n}$ for ${\gamma }_{n}=0.1,0.5,0.8,0.9$ at node $n$. The $\varsigma ({\gamma }_{n})$ peak of $\rho ({\nu }_{n})$ at a given ${\gamma }_{n}$ is $\varsigma ({\gamma }_{n})=1/(1-{\gamma }_{n})$. (b) The mean ${\mathbb{E}}({\mathscr{G}}{\text{'}}_{{{\mathscr{P}}}_{i}}^{n}({\nu }_{n}))={\mu }_{{{\mathscr{P}}}_{i}}^{n}\varsigma ({\gamma }_{n})$ entanglement gradient received from path ${{\mathscr{P}}}_{i}$ as a function of ${\mu }_{{{\mathscr{P}}}_{i}}^{n}$ for a ${\gamma }_{n}=0.1,0.5,0.8,0.9$.

At a $0\le {\rm{\Pi }}\le 1$ tuning parameter (a fraction of peak value), let ${\kappa }_{n}^{\ast }$ be a cutoff observation rate (critical received $d$-dimensional entangled states per sec) defined at a given observation rate ${\kappa }_{n}$ as

$${\kappa }_{n}^{\ast }=\frac{{\kappa }_{n}}{2\pi }{\cos }^{-1}(\frac{{\kappa }_{n}^{2}+{\kappa }_{n}{\tau }_{n}-\frac{{\tau }_{n}^{2}+{{\rm{\Pi }}}^{2}{\tau }_{n}^{2}}{2{{\rm{\Pi }}}^{2}}}{{\kappa }_{n}^{2}+{\kappa }_{n}{\tau }_{n}}).$$

(54)

If ${\kappa }_{n} > {\kappa }_{n}^{\ast }\,$at a given ${\tau }_{n}$ and ${\rm{\Pi }}$, then in node $n$, the value of the total received entanglement gradient will not adapt to the actually received total value of entanglement gradients, i.e., ${\kappa }_{n}^{\ast }$ serves a cutoff in the observation rate.

The values of ${\kappa }_{n}^{\ast }$ as a function of ${\tau }_{n}$ for various ${\kappa }_{n}$ at ${\rm{\Pi }}=0.5$ (in analogue to a $-3$ dB cutoff^38,39,40,46) are shown in Fig. 5. The ${\kappa }_{n}^{\ast }$ cutoff observation rate is controllable by ${\tau }_{n}$ and the impact of an actual ${\kappa }_{n}$ rate on ${\kappa }_{n}^{\ast }$ is almost negligible.

Figure 5

The values of ${\kappa }_{n}^{\ast }$ as a function of ${\tau }_{n}$ for ${\kappa }_{n}={10}^{4},{10}^{5},{10}^{6},{10}^{7},{10}^{8}$ at ${\rm{\Pi }}=0.5$.

Decentralized Routing

The routing procedure is discussed by the ${{\rm{\Pr }}}_{{{\mathscr{T}}}_{i}}(n,z)$ probability function of (42). In (42), the ${C}_{1}$ and ${C}_{2}$ weights have a crucial role and are determined as follows.

If the average value ${\mu }^{n}({{\rm{\Phi }}}_{{\mathscr{P}}}^{s,n})$ (see (35)) is low, then ${C}_{1}$ is high and ${C}_{2}$ is low. In this case an another way and a different node but not $z$ is selected at an actual node $n$. For a high ${\mu }^{n}({{\rm{\Phi }}}_{{\mathscr{P}}}^{s,n})$, ${C}_{2}$ picks up a high value and ${C}_{1}$ is low. In this case the current target node $z$ is selected at node $n$.

Thus, for a given threshold $o$ on ${\mu }^{n}({{\rm{\Phi }}}_{{\mathscr{P}}}^{s,n})$, ${\mu }^{n}({{\rm{\Phi }}}_{{\mathscr{P}}}^{s,n})\le o$, the selection rule for weights $\{{C}_{1},{C}_{2}\}$ is

$$\{{C}_{1},{C}_{2}\}=\{\begin{array}{l}{C}_{1}\to 1,{C}_{2}\to 0,if{\mu }^{n}({{\rm{\Phi }}}_{{\mathscr{P}}}^{s,n})\le o,\\ {C}_{1}\to 0,{C}_{2}\to 1,{\rm{otherwise}}.\end{array}$$

(55)

As a corollary of (55), a high value of C ₁ and a low value of C ₂ increases the network area to be explored by a thread, while for a low value of C ₁ and a high value of C ₂, the number of explored nodes is smaller.

The values of ${{\rm{\Pr }}}_{{{\mathscr{T}}}_{i}}(n,z)$ (42) as a function of weight coefficients C ₁ and C ₂ for a given path ${{\mathscr{P}}}_{i}$, current node $n$, and next node $z$ at a particular thread ${{\mathscr{T}}}_{i}$ and network setting are depicted in Fig. 6. In Fig. 6(a), the inverse link entanglement gradient is ${\theta }_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{z}=0.5$, while in Fig. 6(b), it has the value of ${\theta }_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{z}=0.2$.

Figure 6

(a) The ${{\rm{\Pr }}}_{{{\mathscr{T}}}_{i}}(n,z)$ probability of selecting a next node $z$ from a current node $n$ for a given path ${{\mathscr{P}}}_{i}$, $0\le {C}_{1}\le 1$ and $0\le {C}_{2}\le 1$, at a setting of ${\theta }_{{E}_{{{\rm{L}}}_{l}}(n,z)}^{z}=0.5$, $\psi (n,z)=5$, $k=5$, and at (b) ${{\boldsymbol{\theta }}}_{{{\boldsymbol{E}}}_{{{\bf{L}}}_{{\boldsymbol{l}}}}({\boldsymbol{n}},{\boldsymbol{z}})}^{{\boldsymbol{z}}}=0.2$, $\psi (n,z)=5$, $k=5$.

Achievable Entanglement Fidelity in the Protocol

Assuming an ideal recovery operation ${\mathcal R}$ with an optimal quantum error correction ${\mathscr{C}}$ ^{12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,41,42,43,44,45,48} in the proposed routing mechanism, the $F$ entanglement fidelity is evaluated as

$$F=\langle \tilde{{\rm{\Psi }}}| {\mathcal R} ({\rho }_{f})|\tilde{{\rm{\Psi }}}\rangle ,$$

(56)

where $\tilde{{\rm{\Psi }}}$ is a shared Bell pair between the final stations, while ${\rho }_{f}$ is the input density matrix of ${\mathcal R}$.

For an ${{\rm{L}}}_{l}$-level entangled link ${E}_{{{\rm{L}}}_{l}}(A,B)$ with hop-distance $d{(A,B)}_{{{\rm{L}}}_{l}}={2}^{l-1}$ between final stations $A$ and $B$, and per-node error probability ${P}_{err}$ (that includes the effective logical error probability $Q$ and other residual errors ${\varepsilon }_{res}$ in the nodes) in the $d{(A,B)}_{{{\rm{L}}}_{l}}+1$ total stations, after some calculations the entanglement fidelity (56) can be rewritten as⁴¹

$$\begin{array}{l}F={(1-{P}_{err})}^{2(d{(A,B)}_{{{\rm{L}}}_{l}}+1)-2}\\ ={(1-(Q+{\varepsilon }_{res}))}^{2d{(A,B)}_{{{\rm{L}}}_{l}}}.\end{array}$$

(57)

The performance of the routing is approachable by the correlation measurement ${\mathcal M} (A,B)$ between the final stations $A$ and $B$, which quantity practically yields the corresponding fidelity information as⁴¹

$$\begin{array}{l} {\mathcal M} (A,B)\approx \sqrt{F}\\ \approx {(1-{P}_{err})}^{d{(A,B)}_{{{\rm{L}}}_{l}}+1}\\ ={(1-(Q+{\varepsilon }_{res}))}^{{2}^{l-1}+1}.\end{array}$$

(58)

The results for ${\mathcal M} (A,B)$ in function of per-node error probability ${P}_{err}$, and level ${{\rm{L}}}_{l}$ of the entangled link ${E}_{{{\rm{L}}}_{l}}(A,B)$ between the final stations $A$ and $B$ are depicted in Fig. 7.

Figure 7

The $F$ entanglement fidelity as obtainable from the correlation measurement ${\mathcal M} (A,B)\approx \sqrt{F}$ between final stations $A$ and $B$, at per-node error probability ${P}_{err}=[0,0.025]$, hop distance $d{(A,B)}_{{{\rm{L}}}_{l}}={2}^{l-1}$, and entanglement level ${{\rm{L}}}_{l}=[1,10]$.

In the protocol, the $F$ entanglement fidelity of the final Bell pair $\tilde{{\rm{\Psi }}}$ between $A$ and $B$ (see (57)) achieves a theoretical maximum at $d{(A,B)}_{{{\rm{L}}}_{l}}-1$ intermediate quantum repeaters, and at operators ${\mathcal R}$ and ${\mathscr{C}}$ ^33,47 Using ${P}_{err}$, the ${P}_{succ}^{tot}( {\mathcal R} )$ total success probability of the recovery operation ${\mathcal R}$ for the intermediate nodes is evaluated as

$${P}_{succ}^{tot}( {\mathcal R} )={(1-{P}_{err})}^{2((d{(A,B)}_{{{\rm{L}}}_{l}}+1)-2)}={(1-(Q+{\varepsilon }_{res}))}^{2(d{(A,B)}_{{{\rm{L}}}_{l}}-1)},$$

(59)

while the internal error-correction operation ${\mathscr{C}}$ has a ${P}_{succ}^{\tilde{{\rm{\Psi }}}}({\mathscr{C}})$ success probability with respect to the final state $\tilde{{\rm{\Psi }}}$ as

$${P}_{succ}^{\tilde{{\rm{\Psi }}}}({\mathscr{C}})={(1-(Q+{\varepsilon }_{res}))}^{2}.$$

(60)

The success probabilities in (59) and (60) yield an estimation^33,47 for the entanglement fidelity $F$ of $\tilde{{\rm{\Psi }}}$ as

$$F\approx {P}_{succ}^{tot}( {\mathcal R} ){P}_{succ}^{\tilde{{\rm{\Psi }}}}({\mathscr{C}}),$$

(61)

which therefore practically yields (57).

Security of the Protocol

Based on the $F$ entanglement fidelity (57) of $\tilde{{\rm{\Psi }}}$, the security of the protocol can be characterized^33,47 as follows. At a particular final key $K$ (a shared bitstring between $A$ and $B$), the proposed protocol guarantees that the maximum information leaked to an eavesdropper $E$ (Eve) is upper bounded³³ as

$$I(E:K)\le {2}^{-c}+{2}^{{\mathscr{O}}(-2s)},$$

(62)

where $I(E:K)$ is the mutual information of Eve, and

$$c=s-{\mathrm{log}}_{2}(2+s+\frac{1}{\mathrm{ln}\,2}),$$

(63)

while $s$ is evaluated as

$$s=-{\mathrm{log}}_{2}(1-F),$$

(64)

at a particular entanglement fidelity $F$ (57) of $\tilde{{\rm{\Psi }}}$.

The protocol therefore also provides a practical framework to realize quantum key distribution over long distances.

Conclusions

In this work, we defined the entanglement-gradient routing method for quantum repeater networks. The routing scheme is based on the fundamentals of swarm intelligence in order to find the optimal shortest path in entangled quantum networks. We defined the terms of entanglement utility and link and path entanglement gradient, and proposed the routing metrics. The routing metrics are derived from the characteristics of entangled links, entanglement throughput capabilities, and the distribution of the entangled states. The method allows for moderate complexity routing in quantum repeater networks by fusing the relevant characteristics of entanglement distribution and swarm intelligence theory. The scheme can be directly applied in quantum networking, future quantum Internet, and experimental long-distance quantum communications. As a future work, we are planning to prepare a transmission analysis and performance comparisons with other schemes.