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

AI summary

Overview

Research area: Distributed quantum computing (DQC), specifically circuit compilation and qubit routing for inter-node communication.

Technical level: Intermediate. The paper assumes familiarity with EPR pairs, quantum teleportation, collective communication blocks, and dynamic programming, but its core idea is explained through a small set of routing cost rules.

Scope: The paper introduces DPRQ, a dynamic-programming-based qubit routing algorithm that minimizes the number of EPR pairs consumed by inter-node communication in DQC circuits partitioned into collective communication blocks, and benchmarks it against the QuComm compiler on four circuits across multiple network configurations.

What This Paper Is About

Distributed quantum computing connects several quantum processors so that a circuit can use more qubits than any single processor holds, but every inter-node gate requires scarce, error-prone entangled (EPR) pairs. The state-of-the-art compiler QuComm reduces this cost by grouping inter-node gates into "collective communication blocks" and routing qubits within each block, but it decides each block greedily and ignores how one block's routing affects the next. DPRQ replaces that greedy step with a dynamic programming formulation that optimizes routing across the whole circuit while tracking inter-block dependencies.

Key Contributions

1. A circuit-level routing framework for collective communication. DPRQ retains QuComm's communication fusion stage for forming collective communication blocks, but replaces block-local greedy routing with a routing strategy aimed at minimizing EPR cost over the entire DQC circuit.

2. An intra-block cost procedure with early execution. Algorithm 1 (IntraBlockRouting) selects an aggregator node and teleports the block's qubits to it, evaluating shortest paths between nodes, exploiting common intermediate nodes on multiple shortest paths for early execution, and charging 1 EPR pair when a communication qubit is available versus 2 when an inter-node SWAP is needed.

3. A dynamic programming formulation over aggregator nodes. A cost matrix C(b_k, n_k) is computed as the minimum over all aggregator choices n_{k-1} in the previous block of C(b_{k-1}, n_{k-1}) + T(b_k, n_{k-1}, n_k), with a companion layout matrix L(b_k, n_k) recording the resulting qubit layout; the circuit's final cost is the minimum of C over all nodes for the last block.

4. An empirical comparison against QuComm. DPRQ was evaluated on four benchmark circuits over 80 different configurations, including sweeps of EPR capacity, total qubit count, qubits per node, and three network topologies.

Main Findings

• Overall reduction versus QuComm: Across 80 configurations of the four benchmarks, DPRQ achieves an average reduction of 24.40% and a maximum reduction of 85.06% in EPR cost compared with the state-of-the-art collective-communication-based DQC compiler QuComm.

• Best single configuration: For one circuit configuration, DPRQ offers a maximum average reduction of 48.54% across the four benchmark circuits; that configuration is 200 qubits, 20 qubits per node, and EPR capacity 2.

• Stability under EPR capacity: As EPR capacity increases from 1 to 5 (150 total qubits, 20 qubits per node), DPRQ consistently has lower routing cost than QuComm on all four circuits. DPRQ executes the BV circuit at constant cost, and executes VQE and RCA with a near-constant number of EPR pairs; QuComm adapts less to EPR capacity changes.

• Scaling with circuit width: As total qubits increase from 50 to 200 (EPR capacity 3, 20 qubits per node), DPRQ reduces inter-node communication substantially more than QuComm on all four circuits. For RCA and VQE, QuComm performs comparably when the network has at most five nodes, but that advantage disappears as the network expands.

• Effect of qubits per node: As qubits per node increase from 10 to 40 (EPR capacity 3, 150 total qubits), many collective communication blocks are no longer needed and the value of the dynamic programming approach diminishes; DPRQ's advantage grows for fewer qubits per node, i.e., more nodes.

• Topology resilience: On mesh-grid, ring, and fully-connected topologies with the default parameters, DPRQ performs better than or equal to QuComm on all four circuits, and QuComm never outperforms DPRQ. The benefit of DPRQ diminishes on a fully-connected network because direct links between every pair of nodes reduce the importance of aggregator-node selection.

• Confidence intervals: For QAOA, a 95% confidence interval is reported based on 10 runs per configuration; the other circuits are deterministic in the reported results.

Methodology in Plain English

The circuit is first preprocessed exactly as in QuComm: gates are scanned in order, and non-local gates are merged into a collective communication block as long as an estimated cost formula does not increase; when no more gates can be merged, a new block starts. Any local gates left over become their own blocks so that every gate is assigned.

For each block, the algorithm must pick an "aggregator" node where the block's inter-node gates will actually be executed, then teleport the involved qubits there. The cost of that transfer depends on which node is chosen and on which paths the qubits take. DPRQ walks through the block's two-qubit gates one at a time, finds all shortest paths from each qubit's current node toward the intended aggregator, and looks for nodes shared by those paths where a gate can be executed early. For each candidate node it prices the transfer step by step: one EPR pair if a communication qubit is free at that hop, two if a qubit must be swapped out instead. The cheapest candidate is chosen, both qubits are moved there, and the qubit layout is updated. This procedure produces, for a given block and aggregator node, both a cost and a resulting layout.

