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

QuNet: Cost vector analysis & multi-path entanglement routing in quantum networks

Hudson Leone, Nathan Miller, Deepesh Singh, Nathan K. Langford, Peter P. Rohde

Published May 2, 2021• 13 citations
OpenAlex

Abstract

Entanglement distribution will form the backbone of many future distributed quantum technologies, especially the quantum internet. The act of purifying multiple noisy entangled states into a single one of higher quality has no analogue in classical networking and as such, this transforms the way in which we will consider future algorithms for routing entanglement. We outline the differences that arise because of this, demonstrate some elementary formalisms for `multi-path entanglement routing', and discuss the philosophical differences that arise when comparing this regime to conventional digital network theory. We also present a software package, QuNet, that uses novel `quantum cost-vector analysis' to simulate and benchmark routing in multi-user entanglement networks in a way that is is highly scalable in network size and the number of competing users. Our software accommodates both ground- and space-based networks, and implements efficient multi-user time-optimisation for mitigating congestion when quantum memories are available.

Related papers

Cost vector analysis & multi-path entanglement routing in quantum networks

Hudson Leone, Miller, Nathaniel R., Deepesh Singh +2 more

We present a static framework for analysing quantum routing protocols that we call the \textit{cost-vector formalism}. Here, quantum networks are recast as multi-graphs where edges represent two-qubit entanglement resources that \textit{could} exist under some sequence of operations. Each edge is weighted with a \textit{transmission probability} that represents the likelihood of the pair existing and a \textit{coherence probability} which is the likelihood that the pair is suitable for teleportation. Routing operations such as entanglement swapping and purification are then interpreted as \textit{contractions on the multi-graph} with relatively simple rules for updating the edge-weights. Moreover, we extend our formalism to include routing scenarios over time by developing a compatible resource theory for quantum memories. We develop rudimentary greedy algorithms for routing in this framework and test them over a variety of toy networking scenarios. Our results indicate that congestion in quantum networks does not improve significantly when more nodes (computers) are added. Rather, we find that congestion is all but eliminated by waiting a small amount of time.

arXiv:2105.00418•May 2, 2021•24 citations

On Utility-optimal Entanglement Routing in Quantum Networks

Sounak Kar, Arpan Mukhopadhyay

Quantum networks are envisioned to enable reliable distribution and manipulation of quantum information across distances, forming the foundation of a future quantum internet. The fair and efficient allocation of communication resources in such networks has been addressed through the quantum network utility maximization (QNUM) framework, which optimizes network utility under the assumption of predetermined routes for competing user demands. In this work, we relax this assumption and aim to identify optimal routes that correspond to the maximum achievable network utility. Specifically, we formulate the single-path utility-based entanglement routing problem as a Mixed-Integer Convex Program (MICP). The formulation is exact when negativity is chosen as the entanglement measure for utility quantification or the network supports sufficiently high entanglement generation rates across demands. For other entanglement measures considered, the formulation approximates the problem with over 99.99% accuracy on evaluated real-world examples. To improve computational tractability, we propose a randomized rounding-based heuristic and an upper bound via the relaxation of the MICP. Furthermore, based on min-congestion routing, we introduce an alternative randomized heuristic and upper bound. This heuristic is computationally faster, while both the heuristic and the upper bound often outperform their counterparts on considered real-world networks. Our work provides the framework for extending classical flow-based and quality of service-aware routing concepts to quantum networks.

quant-pharXiv:2603.01197•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Mar 3, 2026•1 citation

Multi-User Entanglement Routing for Quantum Mesh Networks

Evan Sutcliffe, Matty J. Hoban, Alejandra Beghelli

Multipath routing for sharing entanglement between multiple devices was simulated on real network topologies and compared against single-path routing. Results show improved entanglement rates, especially for topologies with a higher average nodal degree. © 2022 The Author(s)

Optical Fiber Communication Conference•Jan 1, 2023•1 citation

Multi-User Entanglement Routing Design over Quantum Internets

Yiming Zeng, Jiarui Zhang, Xiaojun Shang +3 more

Quantum Internet has potential capabilities far beyond the traditional Internet and is thus a promising future platform for communication and computation. Entanglement is a cornerstone of quantum mechanics and forms the basis of numerous quantum applications in the quantum Internet. While existing studies primarily focus on two-user entanglement, a plethora of applications necessitates the leap to multi-user entanglement. This paper tackles the fundamental problem of multi-user entanglement routing in the quantum Internet, aiming to entangle multiple quantum users with a high entanglement rate. We abstract the problem as a novel graph routing problem, which is not readily addressed by existing graph problem solutions due to the unique characteristics of the quantum Internet. To address this problem, we first consider a sufficient condition ensuring a feasible solution's existence and design an algorithm with the optimal solution. Given the NP-Completeness and NP- Hardness of determining a feasible solution's existence and deriving an optimal solution in general cases, respectively, we propose two heuristic algorithms to offer efficient solutions, which are shown, via extensive simulations, to outperform the existing algorithms in terms of entanglement rates.

IEEE International Conference on Distributed Computing Systems (ICDCS)•Jul 23, 2024•7 citations

Purification and Entanglement Routing on Quantum Networks

Michelle Victora, Stefan Krastanov, Alexander Sanchez de la Cerda +2 more

We present an approach to purification and entanglement routing on complex quantum network architectures, that is, how a quantum network equipped with imperfect channel fidelities and limited memory storage time can distribute entanglement between users. We explore how network parameters influence the performance of path-finding algorithms necessary for optimizing routing and, in particular, we explore the interplay between the bandwidth of a quantum channels and the choice of purification protocol. Finally, we demonstrate multi-path routing on various network topologies with resource constraints, in an effort to inform future design choices for quantum network configurations. Our work optimizes both the choice of path over the quantum network and the choice of purification schemes used between nodes. We consider not only pair-production rate, but optimize over the fidelity of the delivered entangled state. We introduce effective heuristics enabling fast path-finding algorithms for maximizing entanglement shared between two nodes on a quantum network, with performance comparable to that of a computationally-expensive brute-force path search.

arXiv:2011.11644•Nov 23, 2020•42 citations

Impact of Topology on Multipartite Entanglement Distribution Protocols in Quantum Networks

Jazz E. Z. Ooi, Evan Sutcliffe, Alejandra Beghelli

Quantum networks will rely on entanglement distribution to enable multi-user applications such as distributed quantum computing and cryptography. While multipartite entanglement distribution routing protocols have been extensively studied on idealised grid topologies, less is understood about how real network structure shapes their performance and resource requirements. We present a systematic study of four routing protocols for multipartite entanglement distribution, each characterised by the number of paths (single-path and multi-path) and routing strategy (star-based and tree-based), over 81 real network topologies. We identified four distinct topology-dependent performance regimes, where: (i) all protocols perform poorly, (ii) tree-based protocols dominate, (iii) multi-path protocols dominate, or (iv) all protocols perform well. By correlating clusters with graph metrics, we also provide structural explanations for the varied performance of specific protocols. Additionally, motivated by the anticipated high cost of repeaters, we investigated the impact of repeater trimming on the performance of multi-path protocols. Topology strongly governs how far repeater nodes can be removed from the network while maintaining a given performance (distribution rate). For instance, in networks where only 80% of nodes operate as repeaters, well-performing topologies are able to retain over 90% of the distribution rate; whereas sparse, weakly connected graphs exhibit rapid performance degradation, retaining less than half of the distribution rate. Our results provide a topology-aware framework for protocol selection and infrastructure optimisation in future quantum networks, bridging routing design with cost-aware deployment strategies.

quant-pharXiv:2603.25920•Journal of Optical Communications and Networking•Mar 30, 2026•1 citation
Entanglement distribution will form the backbone of many future distributed quantum technologies, especially the quantum internet. The act of purifying multiple noisy entangled states into a single one of higher quality has no analogue in classical networking and as such, this transforms the way in which we will consider future algorithms for routing entanglement. We outline the differences that arise because of this, demonstrate some elementary formalisms for multi-path entanglement routing', and discuss the philosophical differences that arise when comparing this regime to conventional digital network theory. We also present a software package, QuNet, that uses novel quantum cost-vector analysis' to simulate and benchmark routing in multi-user entanglement networks in a way that is is highly scalable in network size and the number of competing users. Our software accommodates both ground- and space-based networks, and implements efficient multi-user time-optimisation for mitigating congestion when quantum memories are available.
We present a static framework for analysing quantum routing protocols that we call the \textit{cost-vector formalism}. Here, quantum networks are recast as multi-graphs where edges represent two-qubit entanglement resources that \textit{could} exist under some sequence of operations. Each edge is weighted with a \textit{transmission probability} that represents the likelihood of the pair existing and a \textit{coherence probability} which is the likelihood that the pair is suitable for teleportation. Routing operations such as entanglement swapping and purification are then interpreted as \textit{contractions on the multi-graph} with relatively simple rules for updating the edge-weights. Moreover, we extend our formalism to include routing scenarios over time by developing a compatible resource theory for quantum memories. We develop rudimentary greedy algorithms for routing in this framework and test them over a variety of toy networking scenarios. Our results indicate that congestion in quantum networks does not improve significantly when more nodes (computers) are added. Rather, we find that congestion is all but eliminated by waiting a small amount of time.
Quantum networks are envisioned to enable reliable distribution and manipulation of quantum information across distances, forming the foundation of a future quantum internet. The fair and efficient allocation of communication resources in such networks has been addressed through the quantum network utility maximization (QNUM) framework, which optimizes network utility under the assumption of predetermined routes for competing user demands. In this work, we relax this assumption and aim to identify optimal routes that correspond to the maximum achievable network utility. Specifically, we formulate the single-path utility-based entanglement routing problem as a Mixed-Integer Convex Program (MICP). The formulation is exact when negativity is chosen as the entanglement measure for utility quantification or the network supports sufficiently high entanglement generation rates across demands. For other entanglement measures considered, the formulation approximates the problem with over 99.99% accuracy on evaluated real-world examples. To improve computational tractability, we propose a randomized rounding-based heuristic and an upper bound via the relaxation of the MICP. Furthermore, based on min-congestion routing, we introduce an alternative randomized heuristic and upper bound. This heuristic is computationally faster, while both the heuristic and the upper bound often outperform their counterparts on considered real-world networks. Our work provides the framework for extending classical flow-based and quality of service-aware routing concepts to quantum networks.
Quantum Internet has potential capabilities far beyond the traditional Internet and is thus a promising future platform for communication and computation. Entanglement is a cornerstone of quantum mechanics and forms the basis of numerous quantum applications in the quantum Internet. While existing studies primarily focus on two-user entanglement, a plethora of applications necessitates the leap to multi-user entanglement. This paper tackles the fundamental problem of multi-user entanglement routing in the quantum Internet, aiming to entangle multiple quantum users with a high entanglement rate. We abstract the problem as a novel graph routing problem, which is not readily addressed by existing graph problem solutions due to the unique characteristics of the quantum Internet. To address this problem, we first consider a sufficient condition ensuring a feasible solution's existence and design an algorithm with the optimal solution. Given the NP-Completeness and NP- Hardness of determining a feasible solution's existence and deriving an optimal solution in general cases, respectively, we propose two heuristic algorithms to offer efficient solutions, which are shown, via extensive simulations, to outperform the existing algorithms in terms of entanglement rates.
We present an approach to purification and entanglement routing on complex quantum network architectures, that is, how a quantum network equipped with imperfect channel fidelities and limited memory storage time can distribute entanglement between users. We explore how network parameters influence the performance of path-finding algorithms necessary for optimizing routing and, in particular, we explore the interplay between the bandwidth of a quantum channels and the choice of purification protocol. Finally, we demonstrate multi-path routing on various network topologies with resource constraints, in an effort to inform future design choices for quantum network configurations. Our work optimizes both the choice of path over the quantum network and the choice of purification schemes used between nodes. We consider not only pair-production rate, but optimize over the fidelity of the delivered entangled state. We introduce effective heuristics enabling fast path-finding algorithms for maximizing entanglement shared between two nodes on a quantum network, with performance comparable to that of a computationally-expensive brute-force path search.
Quantum networks will rely on entanglement distribution to enable multi-user applications such as distributed quantum computing and cryptography. While multipartite entanglement distribution routing protocols have been extensively studied on idealised grid topologies, less is understood about how real network structure shapes their performance and resource requirements. We present a systematic study of four routing protocols for multipartite entanglement distribution, each characterised by the number of paths (single-path and multi-path) and routing strategy (star-based and tree-based), over 81 real network topologies. We identified four distinct topology-dependent performance regimes, where: (i) all protocols perform poorly, (ii) tree-based protocols dominate, (iii) multi-path protocols dominate, or (iv) all protocols perform well. By correlating clusters with graph metrics, we also provide structural explanations for the varied performance of specific protocols. Additionally, motivated by the anticipated high cost of repeaters, we investigated the impact of repeater trimming on the performance of multi-path protocols. Topology strongly governs how far repeater nodes can be removed from the network while maintaining a given performance (distribution rate). For instance, in networks where only 80% of nodes operate as repeaters, well-performing topologies are able to retain over 90% of the distribution rate; whereas sparse, weakly connected graphs exhibit rapid performance degradation, retaining less than half of the distribution rate. Our results provide a topology-aware framework for protocol selection and infrastructure optimisation in future quantum networks, bridging routing design with cost-aware deployment strategies.