Complementarity between success probability and coherence in Grover search algorithm

¹ Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology Guilin 541004, China
² Department of Physics, Tsinghua University - Beijing 100084, China
³ College of Mathematics and Informatics, South China Agricultural University - Guangzhou 510642, China
⁴ Peng Cheng Laboratory - Shenzhen 518055, China

^(a) panmh@guet.edu.cn
^(b) situhaozhen@gmail.com
^(c) zhengshg@pcl.ac.cn

Received: 6 April 2022
Accepted: 19 May 2022

Abstract

Coherence plays a very important role in Grover search algorithm (GSA). In this paper, we define the normalization coherence , where C is a coherence measurement. By virtue of the constraint of large N and Shannon's maximum entropy principle, a surprising complementary relationship between the coherence and the success probability of GSA is obtained. Namely, , where C is in terms of the relative entropy of coherence and l₁ norm of coherence, t is the number of the search iterations in GSA. Moreover, the equation holds no matter either in ideal or noisy environments. Considering the number of qubits is limited in the recent noisy intermediate-scale quantum (NISQ) era, some exact numerical calculation experiments are presented for different database sizes N with different types of noises. The results show that the complementarity between the success probability and the coherence almost always holds. This work provides a new perspective to improve the success probability by manipulating its complementary coherence, and vice versa. It has an excellent potential for helping quantum algorithms design in the NISQ era.