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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EffectiveQM</i>. First, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EffectiveQM</i> proposes a new mode-aware search strategy to alleviate the challenge of being trapped in local optima, where local search typically suffers. Moreover, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EffectiveQM</i> 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, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EffectiveQM</i> can effectively determine the appropriate operation to be performed. Extensive experiments on a diverse collection of logical circuits and 6 NISQ devices demonstrate that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EffectiveQM</i> can generate physical circuits with significantly fewer inserted auxiliary gates than current state-of-the-art QMP algorithms, indicating that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EffectiveQM</i> greatly advances the state of the art in QMP solving.