  Quantum computers have the potential to outperform classical computers, but
are currently limited in their capabilities. One such limitation is the
restricted connectivity between qubits, as captured by the hardware's coupling
graph. This limitation poses a challenge for running algorithms that require a
coupling graph different from what the hardware can provide. To overcome this
challenge and fully utilize the hardware, efficient qubit routing strategies
are necessary. In this paper, we introduce line-graph qubit routing, a general
method for routing qubits when the algorithm's coupling graph is a line graph
and the hardware coupling graph is a heavy graph. Line-graph qubit routing is
fast, deterministic, and effective; it requires a classical computational cost
that scales at most quadratically with the number of gates in the original
circuit, while producing a circuit with a SWAP overhead of at most two times
the number of two-qubit gates in the original circuit. We implement line-graph
qubit routing and demonstrate its effectiveness in mapping quantum circuits on
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, both in the required classical wall-clock
time and in the quality of the solution that is found. Line-graph qubit routing
has direct applications in the quantum simulation of lattice-based models and
aids the exploration of the capabilities of near-term quantum hardware.
