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

• Inter-node communication is costly because each communication consumes an EPR pair, whose generation and maintenance are error-prone.Compilation techniques including burst and collective communication have been investigated to improve communication efficiency.Source: §1 · p. 1
• QuComm reduces EPR consumption by dividing a circuit into collective communication blocks and optimizing routing within each block.It is identified as a seminal collective communication approach.Source: §1 · p. 1
• DPRQ achieves an average 24.40% reduction and a maximum 85.06% reduction in inter-node communication compared with the baseline.The paper evaluates the approach against the state-of-the-art baseline and reports these reductions.Source: §1 · p. 1
• DPRQ uses dynamic programming to optimize qubit routing across an entire DQC circuit while retaining collective communication blocks.Its framework targets EPR costs, and the evaluation covers four sets of quantum circuits and varied configurations.Source: §1 · pp. 1–2

2.1 Qubits, Qubit Layout and TP-Comm

• TP-Comm transfers a qubit between nodes using one EPR pair, changing the network’s qubit layout; layouts map logical qubits to their current nodes.Communication qubits establish remote entanglement, while data qubits store program information.Source: §2.1 · p. 2

2.2 Collective Communication for DQC

• A collective communication block groups inter-node gates whose qubit interaction graph is connected across multiple nodes.Executing the gates collectively at a common node can reduce inter-node communication.Source: §2.2 · p. 2

2.3 Communication Fusion

• Communication fusion inspects the circuit for collective communication opportunities and partitions its gates into blocks.Starting with the first non-local gate, it adds overlapping gates when the estimated routing cost does not increase for non-local gates or implementation cost remains unchanged for local gates; unmerged local gates form individual blocks.Source: §2.3 · p. 2
• The fusion cost estimate accounts for node EPR capacity and the qubits outside an aggregator node involved in the blocks.When those qubits exceed the node’s EPR capacity, additional transfers require inter-node SWAPs using two TP-Comm invocations.Source: §2.3 · p. 2

3.1 Intra-block Communication Cost

• Each block selects an aggregator and teleports its involved qubits there for local execution of inter-node gates.DPRQ evaluates transfer paths using a cost of one when communication qubits are available and two otherwise; it can favor shortest paths that permit early gate execution at intermediate nodes.Source: §3.1 · pp. 2–3

3.2 DP-based Inter-block Qubit Routing

• For each aggregator choice, DPRQ minimizes cumulative communication cost across preceding blocks using their resulting qubit layouts.It considers all previous aggregator nodes but retains one best final layout per block–aggregator pair; storing multiple layouts is left for future work because of its significant time and space cost.Source: §3.2 · p. 3

3.3 Scalability Analysis

• DPRQ’s worst-case time complexity is O(|Z|·(P^2|N|^3+P|N|^4+|N|^3Y)).P, the maximum number of shortest paths between two nodes, may be exponential in richly connected large networks; the authors describe the complexity as manageable for near-term networks and suggest heuristic path selection for future large-scale networks.Source: §3.3 · p. 4

4.1 Experimental Setup

• Experiments use mesh-grid networks with nearest-neighbor links and constant communication channels, without assumptions about intra-node qubit topology.Source: §4.1 · p. 4
• The benchmarks are BV, RCA, fixed linear-entanglement VQE, and 10-edge random-graph QAOA; each QAOA configuration uses 10 runs and a 95% confidence interval.Source: §4.1 · p. 4

4.2 Baseline, Evaluation Parameters and Evaluation Metric

• QuComm is the baseline with reproduced fusion preprocessing; default settings are EPR capacity 3, 150 data qubits, and 20 per node, with EPR-pair use as the primary metric.Source: §4.2 · p. 4

4.3 Effect of Circuit Parameters

• Across varying EPR capacities, DPRQ achieves lower routing costs on all four benchmark circuits.For BV, sequential transfer avoids redundant communication; for VQE and RCA, adaptive routing keeps EPR use near-constant.Source: §4.3 · p. 4, Figure 1 · p. 5
• QuComm adapts less to EPR-capacity changes because it lacks a global view of inter-block correlations, leading to inefficient routing and higher communication costs.Source: §4.3 · pp. 4–5
• With circuit width varied, DPRQ reduces inter-node communication more than QuComm across all four circuits; RCA and VQE parity lasts only up to five nodes.QuComm's advantage disappears as the network expands.Source: §4.3 · p. 5, Figure 2 · p. 5
• With fewer data qubits per node, DPRQ's advantage grows; with more per node, fewer collective blocks reduce the importance of dynamic programming.The reported advantage also increases with the number of nodes.Source: §4.3 · p. 5, Figure 3 · p. 5

4.4 Effect of Network Topologies

• Across mesh-grid, ring, and fully connected topologies, DPRQ performs at least as well as QuComm on all four circuits; its benefit diminishes in fully connected networks.Every node's direct link to every other node reduces the importance of improved aggregator-node selection.Source: §4.4 · pp. 5–6

5 Conclusion

• DPRQ uses dynamic programming to search initial qubit layouts and combines intra-block with inter-block routing to reduce inter-node communication.Its layout search addresses the strong dependence of within-block communication on the initial qubit layout.Source: §5 · p. 6
• DPRQ’s communication-reduction advantage grows as node count increases, and its results remain resilient to changes in collective-block patterns and network topologies.Source: §5 · p. 6
• 24.40% average and 85.06% maximum EPR-cost reductions versus QuComm across 80 configurations; DPRQ’s maximum average reduction across four benchmark circuits was 48.54% for a single circuit configuration.The discussed configuration used 200 qubits, 20 qubits per node, and EPR capacity 2.Source: §5 · p. 6