We consider problems of distributing high-fidelity entangled states across nodes of a quantum network. We consider a repeater-based network architecture with entanglement swapping (fusion) operations for generating long-distance entanglements, and purification operations that produce high-fidelity states from several lower-fidelity states. The contributions of this paper are two-fold: First, while there have been several works on fidelity-aware routing and incorporating purification into routing for generating EPs, this paper presents the first algorithms for optimal solutions to the high-fidelity EP distribution problem. We provide a dynamic programming algorithm for generating the optimal tree of operations to produce a high-fidelity EP, and an LP-based algorithm for generating an optimal collection of trees. Second, following the EP algorithms, this paper presents the first algorithms for the high-fidelity GHZ-state distribution problem and characterizes its optimality. We evaluate our techniques via simulations over NetSquid, a quantum network simulator.
We consider problems of distributing high-fidelity entangled states across nodes of a quantum network. We consider a repeater-based network architecture with entanglement swapping (fusion) operations for generating long-distance entanglements, and purification operations that produce high-fidelity states from several lower-fidelity states. The contributions of this paper are two-fold: First, while there have been several works on fidelity-aware routing and incorporating purification into routing for generating EPs, this paper presents the first algorithms for optimal solutions to the high-fidelity EP distribution problem. We provide a dynamic programming algorithm for generating the optimal tree of operations to produce a high-fidelity EP, and an LP-based algorithm for generating an optimal collection of trees. Second, following the EP algorithms, this paper presents the first algorithms for the high-fidelity GHZ-state distribution problem and characterizes its optimality. We evaluate our techniques via simulations over NetSquid, a quantum network simulator.
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.
Quantum networks rely on the efficient distribution of entanglement to enable long-distance quantum communication and information processing. A key challenge in these networks is the design of routing protocols capable of maintaining high quality entanglement in the presence of noise, decoherence, and imperfect operations, which progressively degrade the fidelity of entangled states through entanglement swapping. Entanglement purification provides an effective mechanism to mitigate this degradation at the cost of additional resources. In this work, we study purification-aware quantum routing and formulate the problem of selecting optimal purification strategies as an optimization task. By employing dynamic programming techniques, we identify strategies that optimally balance resource consumption and end-to-end fidelity, demonstrating the effectiveness of our approach across different scenarios.
Entanglement routing establishes entangled pairs between distant nodes of a quantum network by purifying and swapping pairs generated on elementary links. Existing methods typically restrict the decision space along two axes: the operation order, often fixed to purify-then-swap (PtS), and the purification schedule of each link, often restricted to pumping. Focusing on linear repeater chains with finite link capacities, we relax both restrictions and study the maximization of the expected end-to-end throughput subject to a fidelity threshold under two quantum-noise models. We develop a unified capacity-aware optimization framework comprising an exact mixed-integer linear program (MILP) under PtS, instantiated with either pumping or general tree purification schedules, and an exact dynamic program (DP) over arbitrary operation orders. Under symmetric Pauli noise, we prove that pumping converges to a fidelity strictly below unity, imposing a capacity-independent feasibility bound and a maximum chain length on every pumping-based PtS method, whereas general tree schedules yield a capacity-dependent bound. We further prove that post-swap purification never increases the throughput, so a free operation order can only increase feasibility. Numerical evaluations confirm the bounds: tree schedules serve over 90\% of the requests that pumping cannot at moderate fidelity thresholds; within the pumping class, a free operation order recovers much of this advantage; but once links use tree schedules, the tree-based MILP and the order-exact DP serve identical request sets throughout. Operation order and purification schedule are thus substitutes, with the purification schedule the dominant factor governing feasibility under symmetric Pauli noise.
In quantum networks, multipartite entangled states distributed over the network are useful in implementing and supporting many quantum network applications for communications, sensing, and computing. The focus of our work is to de-velop techniques to efficiently generate distributed Greenberger-Horne-Zeilinger (GHZ) states, a special class of multipartite entanglement states. Prior works on generating GHZ states have focused on the objective of minimizing the number of maximally entangled (bipartite) pairs (EPs), while ignoring the stochastic nature of quantum processes and assuming uniform network links for generating EPs. In contrast, in our work, we take into consideration the stochastic nature of quantum networks, and focus on maximizing the expected generated rate of the GHZ states under given fidelity constraints. In this context, we develop two efficient generation schemes, viz., Fusion - Retain - only and General Fusion, comprised of optimal or near-optimal sub-steps. Both schemes, at a high-level, first determine a way to “connect” the nodes over which the GHZ state is to distributed, and then, determine a sequence of fusion operations on the EPs created over the connections. Using extensive simulations over a quantum network simulator (NetSquid), we demonstrate the effectiveness of our developed techniques and show that our schemes outperform prior work as well as a simple centralized approach by up to orders of magnitude while generating GHZ states of tolerable fidelity.
Quantum network communication is challenging, as the no-cloning theorem in the quantum regime makes many classical techniques inapplicable; in particular, the direct transmission of qubit states over long distances is infeasible due to unrecoverable errors. For the long-distance communication of unknown quantum states, the only viable communication approach (assuming local operations and classical communications) is the teleportation of quantum states, which requires a prior distribution of the entangled pairs (EPs) of qubits. The establishment of EPs across remote nodes can incur significant latency due to the low probability of success of the underlying physical processes. The focus of our work is to develop efficient techniques that minimize EP generation latency. Prior works have focused on selecting entanglementpaths; in contrast, we selectentanglement swapping trees—a more accurate representation of the entanglement generation structure. We develop a dynamic programming algorithm to select an optimal swapping tree for a single pair of nodes, under the given capacity and fidelity constraints. For the general setting, we develop an efficient iterative algorithm to compute a set of swapping trees. We present simulation results, which show that our solutions outperform the prior approaches by an order of magnitude and are viable for long-distance entanglement generation.
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.