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

arXiv:2608.11501

Multi-Pair Fidelity-Aware Rate Allocation in a Quantum Network: Approximation Schemes

Zunzheng Zhang, Xuanli Lin, Zhaofeng Zhang, Nageswara S. V. Rao, Guoliang Xue

Published Aug 11, 2026• 1 citation
arXivHTMLPDF

Abstract

Entanglement distribution in quantum networks must jointly account for limited link capacities, probabilistic entanglement swapping, and heterogeneous link fidelities. In this paper, we study multi-pair fidelity-aware rate allocation in quantum networks. We formulate three rate-allocation problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Prior work has studied a special case of the rate sum problem, where all links have identical fidelity. This special case admits a polynomial-time algorithm. We prove that all three problems are NP-hard. We then study optimization versions of these problems which maximize the minimum end-to-end fidelity subject to throughput or fairness requirements. We present fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Experiments on randomly generated networks demonstrate the computational effectiveness of the proposed schemes.

DOI
10.48550/arxiv.2608.11501

Related papers

Computing an Optimal Entanglement Path With Throughput and Fidelity Considerations

Guoliang Xue, Nageswara S. V. Rao, Don Towsley +7 more

Entanglement distribution is a core function of quantum networks essential for operations including teleportation, distributed quantum sensing, and multisite computation. Entanglement throughput and fidelity are two critical performance measures that depend on the quantum transmission along the links and swapping operations at the repeaters along the path. We study the problem of computing an end-to-end entanglement path that satisfies both fidelity and throughput requirements, leveraging qubit buffers at the nodes and considering the sequential swapping order. We show that the general problem of simultaneously satisfying both metrics is NP-hard, and develop an algorithm to maximize throughput subject to a given fidelity threshold. We introduce the concepts of entanglement probability distribution and path domination and exploit them in the design of our algorithm. Extensive numerical results show that our algorithm can find optimal solutions in networks with thousands of nodes in less than a second. We also describe practical and possible implementation aspects of this algorithm in terms of devices and architecture support.

IEEE Transactions on Networking•Jan 1, 2026•0 citations

Entanglement Distribution in a Quantum Network: A Multicommodity Flow-Based Approach

Kaushik Chakraborty, David Elkouss, Bruno Rijsman +1 more

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.

arXiv:2005.14304•IEEE Transactions on Quantum Engineering•Jan 1, 2020•135 citations

Entanglement Rate Maximization for Dual-Connectivity Wireless Quantum Networks

Kavini Thenuwara, Shiva Kazemi Taskooh, Ekram Hossain

The development of quantum networks (QNs) relies on efficient mechanisms for distributing entanglement among multiple quantum users (QUs) under practical system constraints. This paper investigates the problem of entanglement rate maximization in a dual-connectivity (DC) wireless quantum network comprising multiple quantum base stations (QBSs). Under the DC architecture, each QU can associate with up to two QBSs, thereby enhancing resource utilization compared to conventional single-connectivity (SC) schemes. The joint QBS-QU association and entanglement generation rate allocation problem is formulated as a mixed-integer nonlinear programming problem that incorporates practical constraints, including limited QBS entanglement generation capacity as well as heterogeneous minimum entanglement rate demands and fidelity requirements for QUs. To efficiently solve this challenging problem, an alternating optimization (AO) algorithm is developed, which decomposes the original formulation into entanglement rate allocation and association subproblems. Simulation results demonstrate that the proposed DC architecture significantly outperforms SC schemes, while the AO algorithm achieves near-optimal performance with substantially reduced computational complexity.

quant-pharXiv:2604.04143•Apr 7, 2026•0 citations

Optimal Fidelity-Aware Entanglement Distribution in Linear Quantum Networks

Iordanis Koutsopoulos

We study the problem of entanglement distribution in terms of maximizing a utility function that captures the total fidelity of end-to-end entanglements in a two-link linear quantum network with a source, a repeater, and a destination. The nodes have several quantum memories, and the problem is how to coordinate entanglement purification in each of the links, and entanglement swapping across links so as to achieve the goal above. We show that entanglement swapping (i.e, deciding on the pair of qubits from each link to perform swapping on) is equivalent to finding a max-weight matching on a bipartite graph. Further, entanglement purification (i.e, deciding which pairs of qubits in a link will undergo purification) is equivalent to finding a max-weight matching on a non-bipartite graph. We propose two polynomial algorithms, the Purify-then-Swap (PtS) and the Swap-then-Purify (StP) ones, where the decisions about purification and swapping are taken with different order. Numerical results show that PtS performs better than StP, and that the omission of purification in StP gives substantial benefits.

