Operating a quantum network incurs high capital and operational expenditures, which are expected to be compensated by the high value of enabled quantum applications. However, existing mechanisms mainly focus on maximizing the entanglement distribution rate and neglect the cost incurred on users. This paper aims to address how to utilize quantum network resources in a cost-efficient manner while sustaining high-quantity and high-quality entanglement distribution. We first consider how to establish a steady stream of entanglements between remote nodes with the minimum cost. Utilizing a recent flow-based abstraction and a novel graph representation, we design an optimal algorithm for min-cost remote entanglement distribution. Next, we consider distributing entanglements with the highest fidelity subject to a cost bound and prove its NP-hardness. To explore the cost-fidelity trade-off due to swapping and purification, we propose an approximation scheme for maximizing fidelity while satisfying an arbitrary cost bound. Our algorithms provide rigorous tools for supporting high-performance quantum network applications with financial consideration and offer strong theoretical guarantees. Extensive simulation results validate the advantageous performance in cost efficiency and/or fidelity compared to existing solutions and heuristics.
Operating a quantum network incurs high capital and operational expenditures, which are expected to be compensated by the high value of enabled quantum applications. However, existing mechanisms mainly focus on maximizing the entanglement distribution rate and neglect the cost incurred on users. This paper aims to address how to utilize quantum network resources in a cost-efficient manner while sustaining high-quantity and high-quality entanglement distribution. We first consider how to establish a steady stream of entanglements between remote nodes with the minimum cost. Utilizing a recent flow-based abstraction and a novel graph representation, we design an optimal algorithm for min-cost remote entanglement distribution. Next, we consider distributing entanglements with the highest fidelity subject to a cost bound and prove its NP-hardness. To explore the cost-fidelity trade-off due to swapping and purification, we propose an approximation scheme for maximizing fidelity while satisfying an arbitrary cost bound. Our algorithms provide rigorous tools for supporting high-performance quantum network applications with financial consideration and offer strong theoretical guarantees. Extensive simulation results validate the advantageous performance in cost efficiency and/or fidelity compared to existing solutions and heuristics.
Operating a quantum network incurs high capital and operational expenditures, which are expected to be compensated by the high value of enabled quantum applications. However, existing mechanisms mainly focus on maximizing the entanglement distribution rate and neglect the cost incurred on users. This paper aims to address how to utilize quantum network resources in a cost-efficient manner while sustaining high-quantity entanglement distribution. We first consider how to establish a steady stream of entanglements between remote nodes with the minimum cost. Utilizing a recent flow-based abstraction and a novel graph representation, we design an optimal algorithm for min-cost remote entanglement distribution. Our algorithm provides rigorous tools for supporting high-performance quantum network applications with financial consideration and offers longterm data transmission in remote distances. Extensive simulation results validate the advantageous performance compared to existing solutions and heuristics.
Entanglement routing establishes remote entanglement connection between two arbitrary nodes, which is one of the most important functions in quantum networks. The existing routing mechanisms mainly improve the robustness and throughput facing the failure of entanglement generations, which, however, rarely include the considerations on the most important metric to evaluate the quality of connection, entanglement fidelity. To solve this problem, we propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks. In our proposal, we first consider the single S-D pair scenario and design an iterative routing algorithm, Q-PATH, to find the optimal purification decisions along the routing path with minimum entangled pair cost. Further, a low-complexity routing algorithm using an extended Dijkstra algorithm, Q-LEAP, is designed to reduce the computational complexity by using a simple but effective purification decision method. Then we consider the common scenario with multiple S-D pairs and design a greedy-based algorithm considering resource allocation and rerouting process for multiple routing requests. To verify the effectiveness and superiority of the proposed algorithms, extensive simulations are conducted, and the simulation results show that the proposed algorithms not only can provide fidelity-guarantee routing solutions, but also has superior performance in terms of throughput, fidelity of end-to-end entanglement connection, and resource utilization ratio, compared with the existing routing scheme.
Entanglement routing establishes remote entanglement connection between two arbitrary nodes, which is one of the most important functions in quantum networks. The existing routing mechanisms mainly improve the robustness and throughput facing the failure of entanglement generations, which, however, rarely include the considerations on the most important metric to evaluate the quality of connection, entanglement fidelity. To solve this problem, we propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (S-D) pairs in quantum networks. In our proposal, we first consider the single S-D pair scenario and design an iterative routing algorithm, Q-PATH, to find the optimal purification decisions along the routing path with minimum entangled pair cost. Further, a low-complexity routing algorithm using an extended Dijkstra algorithm, Q-LEAP, is designed to reduce the computational complexity by using a simple but effective purification decision method. Finally, we consider the common scenario with multiple S-D pairs and design a greedy-based algorithm considering resource allocation and re-routing process for multiple routing requests. Simulation results show that the proposed algorithms not only can provide fidelity-guaranteed routing solutions, but also has superior performance in terms of throughput, fidelity of end-to-end entanglement connection, and resource utilization ratio, compared with the existing routing scheme.
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.
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.
Quantum Internet has potential capabilities far beyond the traditional Internet and is thus a promising future platform for communication and computation. Entanglement is a cornerstone of quantum mechanics and forms the basis of numerous quantum applications in the quantum Internet. While existing studies primarily focus on two-user entanglement, a plethora of applications necessitates the leap to multi-user entanglement. This paper tackles the fundamental problem of multi-user entanglement routing in the quantum Internet, aiming to entangle multiple quantum users with a high entanglement rate. We abstract the problem as a novel graph routing problem, which is not readily addressed by existing graph problem solutions due to the unique characteristics of the quantum Internet. To address this problem, we first consider a sufficient condition ensuring a feasible solution's existence and design an algorithm with the optimal solution. Given the NP-Completeness and NP- Hardness of determining a feasible solution's existence and deriving an optimal solution in general cases, respectively, we propose two heuristic algorithms to offer efficient solutions, which are shown, via extensive simulations, to outperform the existing algorithms in terms of entanglement rates.