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 dubbedEffectiveQM. First,EffectiveQMproposes a new mode-aware search strategy to alleviate the challenge of being trapped in local optima, where local search typically suffers. Moreover,EffectiveQMintroduces 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,EffectiveQMcan effectively determine the appropriate operation to be performed. Extensive experiments on a diverse collection of logical circuits and 6 NISQ devices demonstrate thatEffectiveQMcan generate physical circuits with significantly fewer inserted auxiliary gates than current state-of-the-art QMP algorithms, indicating thatEffectiveQMgreatly advances the state of the art in QMP solving.