Locality-aware Qubit Routing for the Grid Architecture

Understand

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.