Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.09268 · Europhysics Letters (EPL)

Complementarity between success probability and coherence in Grover search algorithm

Minghua Pan, Haozhen Situ, Shenggen Zheng

Published May 1, 2022• 12 citations
arXivHTMLPDF

Abstract

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 1 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.

DOI
10.1209/0295-5075/ac7165

Related papers

Tsallis relative $α$ entropy of coherence dynamics in Grover's search algorithm

Linlin Ye, Zhaoqi Wu, Shao-Ming Fei

Quantum coherence plays a central role in Grover's search algorithm. We study the Tsallis relative $α$ entropy of coherence dynamics of the evolved state in Grover's search algorithm. We prove that the Tsallis relative $α$ entropy of coherence decreases with the increase of the success probability, and derive the complementarity relations between the coherence and the success probability. We show that the operator coherence of the first $H^{\otimes n}$ relies on the size of the database $N$, the success probability and the target states. Moreover, we illustrate the relationships between coherence and entanglement of the superposition state of targets, as well as the production and deletion of coherence in Grover iterations.

quant-pharXiv:2604.13910•Communications in Theoretical Physics•Apr 16, 2026•12 citations

Coherence depletion in the Grover quantum search algorithm

Hailong Shi, Siyuan Liu, Xiao-Hui Wang +3 more

We investigate the role of quantum coherence depletion (QCD) in the Grover search algorithm (GA) by using several typical measures of quantum coherence and quantum correlations. By using the relative entropy of coherence measure (${\mathcal{C}}_{r}$), we show that the success probability depends on the QCD. The same phenomenon is also found by using the ${l}_{1}$ norm of coherence measure (${\mathcal{C}}_{{l}_{1}}$). In the limit case, the cost performance is defined to characterize the behavior about QCD in enhancing the success probability of GA, which is only related to the number of searcher items and the scale of the database, regardless of using ${\mathcal{C}}_{r}$ or ${\mathcal{C}}_{{l}_{1}}$. In the generalized Grover search algorithm (GGA), the QCD for a class of states increases with the required optimal measurement time. In comparison, the quantification of other quantum correlations in GA, such as pairwise entanglement, multipartite entanglement, pairwise discord, and genuine multipartite discord, cannot be directly related to the success probability or the optimal measurement time. Additionally, we do not detect pairwise nonlocality or genuine tripartite nonlocality in GA since Clauser-Horne-Shimony-Holt inequality and Svetlichny's inequality are not violated.

arXiv:1610.08656•Physical Review A•Mar 7, 2017•183 citations

Complementary-multiphase quantum search for all numbers of target items

Tan Li, Wan‐Su Bao, He-Liang Huang +7 more

Grover's algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of $\ensuremath{\lambda}$ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where $\ensuremath{\lambda}$ is the fraction of target items in the database. In this paper, we find out that the Grover algorithm can actually apply to the case where one can identify the range that $\ensuremath{\lambda}$ belongs to from a given series of disjoint ranges. However, Grover's algorithm still cannot maintain high success probability when there exist multiple target items. For this problem, we proposed a complementary-multiphase quantum search algorithm in which multiple phases complement each other so that the overall high success probability can be maintained. Compared to the existing algorithms, in the case defined above, our algorithm achieves the following three goals simultaneously: (1) the success probability can be no less than any given value between 0 and 1, (2) the algorithm is applicable to the entire range of $\ensuremath{\lambda}$, and (3) the number of iterations is almost the same as that of Grover's algorithm. Especially compared to the optimal fixed-point algorithm [Phys. Rev. Lett. 113, 210501 (2014)], our algorithm uses fewer iterations to achieve a success probability greater than 82.71%, e.g., when the minimum success probability is required to be 99.25%, the number of iterations can be reduced by 50%.

arXiv:1806.03259•Physical Review A•Dec 6, 2018•4 citations

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•4 citations

Exact results on Quantum search algorithm

Saptarshi Roy Chowdhury, Swarupananda Pradhan

We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.

arXiv:2207.09762•Jul 20, 2022•1 citation

Degeneration of the Grover search algorithm with depolarization in the oracle-box wires

