To execute a quantum program, it has to be compiled for execution on the target quantum processor. The program is first converted into a logical circuit composed of elementary gates supported by the target processor. Most often the logical circuit cannot be executed directly on the quantum processor due to the limited connectivity between the physical qubits of the processor. So, a quantum compiler needs to perform qubit routing by inserting auxiliary gates to execute operations like SWAP, MOVE, and BRIDGE in order to satisfy the connectivity constraint. Qubit routing yields a physical circuit that can be executed on the target processor. Finally, the physical circuit still has to be scheduled considering the gate delays and the control constraints imposed by the shared classical control electronics of the quantum processor. For noisy intermediate-scale quantum processors, it is important to minimize the latency of the final scheduled physical circuit. However, solving qubit routing without considering gate delays and control constraints will inevitably lead to suboptimal final results. Here we propose a control and timing-aware qubit routing algorithm, CTQr, considering gate delays and control constraints. Moreover, CTQr performs gate merging on the fly in order to minimize the final circuit latency. The experimental results show that CTQr outperforms the state-of-art approach with 11.2%, 8.8%, and 54.6% average reduction in the circuit latency, number of additional gates, and execution time, respectively.
To execute a quantum program, it has to be compiled for execution on the target quantum processor. The program is first converted into a logical circuit composed of elementary gates supported by the target processor. Most often the logical circuit cannot be executed directly on the quantum processor due to the limited connectivity between the physical qubits of the processor. So, a quantum compiler needs to perform qubit routing by inserting auxiliary gates to execute operations like SWAP, MOVE, and BRIDGE in order to satisfy the connectivity constraint. Qubit routing yields a physical circuit that can be executed on the target processor. Finally, the physical circuit still has to be scheduled considering the gate delays and the control constraints imposed by the shared classical control electronics of the quantum processor. For noisy intermediate-scale quantum processors, it is important to minimize the latency of the final scheduled physical circuit. However, solving qubit routing without considering gate delays and control constraints will inevitably lead to suboptimal final results. Here we propose a control and timing-aware qubit routing algorithm, CTQr, considering gate delays and control constraints. Moreover, CTQr performs gate merging on the fly in order to minimize the final circuit latency. The experimental results show that CTQr outperforms the state-of-art approach with 11.2%, 8.8%, and 54.6% average reduction in the circuit latency, number of additional gates, and execution time, respectively.
Quantum algorithms need to be compiled to respect the constraints imposed by quantum processors, which is known as the mapping problem. The mapping procedure will result in an increase of the number of gates and of the circuit latency, decreasing the algorithm’s success rate. It is crucial to minimize mapping overhead, especially for noisy intermediate-scale quantum (NISQ) processors that have relatively short qubit coherence times and high gate error rates. Most of prior mapping algorithms have only considered constraints, such as the primitive gate set and qubit connectivity, but the actual gate duration and the restrictions imposed by the use of shared classical control electronics have not been taken into account. In this article, we present a mapper called Qmap to make quantum circuits executable on scalable processors with the objective of achieving the shortest circuit latency. In particular, we propose an approach to formulate the classical control restrictions as resource constraints in a conventional list scheduler with polynomial complexity. Furthermore, we implement a routing heuristic to cope with the connectivity limitation. This router finds a set of movement operations that minimally extends circuit latency. To analyze the mapping overhead and evaluate the performance of different mappers, we map 56 quantum benchmarks onto a superconducting processor named Surface-17. Compared to a prior mapping strategy that minimizes the number of operations, Qmap can reduce the latency overhead (LtyOH) up to 47.3% and operation overhead up to 28.6%, respectively.
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.
Abstract The limited qubit connectivity of quantum processors poses a significant challenge in deploying practical algorithms and logical gates, necessitating efficient qubit mapping and routing strategies. When implementing a gate that requires additional connectivity beyond the native connectivity, the qubit state must be moved to a nearby connected qubit to execute the desired gate locally. This is typically achieved using a series of SWAP gates creating a SWAP path. However, routing methods relying on SWAP gates often lead to increased circuit depth and gate count, motivating the need for alternative approaches. This work explores the potential of teleported gates to improve qubit routing efficiency, focusing on implementation within specific hardware topologies and benchmark quantum algorithms. We propose a routing method that is assisted by gate teleportation. It establishes additional connectivity using gate teleportation paths through available unused qubits, termed auxiliary qubits, within the topology. To optimize this approach, we have developed an algorithm to identify the best gate teleportation connections, considering their potential to reduce the depth of the circuit and address possible errors that may arise from the teleportation paths. Finally, we demonstrate depth reduction with gate teleportation-assisted routing in various benchmark algorithms, including case studies on the compilation of the Deutsch–Jozsa algorithm and the quantum approximation optimization algorithm for heavy-hexagon topology used in IBM 127-qubit Eagle r3 processors. Our benchmark results show a 10%–25% depth reduction in the routing of selected algorithms compared to regular routing without using teleported gates.
To address the scalability challenges of quantum computing, the industry is shifting from monolithic architectures to modular quantum systems. By interconnecting multiple quantum processing units (QPUs) through communication links, modular quantum systems can scale to much higher number of qubits. However, the delay of inter-QPU operations is an order of magnitude greater than that of intra-QPU operations. To minimize the final circuit latency, a well-considered initial assignment of logical qubits in the circuit to QPUs in the system and careful insertion of inter-QPU operations are required. In this paper, we propose a timing-aware end-to-end circuit compilation framework for modular quantum systems. In the placement stage, a dependency- and interaction-aware assignment strategy is developed to assign logical qubits that interact early and frequently to nearby QPUs. In the routing stage, we optimize the insertion of inter-QPU operations and multiple intra-QPU operations to enable the execution of the gates. The selection of both inter- and intra-QPU operations is based on their circuit latency overhead, which is estimated using the operation delay and the available idle time of operand qubits that can cover the delay, as well as their benefit to subsequent gates. Our experiments assumed a realistic modular quantum system consisting of three interconnected QPUs with a total of 1,386 physical qubits. We evaluated our framework using two benchmark sets consisting of reversible arithmetic circuits and algorithmic circuits, with up to 1,300 qubits and over 800,000 two-qubit gates. Experimental results demonstrate that our approach outperformed the state-of-the-art compilation approach for modular quantum systems with over 73.8% and 46.9% reduction in final circuit latency and number of inserted inter-QPU operations, respectively. In addition, this advantage is preserved on a larger modular quantum system with four QPUs arranged in a square topology.
Quantum circuits are typically represented by a (ordered) sequence of gates over a set of virtual qubits. During compilation, the virtual qubits of the gates are assigned to the physical qubits of the underlying quantum hardware, a step often referred to as the qubit assignment problem. To ensure that the resulting circuit respects hardware connectivity constraints, additional SWAP gates are inserted as needed, which is known as the qubit routing problem. Together, they are called the Qubit Mapping Problem (QMP), which is known to be NP-hard. A very common way to deal with the complexity of the QMP is to partition the sequence of gates into a sequence of gate groups (or layers). However, this imposes a couple of important restrictions: (1) SWAP gates can only be added between pairs of consecutive groups, and (2) all the gates belonging to a certain group have to be executed (in parallel) in the same time slot. The first one prevents gates to be re-arranged optimally, while the second one imposes a time discretization that practically ignores gate execution time. While this clearly reduces the size of the feasible space, little is still known about how much is actually lost by imposing a fixed layering when looking at the minimization of either the number of SWAPs or the makespan of the compiled circuit. In this paper, we present a flexible branch and bound algorithm for a generalized version of the QMP that either considers or ignores the gate layering and the gate execution time. The algorithm can find find proven optimal solutions for all variations of the QMP, but also offers a great platform for different heuristic algorithms. We present results on several benchmark sets of small quantum circuits, and we show how ignoring the layering can significantly improve some key performance indicators of the compiled circuit.