Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Quantum Communications, Networking, and Computing (QCNC)

Minimum Cost Swapping and Purification Scheduling Over Quantum Repeater Chains

Jiyao Liu, Lei Fan, Yuanxiong Guo, Zhu Han, Yu Wang

Published Apr 6, 2026• 0 citations
Publisher

Abstract

Entanglement swapping and purification are two fundamental primitives for long-distance entanglement distribution in quantum networks, enabling key applications such as quantum key distribution, quantum sensing, and distributed quantum computing. While prior work has established that purification should precede swapping in Binary systems to minimize the expected number of consumed link-level entanglements for an E2E fidelity guarantee, the critical problem of finding the optimal swapping and purification strategy remains open. To fill this gap, we study the Optimal Swapping and Purification Tree (OSPT) problem for a quantum repeater chain in Binary systems and derive the exact optimal solution. By leveraging the associativity of swapping and purification fidelity, we decompose the problem into three subproblems: optimal swapping tree construction, optimal purification scheduling, and global budget allocation. We show that although the exact solution can be obtained via brute-force search over budget distributions, its complexity grows exponentially. To address this challenge, we further propose an efficient greedy budget allocation algorithm. Extensive evaluations demonstrate that the greedy algorithm closely approximates the optimal solution and outperforms existing solutions while significantly reducing computational complexity.

DOI
10.1109/qcnc69040.2026.00084

Related papers

Swapping and Purification Scheme Optimization for Entanglement Distribution in Quantum Networks

Jiyao Liu, Xinwen Zhang, Xinliang Wei +4 more

Swapping and purification are the two fundamental building blocks for high-fidelity entanglement distribution in multi-hop quantum networks. Unfortunately, it is still a mystery how they intertwine with each other to affect the fidelity and cost of end-to-end entanglements. Current scheduling algorithms consider this problem under relatively limited assumptions and a critical yet unjustified conjecture. In this work, we first consider more general assumptions with operation failures and, accordingly, extend a tree-based modeling for joint swapping and purification. Then, we analytically prove the previous conjecture that the optimal strategy underBinary systemis always to purify the entanglements before any swapping. This sheds light on the protocol and device design for quantum networks. We then further propose a tree-based algorithm, which can efficiently schedule swapping and purification along a path for bothBinaryandWerner systems. Extensive simulations of the proposed method against state-of-the-art solutions show that our method uses fewer entanglements to establish qualified end-to-end entanglements, and thus achieves higher network throughput.

IEEE Transactions on Networking•Jan 1, 2026•1 citation

Optimal Entanglement Routing in Quantum Repeater Chains: Beyond Fixed Operation Order and Purification Schedule

Aikaterini Mandilara, Antonia Tsili, Dimitris Syvridis +1 more

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.

quant-pharXiv:2609.37206•Sep 30, 2026•0 citations

Joint Swapping and Purification with Failures for Entanglement Distribution in Quantum Networks

Jiyao Liu, Xinwen Zhang, Xinliang Wei +4 more

Swapping and purification are the two fundamental building blocks for multi-hop quantum networks. However, their interplay and its impact on end-to-end fidelity and cost are not yet fully explored. Existing scheduling algorithms address this problem under certain simplified assumptions and models that may not fully capture the complexities of real scenarios. In this work, we first consider more general assumptions that account for operation failures and extend a tree-based modeling approach for joint swapping and purification. Then, for the first time, we analytically prove the previous conjecture that the optimal strategy under Binary system is always to purify the entanglements before any swapping. This sheds light on the protocol and device design for entanglement distribution in quantum networks. We then further propose a tree-based algorithm, which can efficiently schedule swapping and purification along a path for both Binary and Werner systems. Extensive simulations have been conducted to evaluate the proposed method against the existing solutions, and the results show that our method uses fewer entanglements to establish qualified end-to-end entanglements and thus achieves higher network throughput.

International Workshop on Quality of Service•Jul 2, 2025•4 citations

Purification scheduling control for throughput maximization in quantum networks

Zirui Xiao, Jian Li, Kaiping Xue +4 more

Abstract Quantum networks can establish End-to-End (E2E) entanglement connections between two arbitrary nodes for various quantum applications through entanglement swapping. To support quantum applications reliably, quantum networks should establish E2E entanglement connections with desired entanglement fidelity by performing entanglement purification. The existing works provide mechanisms for link-level purification, which, however, leads to low throughput because of lacking consideration on purifications at network-level. (That is, efficiently allocating scarce resources to jointly purify entanglements under the situation with multiple concurrent requests in a network remains a critical but unsolved problem.) To address this problem, we analyze the cost of purification, design the E2E fidelity calculation method in detail, and propose a novel approach called Purification Scheduling Control (PSC). The basic idea of PSC is to determine the appropriate purification through jointly optimizing purification and resource allocation processes based on conflict avoidance. We conduct extensive experiments showing that PSC can maximize throughput under the fidelity requirement. This solution should spur the development of more applied reliable routing designs for quantum networks, combining quantum error correction, quantum applications, and computer network theory.

