DPRQ: A Dynamic Programming-based Qubit Routing Algorithm for Collective Communication in Distributed Quantum Computing

• URL: http://arxiv.org/abs/2609.04524v2
• Date: Tue, 08 Sep 2026 02:15:47 GMT
• Title: DPRQ: A Dynamic Programming-based Qubit Routing Algorithm for Collective Communication in Distributed Quantum Computing
• Abstract summary: Inter-node communication remains a major bottleneck of Distributed quantum computing.<n>This paper proposes DPRQ, a qubit routing algorithm for minimizing inter-node communication in quantum circuits divided into collective communication blocks.
• Score: 4.8266328158580665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributed quantum computing (DQC) offers a promising approach to scale quantum computing by overcoming the resource limitations of a single quantum processor. However, inter-node communication remains a major bottleneck of DQC due to inefficient and error-prone entanglement distribution. Optimizing inter-node communication can not only reduce the amount of entanglement resource needed to execute a quantum circuit but also improve execution speed and accuracy of the results. This paper proposes DPRQ, a qubit routing algorithm for minimizing inter-node communication in distributed quantum circuits divided into collective communication blocks. Unlike current approaches that utilize greedy block-level qubit routing strategies, DPRQ employs a dynamic programming-based technique focused on global circuit-level optimization, while capturing inter-block dependencies. We evaluated DPRQ on four sets of quantum circuits and a variety of DQC configurations. The results demonstrate that DPRQ's innovative routing strategy achieves an average of 24.40% reduction with a maximum of 85.06% reduction in inter-node communication, when compared to the state-of-the-art collective communication-based DQC compiler QuComm.

Related papers

• Performance Analysis of QAOA Across Distributed Quantum Network Topologies Using SwitchQNet [0.32622301272834514]
  We study the Quantum Approximate Optimization Algorithm (QAOA) as a graph-structured optimization workload for QDC-based quantum computing.<n>We adapt QAOA to SwitchQNet, a distributed quantum compiler framework that schedules communication and entanglement generation over switch-based QDC networks.<n>We evaluate QAOA instances across Clos, fat-tree, and spine-leaf topologies, measuring communication latency, EPR-pair overhead, EPR wait time, retry overhead, and sensitivity to buffer size.
  arXiv  Detail & Related papers  (2026-07-26T01:45:57Z)
• Minimizing Quantized Semantic Age of Information (QSAoI) in Foundation Model-Based Semantic Communications [42.856220919076556]
  We introduce the Quantized Semantic Age of Information (QSAoI), a novel metric that rigorously captures the trade-offs among freshness and semantic efficiency of high-level features in real-time communication.<n>We propose a novel foundation model-based efficient co-designed framework to minimize the expected QSAoI over wireless fading channels in latency-constrained semantic communication.
  arXiv  Detail & Related papers  (2026-06-30T08:16:15Z)
• UNIQ: Communication-Efficient Distributed Quantum Computing via Unified Nonlinear Integer Programming [29.635486335639524]
  Distributed quantum computing (DQC) is widely regarded as a promising approach to overcome quantum hardware limitations.<n>Existing DQC approaches treat the three essential components (qubit allocation, entanglement management, and network scheduling) as independent stages, optimizing each in isolation.<n>We propose UNIQ, a novel DQC optimization framework that integrates all three components into a non-linear integer programming (NIP) model.
  arXiv  Detail & Related papers  (2025-11-29T09:07:36Z)
• Circuit Partitioning for the Quantum Internet [3.8516680239451744]
  In a quantum internet, quantum processing units (QPUs) with varying architectures and capabilities may be connected through quantum communication channels.<n>Remote operations between QPUs are expensive as they require the creation and distribution of entanglement throughout the network.<n>It is therefore crucial to assign qubits to QPUs and partition circuits in such a way that the overall communication between QPUs is minimized.
  arXiv  Detail & Related papers  (2025-09-17T20:28:36Z)
• Solving Drone Routing Problems with Quantum Computing: A Hybrid Approach Combining Quantum Annealing and Gate-Based Paradigms [34.4581898633922]
  The proposed method, coined Quantum for Drone Routing (Q4DR), integrates the two most prominent paradigms in the field.<n>The efficacy of Q4DR is demonstrated through three use cases of increasing complexity.
  arXiv  Detail & Related papers  (2025-01-30T15:38:40Z)
