Complementarity between Success Probability and Coherence in Grover Search Algorithm

Abstract

Coherence plays a very important role in Grover search algorithm (GSA). In this paper, we define the normalization coherence N(C), where C is a coherence measurement. In 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, P_s(t)+N(C(t))\simeq 1, where C is in terms of the relative entropy of coherence and l_1 norm of coherence, t is the number of the search iterations in GSA. Moreover, the equation holds no matter 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 complementary between the success probability and the coherence almost always hold. 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.

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Fixed-point quantum search with an optimal number of queries
• Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
• Noise effect on Grover algorithm
• Scale invariance of entanglement dynamics in Grover's quantum search algorithm
• A brief introduction to quantum algorithms
• Quantum search degeneration under amplitude noise in queries to the oracle
• Performance of Grover's search algorithm with diagonalizable collective noises

Cited by in corpus (7)

• Tsallis relative $\alpha$ entropy of coherence dynamics in Grover's search algorithm
• Cohering and decohering power of massive scalar fields under instantaneous interactions
• Coherence dynamics in quantum algorithm for linear systems of equations
• Coherence Fraction in Grover Search Algorithm
• Coherence and entanglement dynamics in Shor's algorithm
• Basis-independent Coherence in Noninertial Frames
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm