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

Aug 11, 2026· Zunzheng Zhang , Xuanli Lin , Zhaofeng Zhang , Nageswara S. V. Rao , Guoliang Xue · 1 min read
Summary
This preprint studies quantum-network rate allocation across multiple communicating pairs with unequal link fidelities and limited capacity. It proves three throughput and fairness formulations are NP-hard, then develops fully polynomial-time approximation schemes that maximize the minimum end-to-end fidelity under throughput or fairness requirements. Experiments evaluate their computational effectiveness.
Type
Publication
arXiv preprint arXiv:2608.11501
publication

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.

Preprint, first submitted 2026-08-11.

Quantum Networks Rate Allocation Approximation Algorithms
Zunzheng Zhang
Authors
Zunzheng Zhang
PhD Student in Computer Science
Zunzheng Zhang is a PhD student in computer science at Arizona State University. He studies network optimization and quantum networks. Before joining ASU, he earned his bachelor’s and master’s degrees in electronic engineering from Nanjing University in 2021 and 2024, respectively.
Xuanli Lin
Authors
Xuanli Lin
PhD Student in Computer Science

Xuanli Lin is a fifth-year PhD student in the Computer Science department at Arizona State University, supervised by Dr. Guoliang Xue.

His research interests include network optimization, network security, artificial intelligence, and the Internet of Things.

Nageswara S. V. Rao
Authors
Nageswara S. V. Rao
Corporate Fellow
Nageswara S. V. Rao is a Corporate Fellow at Oak Ridge National Laboratory, which he joined in 1993. His research covers high-performance and quantum networking, information fusion, machine learning, and connected scientific instruments. He earned his PhD in computer science from Louisiana State University in 1988. He is an IEEE Fellow and a recipient of the IEEE Computer Society Technical Achievement Award and an R&D 100 Award.
Guoliang Xue
Authors
Guoliang Xue
Professor of Computer Science and Engineering
Guoliang Xue is a professor in Arizona State University’s School of Computing and Augmented Intelligence and an IEEE Fellow. He investigates wireless and quantum networks, network security and privacy, and optimization. He earned his PhD in computer science from the University of Minnesota in 1991. His honors include the IEEE Communications Society’s 2019 William R. Bennett Prize, and he chaired the IEEE INFOCOM Steering Committee from 2020 through 2025.