Abstract:In the noisy intermediate-scale quantum (NISQ) era, due to hardware coupling constraints, CNOT gates often cannot be executed directly. Additional SWAP gates need to be introduced to map logical qubits to suitable physical locations for ensuring circuit executability. To reduce the additional overhead caused by SWAP operations during traditional qubit mapping, this study proposes the multi-strategy quantum sparrow search algorithm (MQSSA) and applies it to qubit mapping. The qubit linkage count is defined based on the number of non-nearest neighbour (non-NN) CNOT gates acting on the same qubit pair. Combined with the physical spacing of CNOT gates, a linked quantum gate set is defined, and a fitness function is constructed based on the qubit linkage count and SWAP gate number. Simultaneously, the individual with the optimal fitness is defined as the discoverer. A quantum superposition state mechanism is introduced to equip the discoverer with parallel search capabilities, enabling the simultaneous exploration of multiple positions to expand the search space. Furthermore, to avoid falling into local optima, MQSSA introduces Gaussian noise as a follower position update perturbation mechanism, enhancing the ability to jump out of local optima. Additionally, the sentinel mechanism is implemented to maintain search diversity. Experimental results demonstrate that within the t|ket and Qiskit compilers, MQSSA achieves average reductions of 37.5% and 46.6% in SWAP gate counts respectively, alongside average hardware overhead reductions of 13.3% and 13.2% respectively. This indicates the proposed algorithm has more efficient performance in qubit mapping, thereby improving the quality of optimization outcomes.