Impact of hardware connectivity on Grover’s algorithm in NISQ era

Abstract

The quantum search operation as dictated in Grover’s landmark paper had been a crucial area in the study of quantum algorithms. It has become a critical component in many quantum cryptography and computation algorithms and threatens today’s AES security infrastructure. The quadratic speedup provided by Grover’s algorithm is hampered severely due to the presence of a realistic environment. Many studies have analyzed the effect of different noises on Grover’s search algorithm. However, the efficiency of the algorithm also depends on the connectivity of qubits on realistic quantum hardware. This study evaluated the performance of Grover’s algorithm with varying qubit connectivity under the presence of two-qubit depolarizing noise and single-qubit amplitude damping and dephasing noise. Unidirectional and bidirectional variants of nine coupling maps for qubit connectivity were chosen. The analysis has shown that the transpilation efficiency for Grover’s algorithm is deeply sensitive to the connectivity and degree of the hardware, which influences the depth of the circuit. This, in turn, has a measurable effect on the performance of the algorithm on a particular hardware. This study also ranks the favorable coupling maps using the decision-making technique of AHP-TOPSIS. The analysis has shown that grid, hex, and modified star are the most favorable hardware connectivity. The unidirectional linear, ring, star, and full-connected are the worst choices. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.