Line-Graph Qubit Routing

Abstract

One limitation of current quantum hardware is the restricted connectivity between qubits, as described by the hardware’s coupling graph. To overcome this limitation, efficient qubit routing strategies are necessary. We introduce line-graph qubit routing, which routes circuits defined on line graphs to hardware with a heavy coupling graph. We implement line-graph qubit routing and demonstrate its effectiveness in mapping quantum circuits defined kagome, checkerboard, and shuriken lattices to hardware with heavy-hex, heavy-square, and heavy-square-octagon coupling graphs, respectively. Benchmarking shows the ability of line-graph qubit routing to outperform established general-purpose methods in a fraction of the computational time, while offering a depth reduction by up to a factor of 5. Line-graph qubit routing has direct applications in the quantum simulation of lattice-based models, serves as a suitable benchmark for other routing methods, and aids the exploration of the capabilities of near-term quantum hardware.