The dynamic programming step then chains blocks together. For block k and each possible aggregator node n_k, the algorithm looks back at every possible aggregator node n_{k-1} of block k-1, adds the already-computed optimal cost for that earlier choice to the cost of routing block k starting from the layout that earlier choice produced, and keeps the minimum. The layout associated with that minimum is stored, so the next block starts from the best layout found. The final answer is the minimum cost over all aggregator nodes for the last block.

The authors analyze the worst-case time complexity as O(|Z|·(P²|N|³ + P|N|⁴ + |N|³Y)), where |Z| is the number of two-qubit gates, |N| the number of nodes, Y the number of links, and P the maximum number of shortest paths between two nodes. They note that P may be exponential in network size but that the complexity is manageable for near-term quantum networks, and that heuristic rules could restrict paths to a polynomial subset in future large networks.

Experiments were run in Python 3.12.8 on Windows 11 with 8 CPU cores and 16 GB RAM, using a mesh-grid topology by default with nearest-neighbor-only communication and a constant channel between neighbors. Default parameters are EPR capacity 3, 150 data qubits, and 20 data qubits per node; the paper describes this as 150 qubits distributed over 8 compute nodes, and states that the number of nodes equals total data qubits divided by qubits per node. Logical qubits are assigned to fill node A first, then B, C, and so on, with the same assignment used for the baseline. The four benchmarks are Bernstein-Vazirani with an all-ones secret string, a Ripple-Carry Adder decomposed into Clifford+T, a fixed EfficientSU2 ansatz for VQE with linear entanglement, and QAOA using a Maxcut ansatz on a random graph with 10 edges; BV, RCA, and QAOA come from the open-source AutoComm implementation, and VQE from IBM Qiskit. The baseline is a reproduction of QuComm's communication fusion and communication routing stages (the communication buffer design stage is omitted as orthogonal), using TP-Comm only for both DPRQ and the reproduced baseline, with Cat-Comm excluded for consistency. The performance metric is the number of EPR pairs, i.e., the number of TP-Comm invocations.

Why This Matters

Inter-node communication is the dominant cost and error source in distributed quantum computing, so reducing EPR consumption directly affects how large a computation a multi-node system can run, how fast it runs, and how accurate the result is. DPRQ shows that treating routing as a global optimization rather than a per-block greedy decision yields large savings, and that the savings grow as the number of nodes increases — the regime DQC is meant to serve. The paper reports no wall-clock runtime measurements, so the practical compile-time overhead of the dynamic program is not quantified.

Real-world applications of the benchmark circuits and setting:

• Arithmetic circuits: Ripple-carry adders are building blocks of modular arithmetic used in Shor-style factoring and in cryptographic and numerical workloads, where DPRQ reduces the entanglement needed per addition.
• Quantum chemistry and materials simulation: VQE with the EfficientSU2 ansatz is a standard near-term approach for estimating molecular energies, a workload that benefits from distributing qubits across processors.
• Combinatorial optimization: QAOA on a Maxcut-style problem represents logistics, scheduling, and network-design tasks that map naturally to distributed hardware.
• Quantum algorithms with structured queries: The Bernstein-Vazirani circuit stands in for oracle-based algorithms where DPRQ achieves constant-cost routing.

Industry relevance: compilers like DPRQ matter to hardware vendors building modular or networked quantum processors, to cloud quantum providers that must schedule circuits across multiple nodes, and to quantum networking efforts where EPR generation is the limiting resource.

Future Directions

• Storing multiple layouts per block and aggregator node. The authors keep a single best final layout per (b_{k-1}, n_{k-1}) pair and explicitly leave exploration of multiple stored layouts as future work, citing space and time complexity.

• Extending beyond TP-Comm. DPRQ currently uses only TP-Comm; the authors state it can be extended to include Cat-Comm, which the original QuComm supports, and leave that for future work.

• Controlling path explosion in large networks. Because the number of shortest paths P may be exponential, the paper suggests defining heuristic rules to select a polynomial subset of paths, a standard practice in classical networks.

• Broader validation. The evaluation covers four circuits, 80 configurations, and three synthetic topologies with noiseless cost accounting; testing on larger circuits, additional topologies, and real hardware noise, plus reporting compilation runtime, would clarify practical deployment limits.

Target Audience

Graduate students and researchers in quantum compilation and quantum networking who already know the basics of DQC and EPR-based teleportation; compiler engineers at quantum hardware and cloud companies building multi-node execution stacks; and readers familiar with dynamic programming who want a concrete example of applying it to circuit-level resource optimization. Beginners will need background reading on collective communication and the QuComm baseline first.

Authors’ 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.