Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis*

We propose a novel hierarchical qubit mapping and routing framework. First, a circuit is decomposed into blocks that span an identical number of qubits. In the second permutation-aware synthesis (PAS) stage, each block is synthesized with different input and output permutations and different topologies. The third stage is a permutation-aware mapping (PAM) algorithm that maps and routes the blocks based on the permutation information. Our approach is based on the following insight: 1) with PAS, any block can implement an arbitrary input → output qubit mapping  (e.g. q0 → q1) that minimizes its communication; and 2) with PAM, for two adjacent blocks we can select input-output permutations that optimize each block together with the amount of communication required at a block boundary. While existing mapping algorithms only introduce ''minimal''  communication via inserting SWAP or bridge gates, the PAS+PAM approach can additionally remove any spurious communication. 

Our experiments show that we can produce better quality circuits than existing mapping algorithms or commercial compilers (Qiskit, Tket). For a combination of benchmarks, we significantly reduce the two-qubit gate count. Furthermore, the approach scales and it can be seamlessly integrated into any quantum circuit compiler or optimization infrastructure.