As quantum computing devices increase in size with respect to the number of qubits, two-qubit interactions become more challenging, necessitating innovative and scalable qubit routing solutions. In this work, we introduce beSnake, a novel algorithm specifically designed to address the intricate qubit routing challenges in scalable spin-qubit architectures. Unlike traditional methods in superconducting architectures that solely rely onswapoperations, beSnake also incorporates the shuttle operation to optimize the execution time and fidelity of quantum circuits and achieves fast computation times of the routing task itself. Employing a simple breadth-first search approach, beSnake effectively manages the restrictions created by diverse topologies and qubit positions acting as obstacles for up to 72% qubit density. It also has the option to adjust the level of optimization and to dynamically tackle parallelized routing tasks, all the while maintaining noise awareness. Our simulations demonstrate beSnake's advantage over an existing routing solution on random circuits and real quantum algorithms with up to 1000 qubits, showing an average improvement of up to 80% in gate overhead, 54% in depth overhead, and up to 8.33 times faster routing times.
As quantum computing devices increase in size with respect to the number of qubits, two-qubit interactions become more challenging, necessitating innovative and scalable qubit routing solutions. In this work, we introduce beSnake, a novel algorithm specifically designed to address the intricate qubit routing challenges in scalable spin-qubit architectures. Unlike traditional methods in superconducting architectures that solely rely onswapoperations, beSnake also incorporates the shuttle operation to optimize the execution time and fidelity of quantum circuits and achieves fast computation times of the routing task itself. Employing a simple breadth-first search approach, beSnake effectively manages the restrictions created by diverse topologies and qubit positions acting as obstacles for up to 72% qubit density. It also has the option to adjust the level of optimization and to dynamically tackle parallelized routing tasks, all the while maintaining noise awareness. Our simulations demonstrate beSnake's advantage over an existing routing solution on random circuits and real quantum algorithms with up to 1000 qubits, showing an average improvement of up to 80% in gate overhead, 54% in depth overhead, and up to 8.33 times faster routing times.
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.
Despite Noisy Intermediate-Scale Quantum devices being severely constrained, hardware- and algorithm-aware quantum circuit mapping techniques have been developed to enable successful algorithm executions. Not so much attention has been paid to mapping and compilation implementations for spin-qubit quantum processors due to the scarce availability of experimental devices and their small sizes. However, based on their high scalability potential and their rapid progress it is timely to start exploring solutions on such devices. In this work, we discuss the unique mapping challenges of a scalable crossbar architecture with shared control and introduce SpinQ , the first native compilation framework for scalable spin-qubit architectures. At the core of SpinQ is the Integrated Strategy that addresses the unique operational constraints of the crossbar while considering compilation scalability and obtaining a O(n) computational complexity. To evaluate the performance of SpinQ on this novel architecture, we compiled a broad set of well-defined quantum circuits and performed an in-depth analysis based on multiple metrics such as gate overhead, depth overhead, and estimated success probability, which in turn allowed us to create unique mapping and architectural insights. Finally, we propose novel mapping techniques that could increase algorithm success rates on this architecture and potentially inspire further research on quantum circuit mapping for other scalable spin-qubit architectures.
Quantum computers are expected to scale in size to close the gap that currently exists between quantum algorithms and quantum hardware. To this end, quantum compilation techniques must scale along with the hardware constraints, shifting the current paradigm of obtaining an optimal compilation to relying on heuristics that allow for a fast solution, even though the quality of such a solution may not be optimal. Significant concerns arise as the execution time of current mapping techniques experiences a notable increase when applied to quantum computers with a high number of qubits. In this work, we present Route-Forcing, a quantum circuit mapping algorithm that shows a compilation time average speedup of 3.7 × compared to the state-of-the-art scalable techniques, reducing the depth of the mapped circuit by 4.7 × at the expense of adding 1.3 × more SWAP gates. Moreover, the proposed mapping algorithm is adapted and tuned for what is expected to be the next generation of quantum computers, in which different processors are interconnected to increase the total number of qubits, allowing for more complex computations.
Quantum computers with a limited qubit connectivity require inserting SWAP gates for qubit routing, which increases gate execution errors and the impact of environmental noise due to an overhead in circuit depth. In this work, we benchmark various routing techniques considering random quantum circuits on one-dimensional and square lattice connectivities, employing both analytical and numerical methods. We introduce circuit fidelity as a comprehensive metric that captures the effects of SWAP and circuit depth overheads. Leveraging a novel approach based on the SABRE algorithm, we achieve up to 84% higher average circuit fidelity for large devices within the NISQ range, compared to previously existing methods. Additionally, our results highlight that the optimal routing choice critically depends on the qubit count and the hardware characteristics, including gate fidelities and coherence times.
Despite rapid advances in quantum computing technologies, the qubit connectivity limitation remains to be a critical challenge. Both near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. As a result, quantum circuits may not be directly executed on quantum hardware, and a quantum compiler needs to perform qubit routing to make the circuit compatible with the device layout. During the qubit routing step, the compiler inserts SWAP gates and performs circuit transformations. Given the connectivity topology of the target hardware, there are typically multiple qubit routing candidates. The state-of-the-art compilers use a cost function to evaluate the number of SWAP gates for different routes and then select the one with the minimum number of SWAP gates. After qubit routing, the quantum compiler performs gate optimizations upon the circuit with the newly inserted SWAP gates.In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should not be independent on subsequent gate optimizations. We find that with the consideration of gate optimizations, not all of the SWAP gates have the same basis-gate cost. These insights lead to the development of our qubit routing algorithm, NASSC (Not All Swaps have the Same Cost). NASSC is the first algorithm that considers the subsequent optimizations during the routing step. Our optimization-aware qubit routing leads to better routing decisions and benefits subsequent optimizations. We also propose a new optimization-aware decomposition for the inserted SWAP gates. Our experiments show that the routing overhead compiled with our routing algorithm is reduced by up to 69.30% (21.30% on average) in the number of CNOT gates and up to 43.50% (7.61% on average) in the circuit depth compared with the state-of-the-art scheme, SABRE.
In current quantum devices, physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. Quantum circuit transformation consists of two steps, initial mapping and qubit routing, and here we propose a DEAR (Dynamically-Extract-and-Route) framework to solve the qubit routing problem. A key insight of DEAR is that by maintaining a sufficient lookahead ability all the time, we can make much better routing decisions while effectively controlling the runtime. In our DEAR framework, we periodically extract a subcircuit by identifying a set of remaining gates that should be executed earlier than the others, and then applies A* search to determine how to insert a sequence of additional SWAP and BRIDGE operations into the subcircuit to obtain a high quality routing solution with minimum number of additional gates. In this work, we consider the insertion of both SWAP and BRIDGE operations while most previous works deal with SWAP insertion only. We evaluate our approach with four benchmark sets with different characterization on IBM Tokyo. The experimental results show that our approach outperforms the state-of-the-art work utilizing SWAP and BRIDGE insertion with 19.1% and 77.5% average reduction in the number of additional gates and runtime, respectively, starting from the same initial mapping. We also performed experiments on larger quantum devices such as Google Sycamore and IBM Rochester both with 53 physical qubits that have largely different architectures from one another and from IBM Tokyo. Again, DEAR was much faster and required significantly less amount of additional gates.