CS Paper Radar

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

Dhaval Vaidya, Ruozhou Yu

cs.DC quant-ph ·submitted 2026-09-03 22:28 UTC · v2
published

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.

Comment
6 pages, 4 figures
Journal ref
Proc. 3rd ACM SIGCOMM Workshop on Quantum Networks and Distributed Quantum Computing (QuNet' 26), 2026, pp. 68-73
DOI
10.1145/3833409.3833449

Closest papers

Nearest neighbours by meaning across the whole index.

Towards Reproducible Evaluation of Distributed Quantum Circuit Partitioning Algorithms

cs.DC quant-ph ·2026-08-27 ·Javier Vela-Tambo, Davud Azizov, Tian Guo
code/data similarity 0.77
Abstract · Accepted at IEEE QCE 2026 Workshop: Distributed Quantum Computing Systems and Infrastructure

Distributed Quantum Computing (DQC) addresses the physical scaling limitations of monolithic quantum processors by networking modular Quantum Processing Units (QPUs). Efficient execution of quantum algorithms on DQC architectures requires compiling them across QPUs while minimizing inter-QPU communication bottlenecks, primarily through circuit partitioning. However, current evaluations of state-of-the-art partitioning heuristics focus primarily on the total entanglement cost of the partitions, failing to capture the broader structural and temporal overheads introduced by distributed network constraints. This paper addresses this evaluation gap by applying established monolithic benchmarking metrics to partitioned distributed circuits to quantify the performance impact of network constraints. Using an open-source, automated evaluation pipeline, we systematically assess diverse partitioning algorithms across standardized workloads and quantum network topologies. Our empirical results reveal that partitioning algorithms with comparable entanglement costs can still introduce drastically different physical execution penalties. By exposing these hidden trade-offs, such as severe increases in circuit depth and substantial reductions in gate density, this study demonstrates that comprehensive circuit-level metrics are essential for guiding the future design of DQC compilers.

0.21

Communication-Aware Qubit Placement and Automatic Node-Count Allocation for Distributed State-Vector Simulation

cs.DC cs.ET ·2026-10-07 ·Íñigo Aréjula-Aísa, Sergio Iserte, Petter Sandås, Ricard S. Raigada-García, Antonio J. Peña
similarity 0.74
Abstract

Quantum circuit simulation enables the execution of large-scale quantum algorithms by partitioning qubits across multiple computational nodes. However, an inefficient qubit placement leads to excessive inter-node communication, limiting performance and scalability. This work introduces a framework that computes a communication-aware qubit placement offline, minimizing data exchange among nodes, and selects, before circuit execution, the largest node count whose performance degradation stays below a user-defined threshold. The framework is integrated with the QuEST simulator. Evaluations on synthetic benchmarks and real-world QASMBench circuits show that optimized placements reduce communication and achieve runtime speedups of up to 2.3x over the identity placement, particularly in circuits with sparse, structured interactions. Our results show that qubit placement strongly affects the efficiency of distributed simulation and provide a practical, resource-scalable solution for quantum workload

0.30

Scalable Transpilation for Overcoming Restricted Connectivity in Distributed Superconducting Quantum Architectures

cs.ET quant-ph ·2026-11-04 ·Afonso Azenha, Ilia Polian, Sebastian Brandhofer
published similarity 0.73
Abstract · 11 pages, 3 figures. Accepted at the 2026 IEEE International Conference on Quantum Computing and Engineering (QCE)

Distributed Quantum Computing (DQC) offers a promising pathway to scale superconducting quantum hardware, but restricted inter- and intra-module connectivity creates a major transpilation bottleneck. Current DQC transpilation methods often assume idealized hardware connectivity, ignore subsequent intra-module routing, or suffer from substantial computational overheads that limit their applicability at scale. To address this, we introduce a scalable transpilation method tailored for the restricted connectivity of distributed superconducting quantum architectures. Specifically, our quantum interaction graph (QIG) approach couples a graph-partitioning mapping step with a fast SABRE-inspired routing heuristic. On a 48-qubit (3 QPUs $\times$ 16 qubits) architecture with all-to-all inter-core connectivity, our method reduces average aggregated costs by up to 24.72% (unstructured) and 24.01% (structured), while delivering >250$\times$ speed-ups for structured workloads compared to the state-of-the-art DMapS algorithm. On the 399-qubit (3$\times$133) IBM Flamingo, where DMapS times out on dense circuits, our approach maintains practical runtimes. Against a DQC-adapted SABRE baseline, it reduces structured circuit routing costs by up to 51.94% (all-to-all inter-core topology) and 51.96% (restricted line topology). Ultimately, this work delivers a practical transpilation method for DQC at scale.

0.20

Resource-Aware Scheduling for Distributed Quantum Computing

cs.NI ·2026-10-21 ·Connor Howe, Raghav Mundada, Jake O'Shaughnessy, Ibrahim Abdullahi, Ali Anwar
similarity 0.72
Abstract

Distributed quantum computing (DQC) is a promising near-term approach for executing circuits that exceed the capacity of a single quantum processing unit (QPU). Prior work has made significant progress on circuit partitioning and reconstruction, but practical DQC requires more than cutting a circuit into smaller pieces. A runtime system must determine whether to execute the circuit intact, cut it for sequential execution on one QPU, or distribute it across multiple QPUs, while accounting for queueing, communication, reconstruction, and hardware constraints. We present a resource-aware scheduler for DQC that compares these execution alternatives at runtime using explicit models of QPU execution, communication, and host-side reconstruction, together with hardware-informed timing derived from simulated IBM QPUs. By treating communication and reconstruction as first-class scheduling costs, the scheduler selects execution plans using a more realistic view of end-to-end overhead than cutting-only approaches. Across our experiments, reconstruction accounts for over 83% of cutting overhead, distributed execution reduces P90 latency by up to 39% relative to uncut single-QPU execution, and scheduling overhead itself remains negligible, never exceeding 0.038% of end-to-end job latency. Together, these results show that DQC must be treated as a runtime scheduling problem over both quantum and classical resources, not just circuit partitioning.

0.15

Spatio-temporal Path Optimization for Stabilizer-Code-Protected Quantum Networks

cs.NI ·2026-08-24 ·Yuanbo Zhang, Qianfan Wang, Yangming Zhao, Lin Chen, Deke Guo
similarity 0.71
Abstract · ICNP 2026 extended version

Quantum Error Correction~(QEC)-protected direct transmission is a fundamental approach to preserve fragile quantum states while they are physically forwarded across noisy quantum networks. When a logical qubit traverses multiple hops, selected QEC-capable nodes may recover the encoded state before it continues along the route. The feasibility and cost of the final transmission strategy therefore depend on how we jointly choose the path, the recovery locations, and the protection schemes. In this paper, we formulate and analyze a cross-layer spatio-temporal path optimization problem for block-style stabilizer-code-protected direct transmission. Our main results include fixed-scheme and flexible-scheme single-flow routing algorithms, as well as a multi-flow routing algorithm. The framework developed in this paper can serve as an algorithmic building block for QEC-aware routing under logical-error and logical-lifetime constraints. Simulations show that it reduces single-flow average routing cost by approximately 25--30\% over Decode-Always and lowers multi-flow throughput-normalized congestion by approximately 28--31\% over Greedy-Assignment.

0.17

Online Scheduling and Distribution of Quantum Circuits over Quantum Networks

cs.ET quant-ph ·2026-10-19 ·Yukun Yang, Himanshu Gupta
published similarity 0.69
Abstract · 8 pages, 5 figures. Full author version revised after acceptance; the QCNC 2026 version was shortened to meet the conference page limit

Emerging quantum networks enable distributed quantum computing (DQC) by interconnecting modest, noisy quantum processors. However, practical deployments face tight memory budgets, probabilistic entanglement generation, and decoherence, all while serving multiple users. In realistic settings -- cloud execution, iterative/interactive workloads and concurrent jobs -- circuits do not arrive in a single batch but as a stream. This creates a fundamentally online problem: the system must react to stochastic arrivals, balance latency and throughput, and remain stable under varying loads without foresight of future jobs. We study Online Scheduling and Distribution of Quantum Circuits (OS-DQC) and formalize the online scheduling problem for quantum networks: circuits arrive over time and must be executed without knowledge of future arrivals. At each event time (arrival or completion), the system decides which waiting circuits to launch and how to place their qubits, while accounting for congestion from in-flight circuits and constraints due to finite memories and decoherence. The objective is to minimize the mean completion time and makespan under these physical and resource constraints.

0.33

Distributing Quantum Circuits Using Pre-Distributed Entanglement Pairs over Quantum Networks

cs.ET quant-ph ·2026-10-19 ·Yukun Yang, Ranjani G. Sundaram, Himanshu Gupta
publishedbenchmark similarity 0.68
Abstract · 9 pages, 4 figures. Full author version revised after acceptance; includes the cost-aware entanglement consumption section omitted from the …

Distributing quantum circuits across a network of quantum devices is a recent approach to improve the scalability of quantum computation. Entangled pairs of qubits distributed across network nodes are used as a communication resource for executing inter-node (remote) gates. However, establishing these entanglement pairs incurs significant latency, and doing so during the circuit's execution may lead to the decoherence of logical qubits. Instead, it may be beneficial to distribute certain entanglement pairs before the circuit is executed. Thus, we consider the problem of distributing a quantum circuit across a quantum network containing some pre-distributed entanglement pairs and seek to minimize the execution time of the circuit. We address this problem in three steps. First, given the quantum network and (optionally) a probability distribution over training circuits, we determine a set of pre-distributed entanglement pairs under a specified budget. Second, we compute a qubit-to-memory allocation that minimizes the expected execution time given these pre-distributed resources. Finally, we identify any additional entanglement pairs required during execution, generate them concurrently, and execute the circuit gates. We evaluate our methods on a broad range of benchmark circuits.

0.46

Quantum Broker: QoS-Aware Distribution of Quantum Computations

cs.ET quant-phcs.SE ·2026-10-20 ·Giuseppe Bisicchia, Alessandro Bocci, Jose Garcia-Alonso, Juan Manuel Murillo, Antonio Brogi
benchmarkcode/data similarity 0.67
Abstract · 32 pages

Cloud-accessible quantum computing has made heterogeneous Quantum Processing Units (QPUs) available through provider platforms that differ in qubit technology, calibration state, queueing behavior, and pricing model. This heterogeneity makes execution management a quantum-engineering concern: a quantum circuit may be executable on several backends, but the resulting cost, latency, fidelity, and reproducibility depend on backend selection and on how measurement shots are allocated. This paper presents the Quantum Broker, an open-source and provider-agnostic framework for Quality-of-Service-aware quantum execution management. The framework operationalizes shot-wise distribution by exploiting the statistical independence of quantum measurement shots to dispatch a single circuit across multiple heterogeneous QPUs according to user-defined constraints and optimization objectives. It combines a modular execution architecture, interchangeable backend-profiling strategies, and the Quantum QoS Specification Language (QQSpec), a declarative language for expressing QoS requirements. Dispatch planning is supported by two solver backends: a mixed-integer linear-programming (MILP) solver, and a nonlinear dual-annealing solver. Experiments on benchmark quantum circuits and noisy simulator backends show that the Quantum Broker can produce feasible QoS-aware dispatch plans under heterogeneous backend conditions and can improve QoS satisfaction with respect to single-backend and naive multi-backend baselines. The results also expose a practical trade-off between planning time and dispatch quality, with the nonlinear solver producing higher-quality allocations at increased computational cost. Overall, the Quantum Broker provides an extensible execution-management layer for engineering portable, reproducible, and QoS-aware quantum software over fragmented quantum cloud infrastructures.

0.24