• SPARQ: Efficient Entanglement Distribution and Routing in Space-Air-Ground Quantum Networks [50.91365514137301]
  Space-air-ground quantum (SPARQ) network is developed as a means for providing a seamless on-demand entanglement distribution. Deep reinforcement learning framework is proposed and trained using deep Q-network (DQN) on multiple graphs of SPARQ. Third-party entanglement distribution policy is proposed to establish entanglement between communication parties.
  arXiv  Detail & Related papers  (2024-09-19T16:31:37Z)
• Resource Management and Circuit Scheduling for Distributed Quantum Computing Interconnect Networks [5.239117416189216]
  Distributed quantum computing (DQC) has emerged as a promising approach to overcome the scalability limitations of monolithic quantum processors.<n>This paper addresses resource management and circuit scheduling in such settings.<n>We propose circuit scheduling algorithms based on Mixed-Integer Linear Programming (MILP)
  arXiv  Detail & Related papers  (2024-09-19T11:39:46Z)
• Scalable Multivariate Fronthaul Quantization for Cell-Free Massive MIMO [36.0373787740205]
  This work sets out to design scalable MQ strategies for PC-based cell-free massive MIMO systems. For the low-fronthaul capacity regime, we present alpha-parallel MQ (alpha-PMQ), whose complexity is exponential only in the fronthaul capacity towards an individual RU. For the high-fronthaul capacity regime, we then introduce neural MQ, which replaces the exhaustive search in MQ with gradient-based updates for a neural-network-based decoder.
  arXiv  Detail & Related papers  (2024-08-26T12:56:41Z)
• Compiler for Distributed Quantum Computing: a Reinforcement Learning Approach [6.347685922582191]
  We introduce a novel compiler that prioritizes reducing the expected execution time by jointly managing the generation and routing of EPR pairs. We present a real-time, adaptive approach to compiler design, accounting for the nature of entanglement generation and the operational demands of quantum circuits. Our contributions are twofold: (i) we model the optimal compiler for DQC using a Markov Decision Process (MDP) formulation, establishing the existence of an optimal algorithm, and (ii) we introduce a constrained Reinforcement Learning (RL) method to approximate this optimal compiler.
  arXiv  Detail & Related papers  (2024-04-25T23:03:20Z)
• Elastic Entangled Pair and Qubit Resource Management in Quantum Cloud Computing [73.7522199491117]
  Quantum cloud computing (QCC) offers a promising approach to efficiently provide quantum computing resources. The fluctuations in user demand and quantum circuit requirements are challenging for efficient resource provisioning. We propose a resource allocation model to provision quantum computing and networking resources.
  arXiv  Detail & Related papers  (2023-07-25T00:38:46Z)
• Multi-User Entanglement Distribution in Quantum Networks Using Multipath Routing [55.2480439325792]
  We propose three protocols that increase the entanglement rate of multi-user applications by leveraging multipath routing. The protocols are evaluated on quantum networks with NISQ constraints, including limited quantum memories and probabilistic entanglement generation.
  arXiv  Detail & Related papers  (2023-03-06T18:06:00Z)
• AutoComm: A Framework for Enabling Efficient Communication in Distributed Quantum Programs [15.05397810840915]
  Non-local quantum communication between quantum devices is much more expensive and error-prone than the local quantum communication within each quantum device. In this paper, we identify burst communication, a specific qubit-node communication pattern that widely exists in many distributed programs. We then propose AutoComm, an automatic compiler framework to first extract the burst communication patterns from the input programs, and then optimize the communication steps of burst communication discovered.
  arXiv  Detail & Related papers  (2022-07-24T06:49:58Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  Internet-of-things, networked sensing, autonomous systems and federated learning call for decentralized algorithms for finite-sum optimizations. We develop DEcentralized STochastic REcurSive methodDESTRESS for non finite-sum optimization. Detailed theoretical and numerical comparisons show that DESTRESS improves upon prior decentralized algorithms.
  arXiv  Detail & Related papers  (2021-10-04T03:17:41Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.