Alexey E. Rastegin, Anzhelika M. Shemet

Grover’s search algorithm and similar techniques are widely used in quantum information science. Communication lines with the so-called oracle are one of inevitable vulnerabilities of quantum search. The impact of localized dephasing and amplitude damping on Grover’s algorithm had already been discussed in recent literature. In this paper, we study the influence of depolarization in the oracle-box wires on the search process. It is shown that even low level of noise is sufficient to degenerate Grover’s algorithm. Complementarity relations between the relative entropy of coherence and the success probability in the presence of depolarization are studied as well.

Modern Physics Letters A•Feb 20, 2023•3 citations
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 1 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.
Tsallis relative ααα entropy of coherence dynamics in Grover's search algorithm
Quantum coherence plays a central role in Grover's search algorithm. We study the Tsallis relative ααα entropy of coherence dynamics of the evolved state in Grover's search algorithm. We prove that the Tsallis relative ααα entropy of coherence decreases with the increase of the success probability, and derive the complementarity relations between the coherence and the success probability. We show that the operator coherence of the first H⊗nH^{\otimes n}H⊗n relies on the size of the database NNN, the success probability and the target states. Moreover, we illustrate the relationships between coherence and entanglement of the superposition state of targets, as well as the production and deletion of coherence in Grover iterations.
We investigate the role of quantum coherence depletion (QCD) in the Grover search algorithm (GA) by using several typical measures of quantum coherence and quantum correlations. By using the relative entropy of coherence measure (Cr{\mathcal{C}}_{r}Cr​), we show that the success probability depends on the QCD. The same phenomenon is also found by using the l1{l}_{1}l1​ norm of coherence measure (Cl1{\mathcal{C}}_{{l}_{1}}Cl1​​). In the limit case, the cost performance is defined to characterize the behavior about QCD in enhancing the success probability of GA, which is only related to the number of searcher items and the scale of the database, regardless of using Cr{\mathcal{C}}_{r}Cr​ or Cl1{\mathcal{C}}_{{l}_{1}}Cl1​​. In the generalized Grover search algorithm (GGA), the QCD for a class of states increases with the required optimal measurement time. In comparison, the quantification of other quantum correlations in GA, such as pairwise entanglement, multipartite entanglement, pairwise discord, and genuine multipartite discord, cannot be directly related to the success probability or the optimal measurement time. Additionally, we do not detect pairwise nonlocality or genuine tripartite nonlocality in GA since Clauser-Horne-Shimony-Holt inequality and Svetlichny's inequality are not violated.
Grover's algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of $\ensuremath{\lambda}$ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where $\ensuremath{\lambda}$ is the fraction of target items in the database. In this paper, we find out that the Grover algorithm can actually apply to the case where one can identify the range that $\ensuremath{\lambda}$ belongs to from a given series of disjoint ranges. However, Grover's algorithm still cannot maintain high success probability when there exist multiple target items. For this problem, we proposed a complementary-multiphase quantum search algorithm in which multiple phases complement each other so that the overall high success probability can be maintained. Compared to the existing algorithms, in the case defined above, our algorithm achieves the following three goals simultaneously: (1) the success probability can be no less than any given value between 0 and 1, (2) the algorithm is applicable to the entire range of $\ensuremath{\lambda}$, and (3) the number of iterations is almost the same as that of Grover's algorithm. Especially compared to the optimal fixed-point algorithm [Phys. Rev. Lett. 113, 210501 (2014)], our algorithm uses fewer iterations to achieve a success probability greater than 82.71%, e.g., when the minimum success probability is required to be 99.25%, the number of iterations can be reduced by 50%.
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.
Grover’s search algorithm and similar techniques are widely used in quantum information science. Communication lines with the so-called oracle are one of inevitable vulnerabilities of quantum search. The impact of localized dephasing and amplitude damping on Grover’s algorithm had already been discussed in recent literature. In this paper, we study the influence of depolarization in the oracle-box wires on the search process. It is shown that even low level of noise is sufficient to degenerate Grover’s algorithm. Complementarity relations between the relative entropy of coherence and the success probability in the presence of depolarization are studied as well.