arXiv:2210.08135 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Quantum Network Utility Maximization

Gayane Vardoyan, Stephanie Wehner

Published Sep 17, 2023• 24 citations

Abstract

Network Utility Maximization (NUM) is a mathe-matical framework that has endowed researchers with powerful methods for designing and analyzing classical communication protocols. NUM has also enabled the development of distributed algorithms for solving the resource allocation problem, while at the same time providing certain guarantees, e.g., that of fair treatment, to the users of a network. We extend here the notion of NUM to quantum networks, and propose three quantum utility functions - each incorporating a different entanglement measure. We aim both to gain an understanding of some of the ways in which quantum users may perceive utility, as well as to explore structured and theoretically-motivated methods of simultaneously servicing multiple users in distributed quantum systems. Using our quantum NUM constructions, we develop an optimization framework for networks that use the single-photon scheme for entanglement generation, which enables us to solve the resource allocation problem while exploring rate-fidelity tradeoffs within the network topologies that we consider. We learn that two of our utility functions, which are based on distillable entanglement and secret key fraction, are in close agreement with each other and produce similar solutions to the optimization problems we study. While these two utilities place a higher emphasis on end-to-end fidelity, our third utility- based on entanglement negativity - has more favorable mathematical properties, and tends to place a higher value on the rate at which users receive entangled resources. These contrasting behaviors thus provide ideas regarding the suitability of quantum network utility definitions to different quantum applications.

DOI: 10.1109/qce57702.2023.00140

Related papers

Convexification of the Quantum Network Utility Maximization Problem

Sounak Kar, Stephanie Wehner

Network utility maximization (NUM) addresses the problem of allocating resources fairly within a network and explores the ways to achieve optimal allocation in real-world networks. Although extensively studied in classical networks, NUM is an emerging area of research in the context of quantum networks. In this work, we consider the quantum network utility maximization (QNUM) problem in a static setting, where a user's utility takes into account the assigned quantum quality (fidelity) via a generic entanglement measure, as well as the corresponding rate of entanglement generation. Under certain assumptions, we demonstrate that the QNUM problem can be formulated as an optimization problem with the rate allocation vector as the only decision variable. Using a change-of-variable technique known in the field of geometric programming, we then establish sufficient conditions under which this formulation can be reduced to a convex problem: a class of optimization problems that can be solved efficiently and with certainty even in high dimensions. We further show that this technique preserves convexity, enabling us to formulate convex QNUM problems in networks where some routes have certain entanglement measures that do not readily admit convex formulation while others do. This allows us to compute the optimal resource allocation in networks where heterogeneous applications run over different routes.

IEEE Transactions on Quantum EngineeringDec 30, 20246 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.01197Mar 3, 20260 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.

International Conference on Quantum Communications, Networking, and Computing (QCNC)Apr 6, 20260 citations

Optimum Resource Allocation in Secure Quantum Networks: Survey of Enabling Technology

Savo Glisic, Beatriz Lorenzo

Due to its complexity, resource allocation in complex communication networks has been always designed with great deal of approximations and restrictions. With the availability of quantum computing, quantum optimization and quantum search algorithms, we are able to overcome these limitations significantly and come up with more precise and efficient “quantum era” algorithms. The main objective of this paper is to provide the future network designers with a new optimization framework for resource (capacity and secrete key rate) allocation in quantum networks. The analysis is general to include: the classical capacityC, for transmitting classical information; the quantum capacityQ, for reliably transmitting intact quantum states; the two-way classical-assisted quantum capacityQ2, for transmitting quantum states with the help of a two-way classical side channel; and the entanglement-assisted classical capacityCE, which we define as the classical capacity of a quantum channel enabled by prior shared entanglement between two nodes. Once the optimization framework is introduced the rest of the paper discusses the optimization constraints, by surveying some examples of the relevant work on achievable network resources (capacity and secrete key rate) and relaxation of the optimization constraints by increasing these parameters using the quantum coding schemes. These constraints are an integral part of the optimization algorithms and full understanding of their nature and limits is essential for system optimization. The achievable secret key rates/capacity of quantum channels are limited, so our optimization framework for resource allocation enables maximization of the overall resources allocated to all users, or maximization of the number of users accessing the network, or minimization of the number of hopes on the routes or maximization of remaining resources in the most critical node in the network. The optimization problems have combinatorial form, and the most efficient execution of these algorithms can be achieved by using quantum search algorithms like Grover’s algorithm or quantum approximative optimization algorithms (QAOA) which are extensively discussed in the paper.Regarding the scope of the technology survey in Section VIII we summarize the coverage of our targeted survey and the coverage of other relevant works.

IEEE AccessJan 1, 20253 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.04143Apr 7, 20260 citations

A Framework for Distributed Resource Allocation in Quantum Networks

Nitish K. Panigrahy, Leonardo Bacciottini, C.V. Hollot +5 more

We introduce a distributed resource allocation framework for the Quantum Internet that relies on feedback-based, fully decentralized coordination to serve multiple co-existing applications. We develop quantum network control algorithms under the mathematical framework of Quantum Network Utility Maximization (QNUM), where utility functions quantify network performance by mapping entanglement rate and quality into a joint optimization objective. We then introduce QPrimal-Dual, a decentralized, scalable algorithm that solves QNUM by strategically placing network controllers that operate using local state information and limited classical message exchange. We prove global asymptotic stability for concave, separable utility functions, and provide sufficient conditions for local stability for broader non-concave cases. To reduce control overhead and account for quantum memory decoherence, we also propose schemes that locally approximate global quantities and prevent congestion in the network. We evaluate the performance of our approach via simulations in realistic quantum network architectures. Results show that QPrimalDual significantly outperforms baseline allocation strategies, scales with network size, and is robust to latency and decoherence. Our observations suggest that QPrimalDual could be a practical, high-performance foundation for fully distributed resource allocation in quantum networks.

arXiv:2510.09371Oct 10, 20250 citations