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.
Quantum computing promises breakthroughs in simulating and solving complex, classically intractable problems. However, current noisy intermediate-scale quantum (NISQ) devices are relatively small and error-prone, prohibiting large-scale computations. To achieve quantum advantage in this regime, it is crucial to minimise the impact of noise from qubit decoherence and two-qubit gates. A direct approach is to optimise quantum circuit compilation, particularly by improving how circuits are mapped onto hardware. This work targets multi-qubit pathfinding (MQPF), a key subproblem in quantum circuit mapping, formulated as a variant of the token swapping problem. We propose an adaptable algorithm, modelled as a binary integer linear program, that routes
K teams of qubits on hardware graphs using swap operations. The algorithm minimises SWAP-gate depth and accumulated gate and idle errors, effectively solving a weighted version of the parallel (
K+1)-coloured token swapping problem. We benchmark performance across various hardware layouts, comparing runtimes, SWAP depths, gate counts, and errors. Our results show that the proposed MQPF algorithm offers significantly improved runtime scaling and lower accumulated errors over a state-of-the-art exact SMT-CBS-based method. Potential applications include precomputing optimal routing for circuit mappers, benchmarking heuristics, and informing quantum hardware design by analysing pathfinding behaviour.
Due to the short decohorence time of qubits available in the NISQ-era, it is essential to pack (minimize the size and or the depth of) a logical quantum circuit as efficiently as possible given a sparsely coupled physical architecture. In this work we introduce a locality-aware qubit routing algorithm based on a graph theoretic framework. Our algorithm is designed for the grid and certain “grid-like” architectures. We experimentally show the competitiveness of algorithm by comparing it against the approximate token swapping algorithm, which is used as a primitive in many state-of-the-art quantum transpilers. Our algorithm produces circuits of comparable depth (better on random permutations) while being an order of magnitude faster than a typical implementation of the approximate token swapping algorithm.