An optimized sparrow search algorithm for quantum circuit mapping

Abstract In the Noisy Intermediate-Scale Quantum (NISQ) era, owing to the limitation of quantum hardware coupling constraints, only physically directly connected qubits can realize interaction. For CNOT gates that do not satisfy the coupling conditions, extra SWAP gates need to be inserted to adjust the qubit positions to ensure the executability of the quantum circuit. To reduce the extra overhead due to SWAP gates, this paper proposes a Leveraging Strategy-Driven Quantum Sparrow Search Algorithm (LS-QSSA) and applies it to quantum circuit mapping. LS-QSSA introduces the concept of qubit coupling count, and combines it with the SWAP gate overhead to jointly construct the fitness function. In the individual selection stage, the top 20% of individuals in terms of fitness value are set as “discoverers, ” which are able to explore multiple solution space locations at the same time through the introduction of quantum representations, thus expanding the search space. To enhance the capability of escaping local optima, LS-QSSA introduces a Gaussian noise mechanism to perturb the follower positions. Experimental results demonstrate that LS-QSSA achieves an approximate reduction of 36. 4% and 47. 5% in the quantity of SWAP gates, and around 13. 1% and 13. 2% in hardware gate count overhead, when compared with the tket and Qiskit compilers, respectively.