A crucial step in compiling a quantum algorithm involves addressing a layout problem to meet the device’s layout constraints. The Qubit Mapping and Routing (QMR) problem aims to minimize the number of SWAP gates added to the circuit to fulfill NISQ hardware’s connectivity constraints. Although this problem is NP-hard, finding solutions quickly is vital as it is part of the compilation process.
A crucial step in compiling a quantum algorithm involves addressing a layout problem to meet the device’s layout constraints. The Qubit Mapping and Routing (QMR) problem aims to minimize the number of SWAP gates added to the circuit to fulfill NISQ hardware’s connectivity constraints. Although this problem is NP-hard, finding solutions quickly is vital as it is part of the compilation process.
To evaluate a quantum circuit on a quantum processor, one must find a mapping from circuit qubits to processor qubits and plan the instruction execution while satisfying the processor’s constraints. This is known as the qubit mapping and routing ( qmr ) problem. High-quality qmr solutions are key to maximizing the utility of scarce quantum resources and minimizing the probability of logical errors affecting computation. The challenge is that the landscape of quantum processors is incredibly diverse and fast-evolving. Given this diversity, dozens of papers have addressed the qmr problem for different qubit hardware, connectivity constraints, and quantum error correction schemes by a developing a new algorithm for a particular context. We present an alternative approach: automatically generating qubit mapping and routing compilers for arbitrary quantum processors. Though each qmr problem is different, we identify a common core structure— device state machine —that we use to formulate an abstract qmr problem . Our formulation naturally leads to a compact domain-specific language for specifying qmr problems and a powerful parametric algorithm that can be instantiated for any qmr specification. Our thorough evaluation on case studies of important qmr problems shows that generated compilers are competitive with handwritten, specialized compilers in terms of runtime and solution quality.
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.
Near-term quantum computers will operate in a noisy environment, without error correction. A critical problem for near-term quantum computing is laying out a logical circuit onto a physical device with limited connectivity between qubits. This is known as the qubit mapping and routing (QMR) problem, an intractable combinatorial problem. It is important to solve QMR as optimally as possible to reduce the amount of added noise, which may render a quantum computation useless. In this paper, we present a novel approach for optimally solving the QMR problem via a reduction to maximum satisfiability (MAXSAT). Additionally, we present two novel relaxation ideas that shrink the size of the MAXSAT constraints by exploiting the structure of a quantum circuit. Our thorough empirical evaluation demonstrates (1) the scalability of our approach compared to state-of-the-art optimal QMR techniques (solves more than 3x benchmarks with 40x speedup), (2) the significant cost reduction compared to state-of-the-art heuristic approaches (an average of ~5x swap reduction), and (3) the power of our proposed constraint relaxations.
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.
Abstract In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446 ), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.
The design of quantum algorithms typically assumes the availability of an ideal quantum computer, characterized by full connectivity, noiseless operation, and unlimited coherence time. However, Noisy Intermediate-Scale Quantum (NISQ) devices present a stark contrast, with a limited number of qubits, non-negligible quantum operation errors, and stringent constraints on the connectivity of physical qubits within a Quantum Processing Unit (QPU). This necessitates the dynamic remapping of logical qubits to physical qubits within the compiler to facilitate the execution of two-qubit gates in the algorithm. However, this introduces additional operations, consequently reducing the fidelity of the algorithm. Therefore, minimizing the number of added gates becomes crucial. Finding such an optimal routing problem is NP-hard, and the task is conventionally addressed using human-crafted heuristics to search for SWAP sequences, but these lack performance guarantees. In this study, we employ a Seq2Seq machine learning model for the qubit routing task, incorporating a Transformer neural network to learn the routing information in the gate and SWAP sequence. Compared to heuristic search-based algorithms, our approach significantly reduces the overhead of quantum computing resources required to adapt logical circuits to physical circuits executable on specific quantum backend hardware.