摘要
Advanced silicon-based spin-qubit chips are being developed by the industry because of its promising scalability for large-scale quantum computing. The silicon-based fabrication of spin-qubit devices allows them to scale to thousands of qubits while maintaining a relatively small area compared to other quantum technologies such as superconducting or neutral atom. However, the unique characteristics of spin-qubit devices limit the applicability of existing qubit routing methods developed for other quantum devices, and the state-of-the-art routing approach for spin-qubit devices overlooks some key factors, leading to suboptimal solution quality. We introduce a novel routing method for spin-qubit devices that leverages Dijkstra's algorithm and breadth-first search to determine the routing path for the operand qubit(s) of each gate. To avoid redundant computations for routing paths, we determine the routing region for each gate and represent it as a bit vector, which enables efficient overlap checking between routing regions. We performed experiments on four benchmark sets, including circuits with up to 1617 qubits and more than 700,000 gates. These benchmark sets cover a wide range of quantum circuits, including reversible arithmetic, algorithmic, synthesized, and random circuits. Our proposed method resulted in high-quality routing solutions and outperformed the state-of-the-art qubit routing approach on spin-qubit devices with over 29% and 7% reduction in operation overhead and depth overhead, respectively.