Divide-et-Impera Heuristic-Based Randomized Search Achieves Improved 20-Qubit Quantum Circuit Routing

The challenge of efficiently routing information between qubits represents a significant hurdle in realising the potential of quantum computers, and researchers are continually seeking improved methods to overcome this limitation. Marco Baioletti from University of Perugia, Fabrizio Fagiolo and Angelo Oddi from the Institute of Cognitive Sciences and Technologies (ISTC) National Research Council (CNR), along with Riccardo Rasconi, present a new algorithm, DIRSH, that tackles this problem using a unique divide-and-conquer strategy. The team’s approach breaks down complex quantum circuits into smaller, more manageable sections, optimising each individually with a carefully balanced combination of random exploration and intelligent decision-making. Testing DIRSH on standard benchmarks designed for realistic quantum hardware demonstrates its superiority over existing methods, achieving faster and more efficient qubit routing, and representing a substantial step towards practical quantum computation.

DIRSH Algorithm Optimizes Qubit Routing Performance

Scientists have developed a new algorithm, DIRSH, designed to address the challenging Qubit Routing Problem, a critical step in executing quantum computations on real hardware. The method employs a divide-and-conquer strategy, splitting quantum circuits into smaller chunks and optimizing each one using a combination of randomized search and heuristic guidance. This approach effectively balances exploring many potential solutions with focusing on promising areas, leading to improved performance. Experiments conducted on RevLib benchmarks mapped to a 20-qubit IBMQ Tokyo topology demonstrate that DIRSH consistently outperforms three variants of the LightSABRE algorithm.

Across various time budgets, DIRSH achieves shorter circuit depths and requires fewer swap gates, essential for minimizing errors in quantum computations. Specifically, the algorithm’s success stems from combining chunk-based decomposition with bandit-driven heuristics, a novel approach to qubit routing. The research team’s method focuses on minimizing both circuit depth and the number of swap gates required, crucial metrics for evaluating the efficiency and accuracy of quantum computations. By strategically rearranging qubits, DIRSH reduces the need for additional operations, thereby decreasing the potential for errors caused by hardware limitations and decoherence. The results confirm that this combination of techniques is highly effective for routing quantum circuits on current Noisy Intermediate-Scale Quantum devices.

DIRSH Algorithm Excels at Qubit Routing

The research team developed DIRSH, a novel algorithm for solving the qubit routing problem, employing a randomized, divide-and-conquer strategy guided by heuristic optimization. The method decomposes quantum circuits into smaller chunks and then optimizes each chunk using a stochastic approach that balances exploration of potential solutions with focused local refinement. This is achieved through a multi-armed bandit scheme, allowing the algorithm to adaptively tune its search parameters and prioritize promising routes. Testing DIRSH on benchmark circuits mapped to a 20-qubit IBMQ Tokyo topology demonstrates its effectiveness, consistently outperforming three variants of the LightSABRE algorithm across various time constraints.

Specifically, DIRSH produced shorter circuits and required fewer swap operations, establishing a clear advantage in both depth and complexity reduction. These results confirm that combining chunk-based decomposition with bandit-controlled heuristics represents a successful approach to routing quantum circuits on near-term, noisy intermediate-scale quantum (NISQ) hardware. Future work could focus on developing a dynamic chunk splitting system to improve performance on larger instances and extending DIRSH to be noise-aware, integrating quantum gate error rates into the cost function to directly minimize noise during routing and enhance circuit accuracy on real quantum devices.