Qubit Mapping: The Adaptive Divide-and-Conquer Approach
The qubit mapping problem (QMP) focuses on the mapping and routing of qubits
in quantum circuits so that the strict connectivity constraints imposed by
near-term quantum hardware are satisfied. QMP is a pivotal task for quantum
circuit compilation and its decision version is NP-complete. In this study, we
present an effective approach called Adaptive Divided-And-Conqure (ADAC) to
solve QMP. Our ADAC algorithm adaptively partitions circuits by leveraging
subgraph isomorphism and ensuring coherence among subcircuits. Additionally, we
employ a heuristic approach to optimise the routing algorithm during circuit
partitioning. Through extensive experiments across various NISQ devices and
circuit benchmarks, we demonstrate that the proposed ADAC algorithm outperforms
the state-of-the-art method. Specifically, ADAC shows an improvement of nearly
50\% on the IBM Tokyo architecture. Furthermore, ADAC exhibits an improvement
of around 18\% on pseudo-realistic circuits implemented on grid-like
architectures with larger qubit numbers, where the pseudo-realistic circuits
are constructed based on the characteristics of widely existing realistic
circuits, aiming to investigate the applicability of ADAC. Our findings
highlight the potential of ADAC in quantum circuit compilation and the
deployment of practical applications on near-term quantum hardware platforms.
Yunqi Huang Xiangzhen Zhou Fanxu Meng Sanjiang Li