Optimized Qubit Routing for Commuting Gates via Integer Programming

Moritz Stargalla, Friedrich Wagner · 2025

Read Optimized Qubit Routing for Commuting Gates via Integer Programming by Moritz Stargalla, Friedrich Wagner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12199.txt.

Introduction

Moritz Stargalla and Friedrich Wagner find provably best routes for qubits in quantum circuits, in a 2025 paper. Quantum hardware is small and error prone, so compilers must place operations with care. Routing qubits for gates that commute, meaning their order can swap, is a key step. It arises when compiling a well-known optimization method.

Their approach splits the problem in two and solves each part with integer programming, a math method that guarantees the best answer. They prove the routing problem itself is NP-hard, which justifies the heavy tool. Bounds on solution quality are derived as well. In computer tests, their method beat guessing heuristics on quality and older exact methods on speed.

Catalog record

CREATORMoritz Stargalla, Friedrich Wagner
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-12199

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimized Qubit Routing for Commuting Gates via Integer Programming Moritz Stargalla, Friedrich Wagner Abstract Quantum computers promise to outperform their classical counterparts at certain tasks. However, existing quantum devices are error-prone and restricted in size. Thus, effective compilation methods are crucial to exploit limited quantum resources. In this work, we address the problem of qubit routing for commuting gates, which arises, for example, during the compilation of the well-known Quantum Approximate Optimization Algorithm. We propose a two-step decomposition approach based on integer programming, which is guaranteed to return an optimal solution. To justify the use of integer programming, we prove NP-hardness of the underlying optimization problem. Furthermore, we derive asymptotic upper and lower bounds on the quality of a solution. We develop several integer programming models and derive linear descriptions of related polytopes, which generalize to applications beyond this work. Finally, we conduct a computational study showing that our approach outperforms existing heuristics in terms of quality and exact methods in terms of runtime. 1 Introduction Quantum computing bears the potential to impact various fields such as chemistry [ 1 ] , material science [ 2 ] , machine learning [ 3 ] and optimization [ 4 ] . However, current quantum hardware is limited in size and prone to high error rates [ 5 ] . Thus, it is crucial to efficiently exploit limited quantum resources and to reduce error probabilities. Qubit routing is an \mathcal{NP} -hard combinatorial optimization problem which arises when compiling quantum algorithms to hardware-specific instructions [ 6 , 7 ] . The quality of the qubit routing solution heavily influences the success probability during execution [ 8 , 9 ] . Quantum algorithms are generally formulated in the circuit model of quantum computing, see [ 10 ] for an introduction. An example quantum circuit is depicted in Figure 1 . Such a circuit comprises wires representing logical qubits and a temporal sequence of gates applied to subsets of logical qubits. In this work, we consider circuits containing exclusively gates that act on pairs of qubits, called two-qubit gates. The presence of single-qubit gates does not alter the resulting qubit routing problem. Moreover, any multi-qubit gate can be decomposed into single- and two-qubit gates [ 11 ] . A quantum circuit may apply two-qubit gates on any pair of logical qubits. However, actual quantum processors can only apply two-qubit gates on certain pairs of qubits. Thus, quantum processors are often represented by a hardware graph , see Figure 1 for an example. The nodes of the hardware graph correspond to physical qubits while its edges define the pairs of physical qubits on which two-qubit gates can be applied. General qubit routing. To execute a circuit on a quantum computer with a given hardware graph, one must choose an initial allocation of logical to physical qubits ensuring that for each two-qubit gate, the logical qubits are located at neighboring physical qubits in the hardware graph. However, such an allocation does not exist in general, as is the case for the example in Figure 1 . In such a case, additional swap gates have to be inserted into the circuit. A swap gate is a two-qubit gate which effectively swaps the allocations of the involved logical qubits. Thus, swap gates allow to modify the initial allocation of logical to physical qubits. The outcome is a routed circuit that meets the connectivity restrictions and is equivalent to the original circuit up to a permutation of the qubits, as shown in Figure 1 . This permutation results from the initial allocation and the swap gates. Figure 1 : Example of a quantum circuit with commuting gates (left), a hardware graph (center), and a routed quantum circuit with inserted swap gates (right). For each gate in the routed circuit, the involved pair of logical qubits gates is allocated at neighboring physical qubits. The order of gates in the routed circuit is the same as in the original circuit. Due to high gate error rates in existing quantum devices, it is crucial to minimize the number of swap gates in the routed circuit. Moreover, the error probability increases with the time taken to execute the routed circuit. This translates into minimizing the depth of the circuit. The depth is defined as the minimum number of layers the gates can be partitioned into. A layer is a set of consecutive gates that act on disjoint qubits and can thus be executed in parallel. For example, the depth of the routed circuit in Figure 1 amounts to 5 . Qubit routing with commuting gates. Generally, the order of the two-qubit gates in a circuit matters. However, important applications such as the Quantum Approximate Optimization Algorithm (QAOA) [ 12 ] and Hamiltonian simulation [ 13 ] result in circuits with blocks of commuting gates. Thus, inside one block the order of gates can be changed arbitrarily. In such a case, the order of the gates provides an additional degree of freedom that can be optimized, potentially reducing the number of swap gates and the circuit depth as illustrated in the example of Figure 2 . Figure 2 : A routed quantum circuit that is equivalent to the circuits in Figure 1 but exploits commutativity. Both depth and swap count are reduced compared to the routed circuit in Figure 1 . 1.1 Our Contribution We propose an algorithm for the qubit routing problem with commuting gates that is guaranteed to return a circuit with a minimum number of swaps. This is in contrast to existing heuristic methods, which do not provide any performance guarantees. Moreover, our algorithm also heuristically minimizes depth among all swap-optimal solutions. We achieve this by developing a two-stage optimization approach that lexicographically optimizes for swap count and depth. First, we compute an initial mapping of circuit to physical qubits and a set of swap layers ensuring that each gate is executable. In the second stage, we schedule all gates of the original circuit into either a swap layer or a new layer, aiming to minimize the depth of the resulting circuit. We formally define the first problem of our two-step approach as a combinatorial optimization problem, which we call Token Meeting Problem (TMP). We analyze the TMP and derive asymptotic lower and upper bounds on the cost of a solution. After proving \mathcal{NP} -hardness, we propose several integer programming models for solving the TMP. Furthermore, we provide linear descriptions for two associated polytopes, which may have applications beyond this work. Additionally, we develop an integer programming model also for the second stage of our approach. Finally, we conduct computational experiments which show that our methods outperform existing heuristics in terms of quality and existing exact methods in terms of solution time. 1.2 Related Work For an introduction to quantum computing, we refer to [ 10 ] . Ge et al. [ 14 ] provide a comprehensive review on the synthesis and compilation of quantum circuits. Numerous heuristics have been proposed for the general qubit routing problem [ 15 , 16 , 17 , 18 , 19 , 20 ] , see [ 21 ] for a detailed survey. Heuristics typically scale well with respect to the circuit size and are thus the

Read the complete text