We consider the problem of optimizing the achievable EPR-pair distribution rate between multiple source-destination pairs in a quantum Internet, where the repeaters may perform a probabilistic Bell-state measurement and we may impose a minimum end-to-end fidelity as a requirement. We construct an efficient linear programming (LP) formulation that computes the maximum total achievable entanglement distribution rate, satisfying the end-to-end fidelity constraint in polynomial time (in the number of nodes in the network). Our LP formulation gives the optimal rate for a class of entanglement generation protocols where the repeaters have very short-lived quantum memories. We also propose an efficient algorithm that takes the output of the LP solver as an input and runs in polynomial time (in the number of nodes) to produce the set of paths to be used to achieve the entanglement distribution rate. Moreover, we point out a practical entanglement generation protocol that can achieve those rates.
We consider the problem of optimizing the achievable EPR-pair distribution rate between multiple source-destination pairs in a quantum Internet, where the repeaters may perform a probabilistic Bell-state measurement and we may impose a minimum end-to-end fidelity as a requirement. We construct an efficient linear programming (LP) formulation that computes the maximum total achievable entanglement distribution rate, satisfying the end-to-end fidelity constraint in polynomial time (in the number of nodes in the network). Our LP formulation gives the optimal rate for a class of entanglement generation protocols where the repeaters have very short-lived quantum memories. We also propose an efficient algorithm that takes the output of the LP solver as an input and runs in polynomial time (in the number of nodes) to produce the set of paths to be used to achieve the entanglement distribution rate. Moreover, we point out a practical entanglement generation protocol that can achieve those rates.
Quantum networks are designed to transmit quantum bits (qubits) among quantum devices to enable new network resources for the applications. Entanglement distribution and entanglement swapping are fundamental procedures that are required in several network operations. However, they are probabilistic operations, which can lead to severe network performance degradation. This article investigates the engineering problem of resource allocation in quantum networks, considering factors like entanglement distribution probability, quantum memory characteristics, and fidelity. We model this as an optimization model to obtain an optimal solution. In particular, we formulate an integer linear programming (ILP) and develop a heuristic algorithm, aiming to minimize the number of required entangled qubit pairs (Bell pairs or EPR pairs) in any adjacent pair in the quantum network. Extensive simulations are performed to compare the performance of proposed ILP and heuristic. In all the cases, the heuristic produces a comparable solution to the optimal one. Simulation results ensure that the value of maximum utilized Bell pairs in a quantum network highly depends on the value of the probability of entangled pairs established, considering the time in the quantum memory besides the number of incoming requests.
Abstract Remote quantum entanglement can enable numerous applications including distributed quantum computation, secure communication, and precision sensing. We consider how a quantum network—nodes equipped with limited quantum processing capabilities connected via lossy optical links—can distribute high-rate entanglement simultaneously between multiple pairs of users. We develop protocols for such quantum “repeater” nodes, which enable a pair of users to achieve large gains in entanglement rates over using a linear chain of quantum repeaters, by exploiting the diversity of multiple paths in the network. Additionally, we develop repeater protocols that enable multiple user pairs to generate entanglement simultaneously at rates that can far exceed what is possible with repeaters time sharing among assisting individual entanglement flows. Our results suggest that the early-stage development of quantum memories with short coherence times and implementations of probabilistic Bell-state measurements can have a much more profound impact on quantum networks than may be apparent from analyzing linear repeater chains. This framework should spur the development of a general quantum network theory, bringing together quantum memory physics, quantum information theory, quantum error correction, and computer network theory.
How to efficiently distribute entanglement over large-scale quantum networks is still an open problem that greatly depends on the technology considered. In this work, we consider quantum networks where each link is characterized by a trade-off between the entanglement generation rate and fidelity. For such networks, we look at the two following problems: the one of finding the best path to connect any two given nodes, and the problem of finding the best starting node in order to connect three nodes in the network multipartite entanglement routing. Two entanglement distribution models are considered: one where entangled qubits are distributed one at a time, and a flow model where a large number of entangled qubits are distributed simultaneously. The paper proposes of a quite general methodology that uses continuous fidelity curves (i.e., entanglement generation fidelity vs. rate) as the main routing metric. Combined with multi-objective path-finding algorithms, the fidelity curves describing each link allow finding a set of paths that maximize both the end-to-end fidelity and the entanglement generation rate. For the link models and networks considered, it is proven that the algorithm always converges to the optimal solution. It is also shown through simulation that the execution time grows polynomially with the number of network nodes (growing with a power between 1 and 1.4, depending on the network)
We consider the problem of multi-path entanglement distribution to a pair of nodes in a quantum network consisting of devices with non-deterministic entanglement swapping capabilities. Multi-path entanglement distribution enables a network to establish end-to-end entangled links across any number of available paths with pre-established elementary (link-level) entanglement. Probabilistic entanglement swapping, on the other hand, limits the amount of entanglement that is shared between the nodes; this is especially the case when, due to architectural and other practical constraints, swaps must be performed in temporal proximity to each other. Limiting our focus to the case where only bipartite entangled states are generated across the network, we cast the problem as an instance of generalized flow maximization between two quantum end nodes wishing to communicate. We propose a mixed-integer quadratically constrained program (MIQCP) to solve this flow problem for networks with arbitrary topology. We then compute the overall network capacity, defined as the maximum number of EPR states distributed to users per time unit, by solving the flow problem for all possible network states generated by probabilistic entangled link presence and absence, and subsequently by averaging over all network state capacities. The MIQCP can also be applied to networks with multiplexed links – ie, links capable of generating multiple EPR pairs per time unit – by converting the original network state's graph into an equivalent one with unit link capacities. While our approach for computing the overall network capacity has the undesirable property that the total number of states grows exponentially with link multiplexing capability, it nevertheless yields an exact solution that serves as an upper bound comparison basis for the throughput performance of more easily-implementable yet non-optimal entanglement routing algorithms. We apply our capacity computation method to several multiplexed and non-multiplexed networks, including a topology based on SURFnet – a backbone network used for research purposes in the Netherlands – for which real fiber length data is available.
A quantum network distributes quantum entanglements between remote nodes, and is key to many applications in secure communication, quantum sensing and distributed quantum computing. This paper explores the fundamental trade-off between the throughput and the quality of entanglement distribution in a multi-hop quantum repeater network. Compared to existing work which aims to heuristically maximize the entanglement distribution rate (EDR) and/or entanglement fidelity, our goal is to characterize the maximum achievable worst-case fidelity, while satisfying a bound on the maximum achievable expected EDR between an arbitrary pair of quantum nodes. This characterization will provide fundamental bounds on the achievable performance region of a quantum network, which can assist with the design of quantum network topology, protocols and applications. However, the task is highly non-trivial and is NP-hard as we shall prove. Our main contribution is a fully polynomial-time approximation scheme to approximate the achievable worst-case fidelity subject to a strict expected EDR bound, combining an optimal fidelity-agnostic EDR-maximizing formulation and a worst-case isotropic noise model. The EDR and fidelity guarantees can be implemented by a post-selection-and-storage protocol with quantum memories. By developing a discrete-time quantum network simulator, we conduct simulations to show the characterized performance region (the approximate Pareto frontier) of a network, and demonstrate that the designed protocol can achieve the performance region while existing protocols exhibit a substantial gap.
Abstract We address the problem of efficiently distributing high-fidelity entangled states across the nodes of a quantum network—a fundamental requirement for quantum communication, distributed quantum computing, and emerging quantum internet applications. We consider a repeater-based architecture that combines entanglement swapping (or fusion) with purification operations, which enhance fidelity by consuming additional entangled pairs. While prior work has explored routing and limited purification strategies, we present the first algorithms for fidelity-constrained entanglement distribution that are near-optimal and compatible with arbitrary purification models. Our approach introduces the notion of purification-augmented entanglement trees, and we develop dynamic programming (DP) algorithms to construct such trees that maximize the generation rate of entangled pairs (EPs) under fidelity constraints. We further extend our framework to a linear programming (LP)–based flow model that enables simultaneous generation of EPs across multiple source-destination pairs. For multipartite entanglement, we generalize our methods to GHZ and arbitrary graph states, supported by novel analytical models for fidelity evolution under fusion and purification. We evaluate our techniques using the NetSquid quantum network simulator and observe consistent performance improvements over prior approaches—achieving an average 50\% increase in generation rate, and up to 100-150\% in some scenarios.