Progress is being made on building the quantum internet [1][2][3][4], with networks consisting of a handful of nodes currently being developed [5]. The promise of a quantum internet is the ability to perform quantum information processing tasks, such as quantum teleportation [6,7], quantum key distribution [8][9][10][11], quantum clock synchronization [12][13][14], distributed quantum computation [15], and distributed quantum metrology and sensing [16][17][18][19][20][21], on a global scale.
One of the most common methods for creating longdistance entangled links is to transmit photonic qubits through either free space or optical fibers [22,23]. However, each of these media is lossy, and the probability of successfully transmitting a photon decays exponentially with the distance between the end points [24,25]. Other sources of loss, such as source and detector inefficiencies, as well as read/write inefficiencies of quantum memories, ultimately make the task of establishing links in a quantum network with photonic qubits inherently probabilistic.
Quantum repeaters [22,26,27] can be used to increase the success probability, as well as the fidelity, of long-range entanglement in a quantum network. Several schemes for long-range bipartite and multipartite entanglement distribution in quantum repeater networks have been considered [28][29][30][31][32][33][34][35][36][37][38][39]. All of these schemes involve first generating elementary bipartite or multipartite entanglement links and then performing measurements to join the elementary links [40]. In general, both the elementary link generation and the joining measurements are probabilistic. How should we evaluate the performance of these entanglement distribution schemes, and what limits are imposed on them by the probabilistic nature of the operations involved?
In this work, we propose two figures of merit that can be used to evaluate the performance of elementary link generation in quantum networks: the average connection time and the average largest entanglement cluster size. The average connection time is an important quantity because, as we show, it can be used to calculate rate of entanglement distribution in a network as a function of the elementary link generation probability. The average largest entanglement cluster size is important because it gives an indication of the range over which entanglement distribution can be achieved in practice.
Much work has been devoted to quantifying the performance of quantum repeater networks by using as figures of merit fundamental limits on the rate at which either bipartite or multipartite entanglement and/or a secret key can be generated between points in the network [41][42][43][44][45][46][47][48][49][50]. In these works, however, perfect quantum repeaters are assumed, and other practical limitations are not explicitly taken into account.
Both of our figures of merit explicitly take into account the probabilistic generation of elementary links as well as the limited coherence time of quantum memories. We show that they can be used to evaluate the performance of the devices used FIG. 1. The network architectures that we consider in this work are based on graphs of arbitrary topology. (a) The vertices of the graph correspond to the nodes in the network, and the edges correspond to the elementary links. At the center of each elementary link is a source of entangled photonic qubits (indicated in blue) that fires entangled photons toward the nodes at the ends of the link, where they are held in quantum memories (indicated in red). (b) An example of the general procedure to create bipartite entanglement between two nonadjacent nodes that are connected to a common node. in an actual quantum network implementation and that they can be used to set device requirements for achieving particular values of the quantities. We do this by obtaining bounds on the two figures of merit for a particular class of quantum repeater protocols based on a repeat-until-success strategy executed on a graph-based network topology. These bounds represent limitations on quantum networks based solely on elementary link generation probabilities, and they are independent of any particular physical platform. They can thus serve as a guide for building a real quantum internet.
We start in Sec. II by outlining the network architecture and quantum repeater protocol that we consider in this work, which generalize the original quantum repeater proposal in Refs. [26,27]. Then, in Sec. III, we consider the average connection time as a figure of merit and evaluate it for our quantum repeater protocol. We show how the average connection time can be used to compute entanglement distribution rates, and we compare these rates with known repeaterless rate limits. In Sec. IV, we consider the average largest entanglement cluster size as a figure of merit for the long-range entanglement distribution capability of a quantum network. We provide concluding remarks in Sec. V.
The network architecture that we consider is illustrated in Fig. 1(a). The network corresponds to an undirected graph G = (V, E ), where V = {v i : 1 i N} is the set of vertices and
The vertices of the graph correspond to the nodes in the network. The edges of the graph correspond to the elementary links in the network. At the center of each elementary link is a source of bipartite entanglement, which is used to generate bipartite entanglement between the nodes at the ends of the edges. These sources produce entangled photonic qubits in a maximally entangled Bell state. The qubits are encoded into single photons in one of two distinct modes, which are usually horizontal and vertical polarization modes.
The transmission of photons from the source to the neighboring nodes typically occurs through either free space or optical fiber. In each case, loss is the dominant source of noise, which makes the transmission of photons to the nodes probabilistic. In particular, the probability that a photon arrives at a node decreases exponentially with the distance that the photon travels. If we let η i, j be the probability that both photons of a pair fired along the edge (v i , v j ) reach the nodes v i and v j , then
where i, j is the length of the edge and α is a value that characterizes the medium. Typically, α = 1 22 km [51]. In the context of dual-rail photonic qubits that we consider here, loss corresponds to an erasure channel between the links (see, e.g., Refs. [35,52]), so that with probability η i, j both photons arrive at their destination with fidelity unchanged, and with probability 1 -η i, j at least one of the photons is lost, meaning that the state in the corresponding mode is the vacuum state.
Each node v i in the network contains d i quantum memories, where d i is the degree of the node v i . (The degree of a node is defined to be the number of edges connected to that node.) Several different platforms have been considered for quantum memories in quantum repeater networks, such as trapped ions [53], Rydberg atoms [54,55], atom-cavity systems [56,57], NV centers in diamond [58][59][60][61][62][63], individual rare-earth ions in crystals [64], and superconducting processors [65]. In order to store the arriving photonic qubit state in the quantum memory, each node has locally an optical Bell measurement device. First, a memory-photon entangled state is generated, then a Bell measurement is performed on the photon from the memory-photon pair and the incoming photon from the source. This strategy allows for direct knowledge about the arrival of the photon, which is then communicated to the neighboring node (see, e.g., Ref. [61]). At the same time, conditioned on the success of the Bell measurement, the state of the photonic qubit is transferred to the memory qubit. Linear-optical Bell measurements are limited to a success probability of 50% [66][67][68], although higher success probabilities are in principle possible using nonlinear elements or by increasing the number of photons [56,[69][70][71][72].
In addition to loss due to the transmission of photons through free space or optical fibers, there are other sources of loss, such as source inefficiency, detector inefficiency, and quantum memory read/write inefficiency. We can combine all of these loss factors into a single probability p i, j for establishing a link between neighboring nodes v i and v j .
To generate elementary links in a network, we use a repeat-until-success strategy in which sources of photonic qubits (blue nodes in Fig. 1) continuously fire entangled states toward repeater stations (gray nodes in Fig. 1) at a rate of R trials per second. Once an elementary link has been established, the corresponding qubits are held in the quantum memories at the repeater nodes for up to time t while the neighboring elementary links are being established. After time t , the effects of decoherence on the stored qubits are considered to be too great and the link is discarded and must be reestablished. The cutoff t can take into account not only the coherence times of the quantum memories, but also other more stringent practical requirements. For example, for protocols making use of entanglement purification, the cutoff time should be such that the end-toend shared entangled states have sufficiently high fidelity in order to perform the desired entanglement purification protocol.
As an example of this repeat-until-success protocol, consider the situation depicted in Fig. 1(b), in which two end nodes are separated via elementary links by a common central node. Generating bipartite entanglement between these end nodes is the most basic element of any long-distance entanglement distribution scheme. Our protocol for establishing entanglement between the end nodes is the following repeat-until-success procedure, which is based on the schemes presented in Refs. [61,63,[73][74][75][76].
(1) Elementary link generation attempts are continuously made at a rate of R trials per second. In each trial, a pair of entangled photons is fired from a source station towards the nodes at the ends of the link. Neighboring nodes at the ends of the elementary link communicate classically to confirm the arrival of both photons. FIG. 2. Instead of bipartite entanglement, as in Fig. 1(a), the elementary links in a quantum network can consist of multipartite entanglement; for example, we can have elementary links of tripartite (left) or four-partite (right) entanglement.
(2) Once an elementary link has been established, the corresponding qubits are stored in quantum memory for up to time t . If this time is reached and the other elementary link has not been established, then the link must be reestablished.
(3) Once both elementary links have been established, an entanglement swapping measurement is performed on the memory qubits in the central node in order to establish entanglement between the end nodes.
The protocol described above for generating bipartite entanglement between two nodes separated by one central node generalizes straightforwardly both to bipartite entanglement generation through a longer chain of elementary links and to multipartite entanglement generation over a collection of adjacent elementary links. In these cases, an elementary link must be reestablished after the cutoff time, which means that all of the relevant elementary links must be established before the cutoff of any one of the elementary links is reached. Once all of the relevant elementary links have been established, measurements can be made on the intermediate nodes in order to generate bipartite or multipartite entanglement between the end nodes. Bell measurements are typically used to obtain long-range bipartite entanglement, while multiqubit measurements can be made in order to generate multipartite entanglement; see, e.g., Refs. [28][29][30][31][32][33][34][35][36][37][38][39]. In this way, the protocol that we consider is an extension of the original quantum repeater protocol in Refs. [26,27] from a linear chain to an arbitrary topology.
Another way to generalize the original quantum repeater protocol is to generate elementary links of multipartite entanglement instead of bipartite entanglement. For example, in Fig. 2, the elementary links consist of tripartite entanglement [31,77] and four-partite entanglement. One can then consider multipartite entanglement swapping (see, e.g., [31]) to extend the range of multipartite entanglement.
The bipartite and multipartite generalizations of the original quantum repeater protocol of Refs. [26,27] that we consider here are similar to the bipartite and multipartite quantum repeater protocols in Refs. [42,44,45,[47][48][49]. For the figures of merit considered in those works, however, no physical limitations are placed on the quantum repeaters, while we consider the practically relevant scenario of probabilistic elementary link generation and quantum repeaters with limited coherence times.
In our network architecture, we allow for the possibility of having multiple parallel links along the edges connecting two neighboring nodes. This can be achieved using multiple optical fibers between the two nodes, or by employing spectral multiplexing; see, e.g., Refs. [60,78,79]. If p i, j is the probability of establishing a connection along the edge (v i , v j ) for one of the parallel links, and there are n > 1 parallel links, then the probability of establishing a connection increases from p i, j to 1 -(1p i, j ) n . In other words, with probability 1 -(1p i, j ) n , at least one of the parallel links successfully connects the two neighboring nodes.
We remark that with nonideal quantum memories, the entanglement distribution protocol described above will in general generate a mixed entangled state between the end nodes with nonunit fidelity to the ideal state. In order to increase the fidelity, one can perform entanglement purification [80] at the intermediate nodes before performing the measurements that increase the range of entanglement (see, e.g., Refs. [44,45]). Since entanglement purification protocols are generally probabilistic, the success probability of entanglement purification can be incorporated into the probability p i, j of successfully obtaining an entangled link along the edge (v i , v j ). Our results thus apply even in the case that entanglement purification between neighboring nodes is incorporated into the entanglement distribution protocol.
A slight modification of the entanglement generation protocol given above is based on the scheme presented in Ref. [81]. In this alternate scheme, we place a linear-optical Bell measurement station at the center of each elementary link instead of a source producing photonic-qubit Bell states. An entangled state between a quantum memory and a photon is generated locally at two neighboring nodes. The photon from each node is then transmitted toward the center of the elementary link connecting the two nodes. A Bell measurement is then performed on the two arriving photons. Success of this Bell measurement heralds the generation of entanglement between the two memory qubits at the neighboring nodes. All of the results presented here apply equally to this method. See also [61,76] for an analysis of this alternative entanglement generation protocol.
To summarize, we consider in this work a quantum repeater protocol in which the elementary link generation is inherently probabilistic. All that matters for our results is the probability p i, j for successfully establishing an elementary link along the edge (v i , v j ) and the cutoff time t of the quantum memories. We do not focus on any particular implementation and the corresponding parameters that may lead to specific values for the probabilities p i, j . This allows our results to be completely general and applicable to any practical quantum network implementation.
How long does it take for all of the required elementary links to be established in a quantum network? Given a cutoff time of t for the quantum memories, the repetition rate R of the trials in the entanglement distribution protocol, as described in the previous section, leads to a cutoff number of trials n := Rt , beyond which an elementary link must be reestablished. Then, if there are M elementary links to be established, we let N (M, n ) denote the number of trials needed to establish all M elementary links, so that the required connection time is T (M, n ) := N (M, n )/R. Note that N (M, n ) depends only on the number M of elementary links and not on the topology of the network, since all elementary link attempts are independent of each other. We are interested in the average connection time E[T (M, n )], which we determine by focusing on the average number E[N (M, n )] of trials.
In Ref.
[82, Eq. ( 5)], it was shown that if all of the elementary links in the network have the same success probability p, then
For higher values of M in the case n = ∞, we have that
In the case n < ∞, the number of trials needed to establish all M elementary links can never be less than the number of trials it takes for any one of the elementary links to be established, meaning that N (M, n ) N i for all 1 i M. In particular, then,
for all n ∞. Furthermore, the most number of trials are required when there are no quantum memories, which is equivalent to setting n = 0. Therefore, E[N (M, n )] E[N (M, 0)] for all n 0. In the case n = 0, all of the elementary links have to be established in the same trial, and the probability that this occurs is p M . This means that Pr [N (M, 0) = n] = p M (1p M ) n-1 . Therefore, E[N (M, 0)] = 1/p M . We thus obtain the following result.
Theorem 1. Consider a quantum network in which the success probability of each of the M 1 elementary links is p. Then, for all 0 n ∞,
See Appendix A for the proof. Theorem 1 gives us a lower bound on the average connection time for any network, and it depends only on the number M of elementary links being established in the network, as well as the elementary link success probability p.
See Fig. 3(a) for plots of E[N (M, 0)] and E[N (M, ∞)] for various values of M. As an example, suppose that we would like to construct a network with M = 10 elementary links, and we would like the network to be fully connected within 10 trials on average. Then, in the best-case scenario of n = ∞, we see from Fig. 3(a) that we would require a link success probability p of at least 0.25. Also, if we assume that p = e -α (with α = 1 22 km ), so that the photon transmission medium is the only source of loss, if we assume that all elementary links have the same length , and we let R = c be the repetition rate [83], where c is the speed of light, then we find that even for an internodal distance of = 40 km, the average global connection time for a network with M = 100 elementary links and no quantum memories is approximately 10 74 seconds, which is longer than the age of the universe. On the other hand, with quantum memories and a cutoff n = ∞, the average connection time is less than 10 -2 seconds. Note that 10 -2 seconds is the optimal connection time, meaning that any network with M = 100 elementary links and an internodal distance of = 40 km making use of the protocol described in Sec. II requires at least 10 -2 seconds to become fully connected. We also find that for a network with M = 10 elementary links and an internodal distance of = 30 km, it is not possible to obtain a fully connected network in less than 10 -3 seconds.
In order to obtain tighter estimates for E[N (M, n )] for 0 < n < ∞, we resort to estimating E[N (M, n )] via Monte Carlo simulations. Assuming that all elementary links have the same length , letting R = c be the repetition rate as before, and assuming p = e -α , α = 1 22 km , we obtain the plots in Fig. 3 10. For example, suppose that we have a network with M = 10 elementary links and we would like to obtain a fully connected network within one second. Then, with quantum memories such that n = 2, we see from Fig. 3(b) that the maximum possible internodal distance is ≈ 37 km, and this maximum distance corresponds to a cutoff time of t = 2 × 37 km/c = 246 μs. More generally, if we impose a particular cutoff time t , then the maximum internodal distance is = ct /2, which corresponds to n = 2, and in this case the average connection time is also maximal. By taking higher values of n , the average connection time can be decreased at the cost of decreasing the maximum internodal distance.
The lower bound in Theorem 1 imposes a requirement on the cutoff n needed in order to obtain the required elementary links in the fewest possible number of trials on average. In Table I, we show the minimum cutoff, denoted by n min , that is required in order to obtain the required elementary links in a number of trials that is within 1% of the optimal number E[N (M, ∞)] of trials. For values of the link success probability p less than 0.1, we require a cutoff on the order of hundreds of trials. If we assume that p = e -α for all elementary links, and that all elementary links have the same length , then p = 0.01 implies ≈ 100 km, so that for M = 10 elementary links the required cutoff time is approximately t = 655 /c = 0.2 seconds.
A well-established figure of merit for any quantum repeater protocol is the repeaterless (i.e., point-to-point) quantum/secret-key capacity [84] of the quantum communication channel over which the protocol takes place. The quantity E[N (M, n )] can be used to evaluate the quantum repeater protocol that we consider here against this figure of merit. Let us consider a linear repeater chain with a total length L divided into M elementary links, such that there are M -1 equally spaced repeater stations between the end points. Photonic qubits are made using the dual-rail encoding. Then, the source stations at the center of each elementary link fire maximally entangled qubit pairs (ebits) towards the repeater stations through a bosonic pure-loss channel [85] with transmissivity e -α 2 , where α = 1 22 km and = L M is the length of each elementary link. We assume for simplicity that the entanglement swapping Bell measurements at the repeater stations are perfect and deterministic, and that there are no other imperfections. Note that each trial of the elementary link generation requires two uses of the channel. Furthermore, due to the dual-rail encoding, each trial has success probability p = e -α [86]. Therefore, because E[N (M, n )] represents the number of trials needed to obtain one end-to-end ebit, the quantity 1/{2E[N (M, n )]} is the average number of endto-end ebits per channel use, i.e., the rate. By Theorem 1, 1/{2E[N (M, ∞)]} is the highest possible rate for the protocol FIG. 4. Optimal rates 1/{2E[N (M, ∞)]} for the quantum repeater protocols considered in this work, as executed on a linear chain with M elementary links, compared to the repeaterless capacity (RL Cap.)log 2 (1 -η) of the bosonic pure-loss channel [87,88]. The end-to-end distance of the chain is L, such that η = e -αL , α = that we consider. We compare this rate to the repeaterless capacity of the bosonic pure-loss channel over the entire length of the chain, which islog 2 (1e -αL ) [87,88]. The results are shown in Fig. 4, using which we obtain repeater chain lengths L min beyond which our repeater protocol can overcome the repeaterless capacity; see Table II.
We can extend Theorem 1 to the case that n P parallel paths exist in the network for the required elementary links. The parallel paths can arise either due to multiple parallel transmission channels or through edge-disjoint paths when considering the connection of two distinct points in the network. We let N (M, n ; n P ) denote the number of trials needed to obtain all M elementary links in a network with memory cutoff n and n P parallel paths for the elementary links.
Without quantum memories, i.e., in the case n = 0, N (M, 0; n P ) is simply a geometric random variable in which the corresponding success probability p succ is given by the probability that at least one of the n P paths has all of its elementary links established. For simplicity, as before, we suppose that each elementary link has a success probability of p. Then, p succ = 1 -(1p M ) n P . This holds due to the fact that the ith path is connected with probability p M . Then, with probability 1p M , at least one of the elementary links in the ith path fails. Then, since all paths are independent of each other, the probability that they all fail is n P i=1 (1p M ) = TABLE II. Minimum total repeater chain lengths L min , as obtained from the results in Fig. 4, beyond which the quantum repeater protocol considered in this work can overcome the repeaterless capacity of the bosonic pure-loss channel. M is the number of elementary links in the chain. (1p M ) n P . We thus have that
Let us now determine N (M, n ; n P ) in the case in which n = ∞. To start, let N i j be the number of trials needed to establish the jth elementary link in the ith path, where 1 j M. Furthermore, let N i (M, ∞) be the number of trials needed to establish the ith path between A and B. Then, the number of trials needed to establish one of the n P paths between A and B depends on which of the paths gets established first. We thus obtain
In Appendix B, we show that
and that the average number of trials needed to connect the M elementary links is
Let us now consider the example of a network with the topology of a two-dimensional pyramid, as shown in Fig. 5(a). We assume that all of the elementary links have the same success probability p. We let n L denote the number of layers in the network.
How many trials does it take, on average, to obtain a connected path from the node at the top of the network to one of the nodes at the bottom? We let p = 0.1, and we let A be at the center of the bottom layer of the pyramid and B be at the very top of the pyramid. The results we obtain are in Fig. 5(b) for n L = 3, 4, 5, 6, 7, 8 and n = 2. We see that as the size of the network grows, so too does the required number of trials.
Next, we consider the distribution of trials for the nodes on the bottom layer. We again let p = 0.1 and n = 2. The results we obtain are shown in Fig. 5(c). The number of trials is symmetric around on the center of the bottom layer for all values of n L . In particular, placing A at the center of the bottom layer results in the fewest number of trials, while placing A at either one of the two edges of the bottom layer results in the highest number of trials.
Finally, we consider the effect of having longer cutoffs n . In Fig. 5(d), we plot the average number of trials needed when A is at the center of the bottom layer and B is at the top, for n L = 3, 5, 7 and p = 0.1. As expected, as n increases, the number of trials decreases. Interestingly, for all three network sizes corresponding to n L = 3, 5, 7, the average number of trials appears to approach a value close to eight, suggesting that eight is the fewest number of trials in which a connection between A and B can be established, at least for pyramid networks with an odd number of layers.
In order to understand the long-range connectivity in a network, it is important to consider the size of the largest cluster of established elementary links that can be achieved in the network within a certain period of time. By a cluster, we mean a collection of nodes in the network, all of which are connected to each other via established elementary links. We define the size of a cluster by the number of established elementary links contained in it. Since every established elementary link corresponds to a shared entangled state between neighboring nodes, we refer to a cluster as an entanglement cluster.
Let S max n (G, n ) denote the size of the largest entanglement cluster after n 1 trials in a network described by the graph G = (V, E ) with memory cutoff n . We are interested in the quantity E[S max n (G, n )], which is the average largest entanglement cluster size. Note that the size of the largest entanglement cluster in a network after a certain number of trials can never exceed the number of established elementary links in the entire network after the same number of trials. If we let L n (M, n ) denote the number of established elementary links after n trials in the network of M = |E | total elementary links, we thus have the upper bound S max n (G, n ) L n (M, n ). Now, how many elementary links can be established in the network in a fixed amount of time when we start with a network with all elementary links unestablished? As before, we work more generally with the number of trials instead of with the time, and we assume that all elementary links have the same success probability p. We are interested in the quantity E[L n (M, n )]. Observe that L n (M, n ) does not depend explicitly on the graph G, similarly to the quantity N (M, n ), since all elementary link attempts are independent of each other. We provide more specific details about the quantity L n (M, n ) in Appendix C.
With n = 0, all established elementary links are reset after one trial. Then, since all elementary link attempts are independent of each other, we have that Pr
In the case n > n + 1, we estimate 1 M E[L n (M, n )] via Monte Carlo simulations. See Fig. 6 for plots of 1 M E[L n (M, n )] with M = 40 for a variety of finite nonzero cutoffs n . Although we take M = 40 elementary links in the network to obtain the plots, after comparing the results with various other values of M, we find that the fraction 1 M E[L n (M, n )] does not depend on M. Furthermore, we find in some cases that having a higher value of n is unhelpful for obtaining a higher fraction of established elementary links for certain values of p. For example, in the case of n = 30 trials, we find that for p roughly between 0.30 and 0.70, the average number of established elementary links with n = 6 is higher than the average number of established elementary links with n = 8. This behavior is due to the fact that with a finite cutoff, there are times at which several established elementary links are simultaneously removed as a consequence of reaching the cutoff number of trials, especially when the elementary link success probability p is high. Interestingly, therefore, unlike the quantity N (M, n ), the quantity L n (M, n ) is not monotonic in n for all values of n and p.
In general, the number of established elementary links with a finite cutoff cannot exceed the number of established elementary links with an infinite cutoff. Therefore,
Using this, we obtain the following result, the proof of which can be found in Appendix C.
Theorem 2. Consider a network described by a graph G with M edges, such that each elementary link has a success probability p. Then, on average in order to achieve the desired fraction f of established elementary links.
Let us now return to the average largest entanglement cluster size E[S max n (G, n )] and examine it in more detail. We consider the regular square and triangular lattices, and we assume that all elementary links have the same success probability p. We also consider n = 10 trials. Then, we find that as the size of the network increases, a critical value of p emerges, call it p crit , at which the average largest entanglement cluster size undergoes a sharp transition. Below p crit , the average largest entanglement cluster size is effectively zero, while beyond p crit the average largest entanglement cluster size increases to one; see Fig. 7. We also observe that as n increases p crit decreases; see Table III.
The quantity p crit can be regarded as the minimum elementary link success probability that must be attained in any practical implementation of a large-scale quantum network. In other words, all of the elements that contribute to the elementary link success probability, such as the source inefficiency, the transmission loss, the quantum memory read/write inefficiencies, and the success probability of entanglement purification, have to combine to be greater than p crit in order to have a good large-scale quantum network. In this context, the values in Fig. 7 imply that the triangular lattice topology is more suitable for large-scale quantum networks since it has a lower critical elementary link success probability for every cutoff value considered. FIG. 7. Estimated average largest entanglement cluster sizes with n = 10 trials and various cutoffs for the 500 × 500 square (left) and triangular (right) lattices.
Generation of elementary links is a crucial first step to obtaining long-distance entanglement in a quantum network. In this work, we considered the limitations imposed on quantum networks due to the inherently probabilistic nature of elementary link generation. We proposed the average connection time and the average largest entanglement cluster size as relevant quantities to consider when evaluating the performance of a quantum network. We provided bounds on these two quantities for a particular class of quantum repeater protocols. These bounds led to requirements on the coherence times of quantum memories (Table I), requirements on the lengths of repeater chains in order to achieve rates that surpass the repeaterless capacity (Table II), and requirements on overall device efficiency for large-scale networks (Table III).
One direction for future work is to investigate the trade-off between the two quantities considered here and the fidelity of the shared entangled state at the end of the protocol. By considering more general operations at the intermediate nodes, one could then aim to determine quantum repeater protocols that are optimal for these two quantities, similarly to the investigation in Ref. [89] on the trade-off between fidelity and success probability in entanglement purification protocols.
Another direction for future work is to explore how the results obtained here can be generalized to "one way" quantum repeater protocols, in which the entanglement to be shared and/or the quantum information to be transmitted is generated entirely locally at a particular node and sent through elementary links to the desired end nodes [90][91][92][93][94][95][96][97]. Such protocols do not require the two-way classical communication that is required in the protocols that we consider; however, these protocols require the use of quantum error-correction codes, which typically results in a significant resource overhead in terms of the number of required physical qubits. and that the average number of trials needed to connect the M elementary links is
In order to prove Eqs. ( 6) and ( 7), the main task is to characterize the set S n P ,n := {(n 1 , n 2 , . . . , n n P ) : min{n 1 , n 2 , . . . , n n P } = n}. It holds that S n P ,n = n P j=1 S j n P ,n , where
Now, let us recall from Eq. (A10) that for n = ∞ we have that
for all 1 n P . Since for all 1 i n P , which follows from Eq. (B8). This completes the proof.
We now prove that Since by Eq. (C7) we have that L n (M, 0) = L (1) (M, 0), and we have from Eq. (C3) that L (1) (M, 0) is simply a binomial random variable, we immediately obtain E[L n (M, 0)] = E[L (1) (M, 0)] = M p, so that Eq. (C8) holds.
To prove Eq. (C9), and more generally Eq. (C10), we first calculate E[L ( j) (M, n )] with 1 j n + 1. Using Eq. (C1), we have
Pr[L (1) (M, n ) = x 1 , L (2) (M, n ) = x 2 , . . . , L ( j-1) (M, n ) = x j-1 , L ( j) (M, n ) = x] (C11)
Pr[L (1) (M, n ) = x 1 ] Pr[L (2)
Therefore,
x Pr[L ( j) (M, n ) = x] (C13)
x j-1 =0
x Pr[L (1) (M, n ) = x 1 ] Pr[L (2) (M, n ) = x 2 | L (1) (M, n
Then,
Similarly, summing over x j-2 gives the result (Mx 1x 2 -• • •x j-3 )(1p). Continuing this for all the summation variables, we ultimately obtain
Using this, we find that for all n n + 1,
as required.