Journal ArticleDQC-QR: Distributing and Routing Quantum Circuits with Minimum Execution TimeSundaram, Ranjani; Gupta, Himanshu; Ramakrishnan, CR<p>Present quantum computers are constrained by limited qubit capacity and restricted physical connectivity, leading to challenges in large-scale quantum computations. Distributing quantum computations across a network of quantum computers is a promising way to circumvent these challenges and facilitate large quantum computations. However, distributed quantum computations require entanglements (to execute remote gates) which can incur significant generation latency and, thus, lead to decoherence of qubits. In this work, we consider the problem of distributing quantum circuits across a quantum network to minimize the execution time. The problem entails mapping the circuit qubits to network memories, including within each computer since limited connectivity within computers can affect the circuit execution time.</p> <p>We provide two-step solutions for the above problem: In the first step, we allocate qubits to memories to minimize the estimated execution time; for this step, we design an efficient algorithm based on an approximation algorithm for the max-quadratic-assignment problem. In the second step, we determine an efficient execution scheme, including generating required entanglements with minimum latency under the network resource and decoherence constraints; for this step, we develop two algorithms with appropriate performance guarantees under certain settings or assumptions. We consider multiple protocols for executing remote gates, viz., telegates and cat-entanglements. With extensive simulations over NetSquid, a quantum network simulator, we demonstrate the effectiveness of our developed techniques and show that they outperform a scheme based on prior work by 40 to<inline-formula content-type='math/tex'><tex-math notation='TeX' version='MathJaX'>\(50\% \)</tex-math></inline-formula>on average and up to 95% in some cases.</p>ACM2025-07-3010628826ACM Transactions on Quantum Computing2643-6809https://doi.org/10.1145/37570692106447National Science Foundation