arXiv:2407.09171•IEEE Military Communications Conference (MILCOM)•Oct 28, 2024•4 citations

Cost-Aware High-Fidelity Entanglement Distribution and Purification in the Quantum Internet

Huayue Gu, Zhouyu Li, Xiaojian Wang +3 more

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.

IEEE Transactions on Networking•Sep 8, 2025•2 citations

FENDI: Toward High-Fidelity Entanglement Distribution in the Quantum Internet

Huayue Gu, Zhouyu Li, Ruozhou Yu +4 more

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.

arXiv:2301.08269•IEEE/ACM Transactions on Networking•Sep 13, 2024•36 citations
Entanglement distribution in quantum networks must jointly account for limited link capacities, probabilistic entanglement swapping, and heterogeneous link fidelities. In this paper, we study multi-pair fidelity-aware rate allocation in quantum networks. We formulate three rate-allocation problems: rate sum, rate sum subject to minimum-rate constraints, and max-min fairness. Prior work has studied a special case of the rate sum problem, where all links have identical fidelity. This special case admits a polynomial-time algorithm. We prove that all three problems are NP-hard. We then study optimization versions of these problems which maximize the minimum end-to-end fidelity subject to throughput or fairness requirements. We present fully polynomial-time approximation schemes (FPTAS) for solving these optimization problems. Experiments on randomly generated networks demonstrate the computational effectiveness of the proposed schemes.
Entanglement distribution is a core function of quantum networks essential for operations including teleportation, distributed quantum sensing, and multisite computation. Entanglement throughput and fidelity are two critical performance measures that depend on the quantum transmission along the links and swapping operations at the repeaters along the path. We study the problem of computing an end-to-end entanglement path that satisfies both fidelity and throughput requirements, leveraging qubit buffers at the nodes and considering the sequential swapping order. We show that the general problem of simultaneously satisfying both metrics is NP-hard, and develop an algorithm to maximize throughput subject to a given fidelity threshold. We introduce the concepts of entanglement probability distribution and path domination and exploit them in the design of our algorithm. Extensive numerical results show that our algorithm can find optimal solutions in networks with thousands of nodes in less than a second. We also describe practical and possible implementation aspects of this algorithm in terms of devices and architecture support.
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.
The development of quantum networks (QNs) relies on efficient mechanisms for distributing entanglement among multiple quantum users (QUs) under practical system constraints. This paper investigates the problem of entanglement rate maximization in a dual-connectivity (DC) wireless quantum network comprising multiple quantum base stations (QBSs). Under the DC architecture, each QU can associate with up to two QBSs, thereby enhancing resource utilization compared to conventional single-connectivity (SC) schemes. The joint QBS-QU association and entanglement generation rate allocation problem is formulated as a mixed-integer nonlinear programming problem that incorporates practical constraints, including limited QBS entanglement generation capacity as well as heterogeneous minimum entanglement rate demands and fidelity requirements for QUs. To efficiently solve this challenging problem, an alternating optimization (AO) algorithm is developed, which decomposes the original formulation into entanglement rate allocation and association subproblems. Simulation results demonstrate that the proposed DC architecture significantly outperforms SC schemes, while the AO algorithm achieves near-optimal performance with substantially reduced computational complexity.
We study the problem of entanglement distribution in terms of maximizing a utility function that captures the total fidelity of end-to-end entanglements in a two-link linear quantum network with a source, a repeater, and a destination. The nodes have several quantum memories, and the problem is how to coordinate entanglement purification in each of the links, and entanglement swapping across links so as to achieve the goal above. We show that entanglement swapping (i.e, deciding on the pair of qubits from each link to perform swapping on) is equivalent to finding a max-weight matching on a bipartite graph. Further, entanglement purification (i.e, deciding which pairs of qubits in a link will undergo purification) is equivalent to finding a max-weight matching on a non-bipartite graph. We propose two polynomial algorithms, the Purify-then-Swap (PtS) and the Swap-then-Purify (StP) ones, where the decisions about purification and swapping are taken with different order. Numerical results show that PtS performs better than StP, and that the omission of purification in StP gives substantial benefits.
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.
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.