  We propose a novel hierarchical qubit mapping and routing algorithm. First, a
circuit is decomposed into blocks that span an identical number of qubits. In
the second stage permutation-aware synthesis (PAS), each block is optimized and
synthesized in isolation. In the third stage a permutation-aware mapping (PAM)
algorithm maps the blocks to the target device based on the information from
the second stage. Our approach is based on the following insights: (1)
partitioning the circuit into blocks is beneficial for qubit mapping and
routing; (2) with PAS, any block can implement an arbitrary input-output qubit
mapping that reduces the gate count; and (3) with PAM, for two adjacent blocks
we can select input-output permutations that optimize each block together with
the amount of communication required at the block boundary. Whereas existing
mapping algorithms preserve the original circuit structure and only introduce
"minimal" communication via inserting SWAP or bridge gates, the PAS+PAM
approach can additionally change the circuit structure and take full advantage
of hardware-connectivity. Our experiments show that we can produce
better-quality circuits than existing mapping algorithms or commercial
compilers (Qiskit, TKET, BQSKit) with maximum optimization settings. For a
combination of benchmarks we produce circuits shorter by up to 68% (18% on
average) fewer gates than Qiskit, up to 36% (9% on average) fewer gates than
TKET, and up to 67% (21% on average) fewer gates than BQSKit. Furthermore, the
approach scales, and it can be seamlessly integrated into any quantum circuit
compiler or optimization infrastructure.
