Adaptable Weighted Token Swapping Algorithm for Optimal Multi-Qubit Pathfinding

Abstract

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.