Routing and Spectrum Allocation in Broadband Quantum Entanglement Distribution
- 10 March 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 43 (5) , 1856-1870
Abstract
We investigate resource allocation for quantum entanglement distribution over an optical network. We characterize and model a network architecture that employs a single broadband quasi-deterministic time-frequency heralded Einstein-Podolsky-Rosen (EPR) pair source, and develop a routing and spectrum allocation scheme for distributing entangled photon pairs over such a network. As our setting allows separately solving the routing and spectrum allocation problems, we first find an optimal polynomial-time routing algorithm. We then employ max-min fairness criterion for spectrum allocation, which presents an NP-hard problem. Thus, we focus on approximately-optimal schemes. We compare their performance by evaluating the max-min and median number of EPR-pair rates assigned by them, and the associated Jain index. We identify two polynomial-time approximation algorithms that perform well, or better than others under these metrics. We also investigate scalability by analyzing how the network size and connectivity affect performance using Watts-Strogatz random graphs. We find that a spectrum allocation approach that achieves higher minimum EPR-pair rate can perform significantly worse when the median EPR-pair rate, Jain index, and computational resources are considered. Additionally, we evaluate the effect of the source node placement on the performance.Keywords
Funding Information
- National Science Foundation (CNS-2107265)
- Research Ireland (20/US/3708, 21/US-C2C/3750, 13/RC/2077_P2)
This publication has 39 references indexed in Scilit:
- Fair allocation of indivisible goods and choresAutonomous Agents and Multi-Agent Systems, 2021
- Routing entanglement in the quantum internetnpj Quantum Information, 2019
- Fundamental limits of repeaterless quantum communicationsNature Communications, 2017
- Fundamental rate-loss tradeoff for optical quantum key distributionNature Communications, 2014
- Optical Network Design and Planning2014
- An analysis of the LPT algorithm for the max–min and the min–ratio partition problemsTheoretical Computer Science, 2005
- Collective dynamics of ‘small-world’ networksNature, 1998
- Parallel Algorithm for Shortest Pairs of Edge-Disjoint PathsJournal of Parallel and Distributed Computing, 1996
- A quick method for finding shortest pairs of disjoint pathsNetworks, 1984
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955