Distributed quantum computing (DQC) holds immense promise in harnessing the potential of quantum computing by interconnecting multiple small quantum computers (QCs) through a quantum data network (QDN). Establishing long-distance quantum entanglement between two QCs for quantum teleportation within the QDN is a critical aspect, and it involves entanglement routing - finding a route between QCs and efficiently allocating qubits along that route. Existing approaches have mainly focused on optimizing entanglement performance for current entanglement connection (EC) requests. However, they often overlook the user's perspective, wherein the user making EC requests operates under a budget constraint over an extended period. Furthermore, both QDN resources (quantum channels and qubits) and the EC requests, reflecting the DQC workload, vary over time. In this paper, we present a novel user-centric entanglement routing problem that spans an extended period to maximize the entanglement success rate while adhering to the user's budget constraint. To address this challenge, we leverage the Lyapunov drift-plus-penalty framework to decompose the long-term optimization problem into per-slot problems, allowing us to find solutions using only the current system information. Subsequently, we develop efficient algorithms based on continuous-relaxation and Gibbs-sampling techniques to solve the per-slot entanglement routing problem. Theoretical performance guarantees are provided for both the per-slot and long-term problems. Extensive simulations demonstrate that our algorithm significantly outperforms baseline approaches in terms of entanglement success rate and budget adherence.
Distributed quantum computing (DQC) holds immense promise in harnessing the potential of quantum computing by interconnecting multiple small quantum computers (QCs) through a quantum data network (QDN). Establishing long-distance quantum entanglement between two QCs for quantum teleportation within the QDN is a critical aspect, and it involves entanglement routing - finding a route between QCs and efficiently allocating qubits along that route. Existing approaches have mainly focused on optimizing entanglement performance for current entanglement connection (EC) requests. However, they often overlook the user's perspective, wherein the user making EC requests operates under a budget constraint over an extended period. Furthermore, both QDN resources (quantum channels and qubits) and the EC requests, reflecting the DQC workload, vary over time. In this paper, we present a novel user-centric entanglement routing problem that spans an extended period to maximize the entanglement success rate while adhering to the user's budget constraint. To address this challenge, we leverage the Lyapunov drift-plus-penalty framework to decompose the long-term optimization problem into per-slot problems, allowing us to find solutions using only the current system information. Subsequently, we develop efficient algorithms based on continuous-relaxation and Gibbs-sampling techniques to solve the per-slot entanglement routing problem. Theoretical performance guarantees are provided for both the per-slot and long-term problems. Extensive simulations demonstrate that our algorithm significantly outperforms baseline approaches in terms of entanglement success rate and budget adherence.
Quantum Data Networks (QDNs) typically leverage teleportation to reliably send data quantum bits (called qubits) to their destinations. To teleport a data qubit from Alice to Bob, one entanglement connection between Alice and Bob needs to be established. Accordingly, we have to establish as many entanglement connections as possible with limited quantum resources in order to maximize the network throughput. Conventional methods assume a known traffic matrix and calculate the paths to establish entanglement connections in one batch using a centralized algorithm. However, these methods are not scalable in large scale QDNs since it is time consuming to optimize the entanglement paths for a batch of requests, which may result in a long time slot duration and significantly reduce the network throughput. To address this issue, we propose an Online Entanglement Routing (OER) scheme which determines the entanglement paths for each request when it arrives. In addition, OER pursues work conservation and fairness among all requests in the QDNs. Through extensive simulations, we demonstrate that OER not only outperforms two representative heuristics by up to 61.27% and 52.79%, respectively, in terms of average request completion time, but also achieves a better fairness performance than these two counterparts.
Quantum Data Networks (QDNs) have emerged as a promising framework in the field of information processing and transmission, harnessing the principles of quantum mechanics. QDNs utilize a quantum teleportation technique through long-distance entanglement connections, encoding data information in quantum bits (qubits). Despite being a cornerstone in various quantum applications, quantum entanglement encounters challenges in establishing connections over extended distances due to probabilistic processes influenced by factors like optical fiber losses. The creation of long-distance entanglement connections between quantum computers involves multiple entanglement links and entanglement swapping techniques through successive quantum nodes, including quantum computers and quantum repeaters, necessitating optimal path selection and qubit allocation. Current research predominantly assumes known success rates of entanglement links between neighboring quantum nodes and overlooks potential network attackers. This paper addresses the online challenge of optimal path selection and qubit allocation, aiming to learn the best strategy for achieving the highest success rate of entanglement connections between two chosen quantum computers without prior knowledge of the success rate and in the presence of a QDN attacker. The proposed approach is based on multi-armed bandits, specifically adversarial group neural bandits, which treat each path as a group and view qubit allocation as arm selection. Our contributions encompass formulating an online adversarial optimization problem, introducing the EXPNeuralUCB bandits algorithm with theoretical performance guarantees, and conducting comprehensive simulations to showcase its superiority over established advanced algorithms.
Distributed quantum computing (DQC) connects multiple quantum processing units (QPUs) via quantum interconnects to overcome the qubit-count and connectivity limitations of individual devices. A critical challenge in this paradigm is routing entanglement resources efficiently across the quantum interconnect network so that inter-QPU quantum gates can be executed with high fidelity and minimal resource waste. We propose the Entanglement-Aware Adaptive Routing (EAAR) framework, which jointly optimizes path selection, entanglement purification scheduling, and congestion-aware load balancing for DQC workloads. EAAR models the quantum network as a fidelity-weighted directed graph and transforms the maximum-fidelity path problem into an additive shortest-path problem. An adaptive purification scheduler targets bottleneck links when end-to-end fidelity falls below application-defined thresholds, and a dynamic congestion penalty steers traffic away from over-utilized entanglement buffers. We evaluate EAAR in simulation across grid, ring, random-regular, and small-world topologies ranging from 4 to 24 QPU nodes. Results demonstrate that EAAR improves average remote-gate fidelity by up to 10.3% and reduces entanglement consumption by up to 44.8% compared to greedy baselines, while maintaining competitive latency with shortest-path routing. These findings confirm that holistic, entanglement-aware routing is essential for practical, high-fidelity distributed quantum computation.
Present quantum computers are constrained by limited qubit capacity and restricted physical connectivity, leading to challenges in large-scale quantum computations. Distributing quantum computations across a network of quantum computers is a promising way to circumvent these challenges and facilitate large quantum computations. However, distributed quantum computations require entanglements (to execute remote gates) which can incur significant generation latency and, thus, lead to decoherence of qubits. In this work, we consider the problem of distributing quantum circuits across a quantum network to minimize the execution time. The problem entails mapping the circuit qubits to network memories, including within each computer since limited connectivity within computers can affect the circuit execution time. We provide two-step solutions for the above problem: In the first step, we allocate qubits to memories to minimize the estimated execution time; for this step, we design an efficient algorithm based on an approximation algorithm for the max-quadratic-assignment problem. In the second step, we determine an efficient execution scheme, including generating required entanglements with minimum latency under the network resource and decoherence constraints; for this step, we develop two algorithms with appropriate performance guarantees under certain settings or assumptions. We consider multiple protocols for executing remote gates, viz., telegates and cat-entanglements. With extensive simulations over NetSquid, a quantum network simulator, we demonstrate the effectiveness of our developed techniques and show that they outperform a scheme based on prior work by 40 to 50% on average and up to 95% in some cases.
Quantum Information networks (QIN) aim to interconnect quantum systems via quantum repeaters through end-to-end entanglement of qubits. The integration of both satellites and ground segments is essential to provide global connectivity, even over large distances. In this paper, we study the problem of entanglement routing in large-scale quantum networks -i.e., with a large number of nodes, with a hybrid space-ground architecture. We decompose the routing problem into two subcomponents: request scheduling and path selection, and structure our approach around two phases: a proactive and a reactive step. We design and implement an entanglement routing strategy in an emulated European quantum network, first in a custom Python-based simulator for performance forecasting, and then into the NetSquid quantum network simulator. Our work thus provides a tool allowing for a comparison between terrestrial and satellite segments in terms of successful end-to-end entanglement in a large-scale network and shows that both segments are required for optimal service. Our results indicate that, within the emulated European topology, terrestrial networks can support end-toend entanglement for approximately 35% of user pairs -the remaining pairs are too distant and suffer from prohibitive losses. In contrast, the satellite-based network achieves connectivity for up to 91% of user pairs, although some pairs remain unreachable due to a lack of simultaneous satellite visibility. However, while satellites can outperform terrestrial networks in total photon distribution, they may not be suitable for lowlatency requests if out of visibility, making ground networks essential. This highlights the complementary roles of space and terrestrial segments in quantum networking.
The quantum internet holds transformative potential for global communication by harnessing the principles of quantum information processing. Despite significant advancements in quantum communication technologies, the efficient distribution of critical resources, such as qubits, remains a persistent and unresolved challenge. Conventional approaches often fall short of achieving optimal resource allocation, underscoring the necessity for more effective solutions. This study proposes a novel reinforcement learning-based adaptive entanglement routing framework designed to enable resource allocation tailored to the specific demands of quantum applications. The introduced QuDQN model utilizes reinforcement learning to optimize the management of quantum networks, allocate resources efficiently, and enhance entanglement routing. The model integrates key considerations, including fidelity requirements, network topology, qubit capacity, and request demands.