arXiv:2609.04524v1 [quant-ph] 3 Sep 2026
DPRQ: A Dynamic Programming-based Qubit Routing Algorithm for Collective Communication in Distributed Quantum Computing Dhaval Vaidya
Ruozhou Yu
[email protected] North Carolina State University Raleigh, North Carolina, USA
[email protected] North Carolina State University Raleigh, North Carolina, USA
Abstract
1
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.
In the NISQ era, quantum processors are erroneous and cannot accommodate enough qubits to be fully fault-tolerant. Distributed Quantum Computing (DQC) is the technique of using a network of multiple quantum processors to perform a task. It enhances the scalability of quantum computing by helping surpass the qubit capacity constraints of a single quantum processor. Different techniques of DQC are being investigated around the world, including those in hardware design [7, 12, 17, 18] as well as program-level compilation [1, 2, 4–6, 8, 9, 11, 13, 20–22]. In the general model of DQC [1, 2, 5, 6, 8, 9, 11, 13, 20–22], one EinsteinPodolsky-Rosen (EPR) pair is consumed to perform one inter-node communication. However, the error-prone nature of the generation and maintenance of EPR pairs makes it a scarce quantum resource and inter-node communication; an expensive process [17]. To increase the efficiency of inter-node communication, some approaches focus on reducing inter-node communication using innovative compiling techniques such as burst communication and collective communication [20, 21]. Among various approaches, collective communication is a novel approach to optimize inter-node communication, pioneered in the seminal work QuComm [20]. QuComm devises a strategy to optimize node-to-node communication by dividing a quantum circuit into collective communication blocks and optimizing the routing within each block to reduce EPR consumption. A major limitation of QuComm is the greedy routing mechanism of inter-node gates that solely considers routing optimization within each collective communication block, significantly limiting the reduction in EPR consumption across collective communication blocks. We present DPRQ, a dynamic programming-based qubit routing algorithm aimed at minimizing the number of EPR pairs required for inter-node communication in a collective communication setting. Retaining the logic of forming collective communication blocks as [20], DPRQ uses an innovative dynamic programmingbased approach to create a routing strategy that intends to minimize inter-node communication across an entire DQC circuit. The results demonstrate that DPRQ offers an average reduction of 24.40% in inter-node communication with a maximum reduction of 85.06% when compared to the baseline. The primary contributions of our paper are summarized as follows:
CCS Concepts • Networks → Network algorithms; • Theory of computation → Dynamic programming; Routing and network design problems.
Keywords Distributed Quantum Computing, Collective Communication, Qubit Routing Algorithm, Dynamic Programming ACM Reference Format: Dhaval Vaidya and Ruozhou Yu. 2026. DPRQ: A Dynamic Programmingbased Qubit Routing Algorithm for Collective Communication in Distributed Quantum Computing. In 3rd ACM SIGCOMM Workshop on Quantum Networks and Distributed Quantum Computing (QuNet ’26), August 17–21, 2026, Denver, CO, USA. ACM, New York, NY, USA, 6 pages. https://doi.org/10. 1145/3833409.3833449
This work is licensed under a Creative Commons Attribution 4.0 International License. QuNet ’26, Denver, CO, USA © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2892-1/2026/08 https://doi.org/10.1145/3833409.3833449
Introduction
• We create an intelligent qubit routing framework specifically aimed at reducing the EPR costs in a DQC circuit divided into collective communication blocks.
QuNet ’26, August 17–21, 2026, Denver, CO, USA
• We evaluate the algorithm against the state-of-the art baseline and prove its effectiveness in reducing inter-node communication. The remainder of this paper is structured as follows. In Section 2, we provide a comprehensive background of the types of qubits in a quantum processor, the TP-Comm quantum communication protocol, collective quantum communication, and the communication fusion stage of QuComm [20] where the circuit is divided into collective communication blocks. In Section 3, we introduce the technical innovation of DPRQ for efficient routing in a collective quantum communication setup. In Section 4, we evaluate DPRQ on four different quantum circuits and demonstrate the performance of DPRQ for a variety of different circuit configurations. In Section 5, we conclude the paper.
2 Background 2.1 Qubits, Qubit Layout and TP-Comm In a quantum processor, the physical qubits that can establish a remote entanglement are called communication qubits, whereas the physical qubits that store program information are known as data qubits. A communication qubit can be used to store program information; however, a data qubit cannot be used to establish a remote entanglement. Each node has a fixed number of communication qubits, which is known as the EPR capacity of the node [20]. Logical qubits are computational abstractions that represent qubits in a quantum circuit. At any given time 𝑡, the qubit layout describes the mapping of each logical qubit in the circuit to the corresponding node where that qubit currently occupies a physical qubit. The TP-Comm protocol uses quantum teleportation to transfer a qubit from one node to another using a remote EPR pair. One invocation of TP-Comm consumes one EPR pair and transfers one qubit to another node. As a qubit is relocated to another node, the qubit layout of the DQC network changes after an invocation of TP-Comm.
2.2
Collective Communication for DQC
Consider a qubit interaction graph 𝐺𝑞 = (𝑉𝑞 , 𝐸𝑞 ) where vertices represent qubits and edges represent gates. A connected 𝐺𝑞 having more than two vertices implies that certain qubits (distributed over various compute nodes) are involved in the execution of more than one gate. If the gates involved in 𝐺𝑞 are executed collectively at a common node, it can lead to a reduction in inter-node communication. This is known as collective communication. Formally, a collective communication block is a group of inter-node gates having a connected inter-node interaction graph on qubits over multiple nodes [20].
2.3
Communication Fusion
Communication fusion is the preprocessing stage in which the circuit is inspected for opportunities for collective communication and systematically divided into various collective communication blocks. This stage is reproduced from the description given by [20]. We assume that the circuit consists of one-qubit and two-qubit gates. Initially, the first non-local gate creates a new block, and
Dhaval Vaidya and Ruozhou Yu
each gate in the circuit having overlapping qubits with the block is subsequently iterated. A non-local gate is fused into the block if the estimated routing cost denoted by (1) in the block does not increase after fusion, while a local gate is fused if the implementation cost of the block after fusion remains unaffected. When no gate could be merged in the block without increasing post-fusion cost estimate, a new block is formed with the next non-local gate, and the entire process is repeated until no non-local gates in the circuit remain unassigned. The remaining unassigned local gates form individual blocks, which is a design choice made by us to ensure the assignment of all gates. Assume that 𝐸 (𝑛𝑎 ) is the EPR capacity of node 𝑛𝑎 , the number of qubits involved in block 𝑏 0 is 𝐻 (𝑏 0 ), and 𝐻 (𝑏 0 +𝑏 1 − 𝑛𝑎 ) is the total number of qubits involved in blocks 𝑏 0 and 𝑏 1 but not present in node 𝑛𝑎 . If a block 𝑏 1 is to be fused into block 𝑏 0 , then the estimated inter-node cost of executing blocks 𝑏 0 and 𝑏 1 is given as 𝐹 (𝑏 0, 𝑏 1 ) in Equation (1).
max 2 · 𝐻 (𝑏 0 + 𝑏 1 —𝑛𝑎 )—𝐸 (𝑛𝑎 ) , 0 + min{𝐸 (𝑛𝑎 ), 𝐻 (𝑏 0 + 𝑏 1 —𝑛𝑎 )} .
𝐹 (𝑏 0, 𝑏 1 ) = min
𝑛𝑎 ∈nodes
(1)
The reasoning is that if 𝐻 (𝑏 0 + 𝑏 1 —𝑛𝑎 ) ≤ 𝐸 (𝑛𝑎 ), then all the qubits in block 𝑏 0 and 𝑏 1 can be sent to 𝑛𝑎 using one EPR pair for each qubit. However, if 𝐻 (𝑏 0 +𝑏 1 —𝑛𝑎 ) > 𝐸 (𝑛𝑎 ), this means that the number of qubits to be transferred to 𝑛𝑎 is more than the availability of communication qubits at 𝑛𝑎 . Each of the additional qubits has to be swapped into node 𝑛𝑎 (with another qubit already present at 𝑛𝑎 ) using an inter-node SWAP gate that uses 2 invocations of TP-Comm. This is the reason why there is a multiplying factor of 2 in the first term of (1).
3
Techniques
We present DPRQ, a dynamic programming-based algorithm for efficient routing of qubits in a collective communication setup. DPRQ relies on two key processes for optimized qubit routing: (1) Intra-block communication cost, and (2) DP-based inter-block qubit routing.
3.1
Intra-block Communication Cost
The goal for routing within each collective communication block is to (i) select an aggregator node, and (ii) teleport all the qubits involved in the block to the aggregator node for local execution of inter-node gates. The intra-block communication cost jointly depends on the aggregator node and the teleportation paths of the qubits. In a uniform DQC network, the EPR cost to transfer a qubit to an aggregator node is the shortest path between the node on which the qubit is present and the aggregator node. However, in a quantum network topology, multiple shortest paths may exist between every pair of nodes. We attempt to pick the shortest path that could lead to the maximum reduction in qubit transfer cost, by leveraging the capability to early-execute some inter-node gates at intermediate nodes. This technique of executing gates early
DPRQ: A Dynamic Programming-based Qubit Routing Algorithm
Algorithm 1: Procedure to calculate intra-block routing cost. Input : Current block 𝑏, aggregator node 𝑛𝑎 , current qubit layout 𝑙, EPR capacity 𝑒; Output : Final qubit layout 𝑙, final cost 𝑇 ; 1 Function IntraBlockRouting(𝑏, 𝑛𝑎 , 𝑙, 𝑒) : 2 𝑇 ← 0; 3 for gate 𝑔 in 𝑏 do 4 if 𝑔 is a local gate then 5 continue; 6 𝑛 ← Current node where the first qubit 𝑞 of 𝑔 is present; 7 𝑛 ′ ← Current node where the second qubit 𝑞 ′ of 𝑔 is present; 8 𝑃𝑎 ← Set of all shortest paths from 𝑛 to 𝑛𝑎 ; 9 𝑃𝑎′ ← Set of all shortest paths from 𝑛 ′ to 𝑛𝑎 ; 10 for 𝑝𝑎 in 𝑃𝑎 do 11 for 𝑝𝑎′ in 𝑃𝑎′ do 12 𝑁 ′′ ← Set of all common nodes in 𝑝𝑎 and 𝑝𝑎′ ; 13 for 𝑛 ′′ in 𝑁 ′′ do 14 𝑐𝑛′′ ← 0; 15 𝑐𝑡 ← Cost of sending 𝑞 to 𝑛 ′′ via the shortest path; 16 𝑐𝑛′′ ← 𝑐𝑛′′ + 𝑐𝑡 ; 17 𝑐𝑡′ ← Cost of sending 𝑞 ′ to 𝑛 ′′ via the shortest path; 18 𝑐𝑛′′ ← 𝑐𝑛′′ + 𝑐𝑡′ ; 19 𝑛 𝑓 ← Node 𝑛 ′′ for which 𝑐𝑛′′ is minimum; 20 𝑐𝑛 𝑓 ← Cost of sending both qubits 𝑞 and 𝑞 ′ to node 𝑛𝑓 ; 21 𝑙 ← Qubit layout after sending both qubits 𝑞 and 𝑞 ′ to 𝑛 𝑓 ; 22 𝑇 ← 𝑇 + 𝑐𝑛 𝑓 ; 23 Return 𝑙,𝑇 ;
on intermediate nodes lying on the shortest qubit transfer paths is called early execution [20]. We define 𝑇 (𝑏𝑘 , 𝑛𝑘—1, 𝑛𝑘 ) as the inter-node communication cost of routing qubits in a block 𝑏𝑘 in (2), where 𝑛𝑘 is the aggregator node of the current block 𝑏𝑘 and 𝑛𝑘—1 is the aggregator node of the previous block 𝑏𝑘—1 . Additionally, a matrix 𝐿 is maintained, where 𝐿(𝑏𝑘 , 𝑛𝑘 ) is the final qubit layout after the execution of block 𝑏𝑘 with node 𝑛𝑘 as the aggregator node. Consider the initial qubit layout before the circuit execution begins as 𝑙 ′′ and the ordered list of all collective communication blocks as 𝐵. Given an aggregator node 𝑛𝑎 , the current block 𝑏, the EPR capacity of the nodes 𝑒, and the initial qubit layout 𝑙, the IntraBlockRouting procedure in Algorithm 1 iterates through each two-qubit gate of the block sequentially and finds all potential nodes (including 𝑛𝑎 ) that offer an early execution opportunity for that gate. For each potential node, the EPR cost is calculated to transfer both
QuNet ’26, August 17–21, 2026, Denver, CO, USA
qubits to these nodes. To calculate the precise routing cost of teleporting a qubit to any specific node using a path, DPRQ sequentially transfers the qubit to each intermediate node and calculates the transfer cost which is one if communication qubits are available (confirmed using the parameter 𝑒) and two otherwise (using internode SWAP gates). Finally, the node offering the least EPR cost is selected, and both qubits are teleported to that node, updating the corresponding qubit layout.
IntraBlockRouting(𝑏𝑘 , 𝑛𝑘 , 𝐿(𝑏𝑘 −1, 𝑛𝑘 −1 ), 𝑒) if 𝑘 ∈ {1, |𝐵|—1}, 𝑇 (𝑏𝑘 , 𝑛𝑘—1, 𝑛𝑘 ) = ′′ IntraBlockRouting(𝑏 0, 𝑛 0, 𝑙 , 𝑒) if 𝑘 = 0.
3.2
(2)
DP-based Inter-block Qubit Routing
Based on the cost of qubit routing within each block, DPRQ further employs a dynamic programming-based approach to reduce the end-to-end routing cost for the entire circuit, taking into account the resultant qubit layouts after executing each block. For a block 𝑏𝑘 , DPRQ calculates the cost to select node 𝑛𝑘 as the aggregator node for all 𝑛𝑘 ∈ 𝑁 , where 𝑁 is the set of all nodes in the DQC network. Specifically, DPRQ maintains a matrix of cost 𝐶, where 𝐶 (𝑏𝑘 , 𝑛𝑘 ) denotes the total communication cost to execute all blocks {𝑏 0, . . . , 𝑏𝑘 } while choosing 𝑛𝑘 as the aggregator node for block 𝑏𝑘 . The cost 𝐶 (𝑏𝑘 , 𝑛𝑘 ) is given in (3).
min∀𝑛𝑘—1 ∈𝑁 {𝐶 (𝑏𝑘—1, 𝑛𝑘—1 ) + 𝑇 (𝑏𝑘 , 𝑛𝑘—1, 𝑛𝑘 )} if 𝑘 ∈ {1, |𝐵|—1}, 𝐶 (𝑏𝑘 , 𝑛𝑘 ) = 𝑇 (𝑏𝑘 , 𝑛𝑘—1, 𝑛𝑘 ) if 𝑘 = 0.
(3)
DPRQ considers all previous aggregator nodes 𝑛𝑘—1 ∈ 𝑁 for every 𝑛𝑘 ∈ 𝑁 . This “looking-back” behavior enables DPRQ to explore a large space of initial qubit layouts for a block 𝑏𝑘 , since the initial qubit layouts for 𝑏𝑘 directly depend on the final qubit layouts after executing 𝑏𝑘 −1 . Then it is intuitive that the layout 𝐿(𝑏𝑘 −1, 𝑛𝑘 −1 ) corresponds to the minimum cost 𝐶 (𝑏𝑘 −1, 𝑛𝑘 −1 ). It can be argued that including multiple final qubit layouts for each tuple (𝑏𝑘 −1, 𝑛𝑘 −1 ) might lead to a better optimization, however, it comes at the cost of significant space and time complexity, due to which we include a single best final layout and leave the exploration of storing multiple layouts as future work. An accurate estimate of cost 𝑇 denoted by (2) gives DPRQ the ability to select a better aggregator node and decrease the number of EPR pairs required for intra-block routing. Additionally, the dynamic programming approach enables DPRQ to optimize routing among consecutive collective communication blocks by considering the best of multiple initial qubit layouts. If 𝑏𝑥 is the last block in the circuit, the final number of EPR pairs required to execute the
QuNet ’26, August 17–21, 2026, Denver, CO, USA
Dhaval Vaidya and Ruozhou Yu
circuit is given as 𝑆 (𝑏𝑥 ) in (4). 𝑆 (𝑏𝑥 ) = min 𝐶 (𝑏𝑥 , 𝑛 𝑦 ). ∀𝑛 𝑦 ∈𝑁
3.3
implementation of AutoComm [21], while the VQE circuit is taken from IBM Qiskit [14]. (4)
Scalability Analysis
We analyze the time complexity by referring to Algorithm 1 for better understanding. Consider that 𝑁 is the set of all nodes in a DQC network and 𝑍 is the list of all two-qubit gates ordered according to the corresponding collective communication blocks into which the circuit is divided. The shortest paths are calculated in 𝑂 (|𝑁 | + 𝑌 + 𝑃 · |𝑁 |) (Lines 8-9), where 𝑌 is the number of links in the network and 𝑃 is the maximum number of shortest paths between two nodes. Common nodes are found in 𝑂 (𝑃 2 |𝑁 |) (Line 12). Now, To send a qubit to each unique common node, all shortest paths are calculated again (from qubit to the common node), and the best is chosen. This ensures that when the node is a common node in another set of shortest paths, we can simply ignore it, as we have already calculated the best path. Now, to send qubit to the node, all intermediate nodes are traversed (this is necessary to account for intermediate nodes without available communication qubits)(Lines 13-18). Hence, the complexity for this process is 𝑂 (|𝑁 | · (|𝑁 | + 𝑌 + 𝑃 · |𝑁 |)). The worst-case time complexity of Algorithm 1 is 𝑂 (|𝑍 | · ((|𝑁 | + 𝑌 + 𝑃 · |𝑁 |) + 𝑃 2 |𝑁 | + |𝑁 | · (|𝑁 | + 𝑌 + 𝑃 · |𝑁 |))) = 𝑂 (|𝑍 | · (𝑃 2 |𝑁 | + 𝑃 |𝑁 | 2 + |𝑁 |𝑌 )). To calculate the routing cost for each node as the aggregator node for a single block, all aggregator nodes of the previous block are considered. Hence, the worst-case time complexity of DPRQ is 𝑂 (|𝑍 |· (𝑃 2 |𝑁 | 3 +𝑃 |𝑁 | 4 +|𝑁 | 3𝑌 )). Please note that in a large network with rich connectivity, P may be exponential in the size of the network, but for near-term quantum networks, the time complexity is manageable, and for future large-scale networks, heuristic rules can be defined for selection of a polynomial subset of paths, which is a standard practice in classical networks [15].
4 Results 4.1 Experimental Setup We have used Python 3.12.8 on a Windows 11 System with 8 CPU cores and 16 GB RAM for simulations. A mesh-grid DQC network topology [20] is employed to evaluate DPRQ on a variety of different DQC circuit configurations. Since the qubit topology inside each node is orthogonal to our research direction, no assumptions are made about the same. Furthermore, a nearest-neighbor architecture is adopted, where inter-node communication is restricted to neighboring nodes. It is also presumed that a constant communication channel is established between neighboring nodes. We evaluated DPRQ on four fault-tolerant quantum circuits that have major real-world applications. They are the BernsteinVazirani (BV) circuit (with secret string of all one) [3], Ripple-Carry Adder (RCA) circuit decomposed into Clifford+T basis [19], fixed EfficientSU2 ansatz for Variational Quantum Eigensolver (VQE) having linear entanglement [16], and QAOA (Maxcut Ansatz on a random graph with 10 edges) [10]. A 95% confidence interval is also calculated by running 10 experiments for each configuration of QAOA to account for randomness. The BV, RCA, and QAOA circuits are obtained from the open-source
4.2
Baseline, Evaluation Parameters and Evaluation Metric
As DPRQ uses the notion of collective communication similar to that used by the state-of-the-art QuComm, we used QuComm as the baseline DQC compiler to evaluate the performance of DPRQ. We reproduced the communication fusion and use it as the preprocessing stage in DPRQ as well as QuComm. We also reproduced the communication routing stage (the qubit routing stage) of QuComm and use it for comparative evaluation with DPRQ’s routing algorithm. 1 TP-Comm is used as the quantum communication protocol to transfer qubits among nodes. 2 In an experimental DQC setup, each node has a limited number of communication qubits. Moreover, a DQC circuit consisting of 150 qubits distributed over 8 compute nodes is physically realizable on certain quantum computing hardware. Hence, we select the following default values of the parameters owing to their practical relevance: EPR capacity = 3, number of data qubits = 150, and number of data qubits per node = 20. Each experiment is performed by keeping the default values for all parameters except one. The initial logical qubits of the circuit are assigned to the data qubits of node A. Once all the data qubits in node A are occupied, the remaining qubits are assigned to the data qubits of node B, C, etc. following the same logic. The same assignment method is applied to the baseline to ensure fairness in the evaluation. Finally, the number of nodes in the DQC network will be the total number of data qubits divided by the number of data qubits per node. Inter-node communication relies on remote EPR pairs, and the primary objective of DPRQ is to reduce inter-node communication in a DQC circuit. Hence, the number of EPR pairs (or the number of invocations to TP-Comm) is used as the primary metric to assess the performance of DPRQ.
4.3
Effect of Circuit Parameters
As shown in Figure 1, DPRQ consistently achieves lower routing costs for varying EPR capacity values across all four benchmark circuits. DPRQ executes the BV circuit in constant cost owing to its dynamic programming-based approach that enables sequential transfer of a single qubit to each node, avoiding redundant internode communication. Similarly, DPRQ executes the VQE and RCA circuits with a near-constant number of EPR pairs using an adaptive routing strategy that remains resilient to change in block patterns. The results indicate that DPRQ is advantageous for a significant variety of DQC hardware, ranging from those with a limited number of communication qubits to those having substantial capability to generate remote entanglements simultaneously. QuComm, on the other hand, lacks a global viewpoint of inter-correlation among blocks, showing less adaptation to the changes in EPR capacity, 1We omit the communication buffer design stage in QuComm’s reproduction as it is
orthogonal to our research direction. 2 Please note that the original QuComm paper uses Cat-Comm as well as TP-Comm; however, we use solely TP-Comm in DPRQ and exclude Cat-Comm from QuComm’s reproduction to maintain consistency in analysis. DPRQ can be extended to include Cat-Comm and we leave it for future work.
DPRQ: A Dynamic Programming-based Qubit Routing Algorithm
Figure 1: The cost comparison of DPRQ and QuComm on the four benchmark circuits as the EPR capacity increases from 1 to 5. The total number of qubits is 150 and the qubits per node is 20.
Figure 2: Cost comparison of DPRQ and QuComm on the 4 benchmark circuits as total number of qubits increases from 50 to 200. The EPR capacity is 3 and the number of qubits per node is 20.
eventually leading to inefficient routing decisions and an increase in communication costs. With varying circuit widths, DPRQ offers significantly higher reduction in inter-node communication compared to QuComm in all four benchmark circuits, as demonstrated in Figure 2. In RCA and VQE circuits, although QuComm performs equally well as DPRQ when the size of the DQC network is at most five nodes, its advantage disappears with the expansion of the network. With an increase in the number of data qubits per node, a huge number of collective communication blocks are no longer needed,
QuNet ’26, August 17–21, 2026, Denver, CO, USA
Figure 3: Cost comparison of DPRQ and QuComm on the four benchmark circuits as number of qubits per node increases from 10 to 40. The EPR capacity is 3 and the total number of qubits is 150.
Figure 4: Cost comparison of DPRQ and QuComm for 3 different network topologies on the four benchmark circuits. The EPR capacity is 3, total number of qubits is 150 and the number of qubits per node is 20.
diminishing the importance of the dynamic programming-based approach. This can be observed in Figure 3. However, the advantage of DPRQ increases for a lesser number of data qubits per node and the results indicate a clear advantage of DPRQ over QuComm, which consistently increases with an increase in the number of nodes in the DQC network.
4.4
Effect of Network Topologies
To study the adaptability of DPRQ on a range of DQC network topologies, we used three different topologies to evaluate the performance of DPRQ, namely mesh-grid topology, ring topology, and a fully-connected topology. The results of the experiments performed using the default parameters are demonstrated in Figure 4. In all
QuNet ’26, August 17–21, 2026, Denver, CO, USA
three topologies, DPRQ performs better than or equal to QuComm for all 4 benchmark circuits. Moreover, the benefit of DPRQ diminishes for a fully-connected DQC network topology. This is due to the fact that each node has an established communication link with every other node, which diminishes the importance of an improved aggregator node selection by DPRQ. However, it is clear that DPRQ is still dominant compared to QuComm due to the fact that in none of the cases, QuComm outperforms DPRQ. These results show that DPRQ is resilient to change in network topology, which makes it more scalable and significantly more adaptable to a large number of distributed systems using a variety of different network topologies.
5
Conclusion
This paper introduces DPRQ, a qubit routing algorithm that reduces the number of EPR pairs required for inter-node communication. DPRQ devises an intelligent strategy for intra-block as well as inter-block qubit routing once the circuit is divided into multiple collective communication blocks. Specifically, since inter-node communication within a block is highly dependent on the initial qubit layout, DPRQ employs a dynamic programming-based approach to explore multiple initial layouts, finally settling on the one that offers the most reduction in inter-node communication. The results demonstrate that DPRQ brings a significant reduction in inter-node communication for a variety of DQC circuit configurations. Moreover, DPRQ’s advantage grows as the number of nodes in a DQC network increases. This makes it much more adaptable for current as well as future DQC networks with a higher number of quantum processors. DPRQ has been shown to be resilient to changes in collective communication block patterns as well as network topologies. With the enhanced EPR cost calculation and dynamic programming-based circuit optimization, DPRQ provides a strong qubit routing framework for inter-node cost reduction compared to the greedy routing approach employed by QuComm. We used 80 different configurations of the four benchmark circuits for evaluation and the results demonstrate that DPRQ offers an average reduction of 24.40% and a maximum reduction of 85.06% in the EPR cost. Moreover, for a single circuit configuration, DPRQ offers a maximum average reduction of 48.54% in four different benchmark circuits. The configuration in the discussion is as follows: Number of qubits = 200, number of qubits per node = 20, and EPR capacity = 2. This shows that for a vast DQC network having a limited number of communication qubits, DPRQ offers a significant reduction in inter-node communication regardless of the benchmark circuit used.
Acknowledgments Yu’s research was supported in part by NSF grant 2350152. The information reported herein does not reflect the position or the policy of the funding agencies.
References [1] Pablo Andrés-Martínez and Chris Heunen. 2019. Automated distribution of quantum circuits via hypergraph partitioning. Physical Review A 100 (9 2019), 032308. Issue 3. https://doi.org/10.1103/PhysRevA.100.032308 [2] Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather. 2013. Efficient distributed quantum computing. Proceedings of the Royal Society A: Mathematical,
Dhaval Vaidya and Ruozhou Yu
Physical and Engineering Sciences 469, 2153 (05 2013), 20120686. https://doi. org/10.1098/rspa.2012.0686 arXiv:https://royalsocietypublishing.org/rspa/articlepdf/doi/10.1098/rspa.2012.0686/834214/rspa.2012.0686.pdf [3] Ethan Bernstein and Umesh Vazirani. 1997. Quantum Complexity Theory. SIAM J. Comput. 26 (10 1997), 1411–1473. Issue 5. https://doi.org/10.1137/ S0097539796300921 [4] Turbasu Chatterjee, Arnav Das, Shah Ishmam Mohtashim, Amit Saha, and Amlan Chakrabarti. 2022. Qurzon: A Prototype for a Divide and Conquer-Based Quantum Compiler for Distributed Quantum Systems. SN Computer Science 3, 4 (10 Jun 2022), 323. https://doi.org/10.1007/s42979-022-01207-9 [5] Davood Dadkhah, Mariam Zomorodi, Seyed Ebrahim Hosseini, Pawel Plawiak, and Xujuan Zhou. 2022. Reordering and Partitioning of Distributed Quantum Circuits. IEEE Access 10 (2022), 70329–70341. https://doi.org/10.1109/ACCESS. 2022.3186485 [6] Omid Daei, Keivan Navi, and Mariam Zomorodi-Moghadam. 2020. Optimized Quantum Circuit Partitioning. International Journal of Theoretical Physics 59 (12 2020), 3804–3820. Issue 12. https://doi.org/10.1007/s10773-020-04633-8 [7] Severin Daiss, Stefan Langenfeld, Stephan Welte, Emanuele Distante, Philip Thomas, Lukas Hartung, Olivier Morin, and Gerhard Rempe. 2021. A quantumlogic gate between distant quantum-network modules. Science 371 (2 2021), 614–617. Issue 6529. https://doi.org/10.1126/science.abe3150 [8] Zohreh Davarzani, Mariam Zomorodi-Moghadam, Mahboobeh Houshmand, and Mostafa Nouri-baygi. 2020. A dynamic programming approach for distributing quantum circuits by bipartite graphs. Quantum Information Processing 19 (10 2020), 360. Issue 10. https://doi.org/10.1007/s11128-020-02871-7 [9] Stephen DiAdamo, Marco Ghibaudi, and James Cruise. 2021. Distributed Quantum Computing and Network Control for Accelerated VQE. IEEE Transactions on Quantum Engineering 2 (2021), 1–21. https://doi.org/10.1109/TQE.2021.3057908 [10] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. (2014). arXiv:quant-ph/1411.4028 https: //arxiv.org/abs/1411.4028 [11] Davide Ferrari, Angela Sara Cacciapuoti, Michele Amoretti, and Marcello Caleffi. 2021. Compiler Design for Distributed Quantum Computing. IEEE Transactions on Quantum Engineering 2 (2021), 1–20. https://doi.org/10.1109/TQE.2021.3053921 [12] S. L. N. Hermans, M. Pompili, H. K. C. Beukers, S. Baier, J. Borregaard, and R. Hanson. 2022. Qubit teleportation between non-neighbouring nodes in a quantum network. Nature 605 (5 2022), 663–668. Issue 7911. https://doi.org/10.1038/s41586022-04697-y [13] Thomas Häner, Damian S. Steiger, Torsten Hoefler, and Matthias Troyer. 2021. Distributed quantum computing with QMPI. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’21). ACM, 1–13. https://doi.org/10.1145/3458817.3476172 [14] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. 2024. Quantum computing with Qiskit. (2024). arXiv:quant-ph/2405.08810 https://arxiv.org/abs/2405.08810 [15] Mathieu Leconte, Apostolos Destounis, and Georgios Paschos. 2018. Traffic Engineering with Precomputed Pathbooks. In IEEE INFOCOM 2018 - IEEE Conference on Computer Communications. IEEE Press, 234–242. https://doi.org/10.1109/ INFOCOM.2018.8486419 [16] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. 2014. A variational eigenvalue solver on a photonic quantum processor. Nature Communications 5 (7 2014), 4213. Issue 1. https://doi.org/10.1038/ncomms5213 [17] M. Pompili, S. L. N. Hermans, S. Baier, H. K. C. Beukers, P. C. Humphreys, R. N. Schouten, R. F. L. Vermeulen, M. J. Tiggelman, L. dos Santos Martins, B. Dirkse, S. Wehner, and R. Hanson. 2021. Realization of a multinode quantum network of remote solid-state qubits. Science 372 (4 2021), 259–264. Issue 6539. https://doi.org/10.1126/science.abg1919 [18] Maximilian Ruf, Noel H. Wan, Hyeongrak Choi, Dirk Englund, and Ronald Hanson. 2021. Quantum networks based on color centers in diamond. Journal of Applied Physics 130 (8 2021). Issue 7. https://doi.org/10.1063/5.0056534 [19] Vlatko Vedral, Adriano Barenco, and Artur Ekert. 1996. Quantum networks for elementary arithmetic operations. Physical Review A 54 (7 1996), 147–153. Issue 1. https://doi.org/10.1103/PhysRevA.54.147 [20] Anbang Wu, Yufei Ding, and Ang Li. 2023. QuComm: Optimizing Collective Communication for Distributed Quantum Computing. In Proceedings of the 56th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO ’23). Association for Computing Machinery, New York, NY, USA, 479–493. https: //doi.org/10.1145/3613424.3614253 [21] Anbang Wu, Hezi Zhang, Gushu Li, Alireza Shabani, Yuan Xie, and Yufei Ding. 2022. AutoComm: A Framework for Enabling Efficient Communication in Distributed Quantum Programs. (2022). arXiv:quant-ph/2207.11674 https://arxiv.org/abs/2207.11674 [22] Mariam Zomorodi-Moghadam, Mahboobeh Houshmand, and Monireh Houshmand. 2018. Optimizing Teleportation Cost in Distributed Quantum Circuits. International Journal of Theoretical Physics 57 (3 2018), 848–861. Issue 3. https://doi.org/10.1007/s10773-017-3618-x