Communications Physics•Sep 18, 2024•14 citations

Near-Optimal Techniques for Distributed Entanglement Generation and Purification

Xiaojie Fan, Yukun Yang, C. R. Ramakrishnan +1 more

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.

•Sep 11, 2025•0 citations

Distribution and Purification of Entanglement States in Quantum Networks

Xiaojie Fan, Yukun Yang, Himanshu Gupta +1 more

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.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 31, 2025•8 citations
Entanglement swapping and purification are two fundamental primitives for long-distance entanglement distribution in quantum networks, enabling key applications such as quantum key distribution, quantum sensing, and distributed quantum computing. While prior work has established that purification should precede swapping in Binary systems to minimize the expected number of consumed link-level entanglements for an E2E fidelity guarantee, the critical problem of finding the optimal swapping and purification strategy remains open. To fill this gap, we study the Optimal Swapping and Purification Tree (OSPT) problem for a quantum repeater chain in Binary systems and derive the exact optimal solution. By leveraging the associativity of swapping and purification fidelity, we decompose the problem into three subproblems: optimal swapping tree construction, optimal purification scheduling, and global budget allocation. We show that although the exact solution can be obtained via brute-force search over budget distributions, its complexity grows exponentially. To address this challenge, we further propose an efficient greedy budget allocation algorithm. Extensive evaluations demonstrate that the greedy algorithm closely approximates the optimal solution and outperforms existing solutions while significantly reducing computational complexity.
Swapping and purification are the two fundamental building blocks for high-fidelity entanglement distribution in multi-hop quantum networks. Unfortunately, it is still a mystery how they intertwine with each other to affect the fidelity and cost of end-to-end entanglements. Current scheduling algorithms consider this problem under relatively limited assumptions and a critical yet unjustified conjecture. In this work, we first consider more general assumptions with operation failures and, accordingly, extend a tree-based modeling for joint swapping and purification. Then, we analytically prove the previous conjecture that the optimal strategy underBinary systemis always to purify the entanglements before any swapping. This sheds light on the protocol and device design for quantum networks. We then further propose a tree-based algorithm, which can efficiently schedule swapping and purification along a path for bothBinaryandWerner systems. Extensive simulations of the proposed method against state-of-the-art solutions show that our method uses fewer entanglements to establish qualified end-to-end entanglements, and thus achieves higher network throughput.
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.
Swapping and purification are the two fundamental building blocks for multi-hop quantum networks. However, their interplay and its impact on end-to-end fidelity and cost are not yet fully explored. Existing scheduling algorithms address this problem under certain simplified assumptions and models that may not fully capture the complexities of real scenarios. In this work, we first consider more general assumptions that account for operation failures and extend a tree-based modeling approach for joint swapping and purification. Then, for the first time, we analytically prove the previous conjecture that the optimal strategy under Binary system is always to purify the entanglements before any swapping. This sheds light on the protocol and device design for entanglement distribution in quantum networks. We then further propose a tree-based algorithm, which can efficiently schedule swapping and purification along a path for both Binary and Werner systems. Extensive simulations have been conducted to evaluate the proposed method against the existing solutions, and the results show that our method uses fewer entanglements to establish qualified end-to-end entanglements and thus achieves higher network throughput.
Abstract Quantum networks can establish End-to-End (E2E) entanglement connections between two arbitrary nodes for various quantum applications through entanglement swapping. To support quantum applications reliably, quantum networks should establish E2E entanglement connections with desired entanglement fidelity by performing entanglement purification. The existing works provide mechanisms for link-level purification, which, however, leads to low throughput because of lacking consideration on purifications at network-level. (That is, efficiently allocating scarce resources to jointly purify entanglements under the situation with multiple concurrent requests in a network remains a critical but unsolved problem.) To address this problem, we analyze the cost of purification, design the E2E fidelity calculation method in detail, and propose a novel approach called Purification Scheduling Control (PSC). The basic idea of PSC is to determine the appropriate purification through jointly optimizing purification and resource allocation processes based on conflict avoidance. We conduct extensive experiments showing that PSC can maximize throughput under the fidelity requirement. This solution should spur the development of more applied reliable routing designs for quantum networks, combining quantum error correction, quantum applications, and computer network theory.
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.
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.