Complementary-multiphase quantum search for all numbers of target items

Grover's algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of $\lambda$ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where $\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 $\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 $\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%.

Figure 1

Inclusion relationships among Cases-KPV, KIGR, and KZO. In Case-KPV, $\lambda$ is precisely known. In Case-KIGR, the range that $\lambda$ belongs to can be identified from a given series of disjoint ranges. In Case-KZO, one knows that $0<\lambda <1$.

Figure 2

The success probability $P$ as a function of the fraction of target items $\lambda$. The black dotted, blue dashed, red solid, and green dashed-dotted curves correspond to the original Grover algorithm [1], the optimal fixed-point algorithm [4], our proposed algorithm, and the complementary-multiphase algorithm with only one iteration [34], respectively. The task is to achieve success probability no less than $P_{cri}=90\%$ for all $\lambda \ge {\lambda }_0={10}^{-2}$.

Figure 3

The number of iterations as a function of the fraction of target items. The red solid and blue dashed curves correspond to our algorithm and the Grover algorithm [1], respectively. Note that, to see the range of small $\lambda$ more clearly, the range of large $\lambda$ is compressed, with a “$//$” on the x-axis marking the boundary.

Figure 4

The schematic of success probability $P$ as a function of the fraction of target items $\lambda$. The black solid, blue dashed, and red dashed-dotted curves correspond to ${\varphi }_{k,n_k-2},{\varphi }_{k,n_k-1}$, and ${\varphi }_{k,n_k}$, respectively, where ${\lambda }_{k,1}^{\varphi ,max}$ defined by Eq. (29), and ${\lambda }_{k=1,1}^{\varphi ,min}$ defined by Eq. (30) represent the local maximum point and minimum point of $P_k^{\varphi }\left(\lambda \right)$, respectively.

Figure 5

The schematic of success probability $P$ as a function of the fraction of target items $\lambda$ for $n_k=1$ and $k\ge 2$. The black solid, blue dashed, and red dashed-dotted curves correspond to ${\varphi }_{k,1},{\varphi }_{k,1}^{\prime }$, and ${\varphi }_{k,1}^{\prime \prime }$, respectively, which satisfy Eqs. (G1), (G3), and (G5), separately.