Towards Effective Local Search for Qubit Mapping

In the era of noisy intermediate-scale quantum (NISQ), a quantum logical circuit must undergo certain compilation before it can be used on a NISQ device, subject to connectivity constraints posed by NISQ devices. During compilation, numerous auxiliary quantum gates are inserted, but a circuit with too many is unreliable, necessitating gate minimization. This requirement gives rise to the qubit mapping problem (QMP), an NP-hard optimization problem that is critical in quantum computing. This work proposes a novel and effective local search algorithm dubbed EffectiveQM. First, EffectiveQM proposes a new mode-aware search strategy to alleviate the challenge of being trapped in local optima, where local search typically suffers. Moreover, EffectiveQM introduces a novel potential-guided scoring function, which can thoroughly quantify the actual benefit brought by an operation of inserting auxiliary gates. By incorporating the potential-guided scoring function, EffectiveQM can effectively determine the appropriate operation to be performed. Extensive experiments on a diverse collection of logical circuits and 6 NISQ devices demonstrate that EffectiveQM can generate physical circuits with significantly fewer inserted auxiliary gates than current state-of-the-art QMP algorithms, indicating that EffectiveQM greatly advances the state of the art in QMP solving.