Robust Quantum Search with Uncertain Number of Target States

Abstract

The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given $\lambda =\sqrt{M/N}$, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity $O\left(\sqrt{N}\right)$ as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio $M/N$. In particular, for a database with an uncertainty in the ratio $\frac{M\pm \sqrt{M}}{N}$, our algorithm will find the target states with a success rate no less than $96\%$.

1. Introduction

The quantum search algorithm is one of the most significant quantum algorithms [1]. Compared with classical search algorithms, quantum search algorithms exhibit quadratic speedup [2,3]. This demonstrates the superiority of quantum computing over classical computing. Grover proposed the first quantum search algorithm [1,4], which can find M marked items from an unstructured database with N items by querying only $O\left(\sqrt{N/M}\right)$ times [5,6]. If the measurements are made after the optimal iterations, Grover’s algorithm will have a success rate $P_{max}={sin}^2\left[(2j_{op}+1)\beta \right]$ to find the marked items, where $\beta =arcsin\sqrt{M/N}$ and $j_{op}=[(\pi /2-\beta )/\left(2\beta \right)]$ is the number of optimal Grover iterations. If $(2j_{op}+1)\beta \approx \pi /2$, the maximum probability approaches 1, which means that the Grover’s algorithm usually has a high success rate if the dimension of the quantum database is very large.

There have been several important developments in the Grover’s algorithm. In some situations, such as structured search [7], where the success rate is the product of the success rates of individual search, high success rate in each individual search is critical; especially, when dimensions are not so large, the standard Grover’s algorithm will not perform well. In order to solve this problem, some modified search algorithms have been proposed [8,9,10,11,12]. The Grover–Long algorithm [11], one of these improved algorithms, has been proved to be the simplest and most optimal [13,14]. This algorithm achieves 100% success rate, whereas Grover’s algorithm can only achieve 100% success rate when finding one out of four.

In both the original Grover and improved versions of Grover’s algorithm, one needs to know the exact number of marked states in advance. Therefore, if the exact number is not known, these algorithms can not determine when to stop [15]. Spatial search [16,17,18] is one of the methods to solve this problem. Fixed-point search algorithm is another method to solve this problem. By constructing the recursively searching operator, the ratio of marked state always amplifies after each search, the $\pi /3$ fixed-point search algorithm of Grover [19], for example. In this algorithm, each search approaches the marked states monotonously, but the cost of monotony is large in this algorithm, and the quadratic speedup of standard Grover’s algorithm is lost.

The Yoder–Low–Chung algorithm [20] was proposed to improve the performance of fixed-point algorithms on wide ranges of $M/N$. It retains the quadratic speedup advantage of quantum search, and it achieves the fixed-point property at the same time. It also solves overcooking problem, but the success rate of which is not monotonically increasing as in the $\pi /3$ algorithm. The error is bounded by a tunable parameter $\delta \in [0,1]$ over an ever-widening range of $M/N$, but the phases in each search step need to be calculated by solving a hype-trigonometric equation.

In this paper, we develop a robust quantum search algorithm, based on the Grover–Long algorithm, which overcomes the problem of not knowing the exact ratio $M/N$ in advance. This algorithm has the advantage of easiness in constructing the search operators, and also certain degrees of “fixed-point” properties. Namely, it enjoys a high success rate over a wide range of the ratio of $M/N$. In our algorithm, we do not need to know the exact number of marked states, but rather an approximate number in the range $\left[{\lambda }_0,{\lambda }_0+\Delta \right]$ of the ratio $\lambda =M/N$. The error of our algorithm is bounded by a parameter $\delta \in [0,1]$ related to the $\Delta /{\lambda }_0$. Specifically, searching operators in our algorithm are determined by the lower bound ${\lambda }_0$. After $J+1-J_{\mathcal{D}}$ iterations, the probability of success is larger than $1-{\delta }^2$, where $J_{\mathcal{D}}$ is denoted as $⌈\left(\frac{1}{2\sqrt{{\lambda }_0+\Delta }}+\frac{4}{\pi }\right)\delta ⌉$.

This paper is organized as follows. First of all, the Grover–Long algorithm is summarized. Secondly, the relationship between the success rate of Grover–Long algorithm and iterative steps is studied, and the relation between iteration number and success rate is given. Thirdly, we propose a robust search version of Grover–Long algorithm and show its high tolerance to the ratio $M/N$. The comparison is then made with the Yoder–Low–Chuang algorithm, standard Grover’s algorithm, and the Grover $\pi /3$ fixed-point algorithm, respectively. Finally, we prove that our algorithm can find the target state with a success rate of more than $96\%$ from an database, with only an estimate of M, in the range between $\{M-\sqrt{M},M+\sqrt{M}\}$, which can be carried out using the quantum counting algorithm [21,22].

2. Overview of Grover–Long Algorithm

The Grover–Long algorithm can extract M marked items from an unstructured database with N items by querying $O\left(\sqrt{N/M}\right)$ times. First, from the given ratio $M/N$, parameter $\beta$ can be calculated:

$$\beta =arcsin\sqrt{\frac{M}{N}},$$

(1)

which is further used to determine the value of search steps $j_{op}=⌊\frac{\pi -2\beta }{4\beta }⌋$. The square brackets here represent the floor function. One can set the number of iteration as

$$J\ge j_{op}.$$

(2)

Then, the phases in the search algorithm are calculated by

$$\varphi =2arcsin\left(\frac{sin\frac{\pi }{4J+6}}{sin\beta }\right).$$

(3)

Next, the oracle operator can be expressed as

$$I_{\tau }=I+\left(e^{i\varphi }-1\right)|\tau \rangle \langle \tau |,$$

(4)

where $|\tau \rangle$ denotes as the superposition of M marked states, and the phase shifting operator for the $|0\rangle$ state is

$$I_0=I+\left(e^{i\varphi }-1\right)|0\rangle \langle 0|.$$

(5)

Finally, the Grover–Long operator in each iteration is

$$Q=-H{I}_{0}H{I}_{\tau },$$

(6)

where H is the Hadamard gate. After $J+1$ steps of iterations, one can obtain the marked states with certainty by measurement. When $\varphi =\pi$, we recover the original Grover’s algorithm, which usually does not find the marked states with certainly.

The quantum search algorithm can be described using the SO(3) picture [11,23] instead of SU(2). In this picture, the quantum search operator in Equation (6) corresponds to a rotation in three-dimensional space with the following matrix form

$$R_Q=\left[\begin{array}{ccc}{R}_{11}\hfill & R_{12}\hfill & R_{13}\hfill \\ R_{21}\hfill & R_{22}\hfill & R_{23}\hfill \\ R_{31}\hfill & R_{32}\hfill & R_{33}\hfill \end{array}\right],$$

(7)

where the entries of the matrix $R_Q$ are calculated in [11]. The states are rotated along the $\overrightarrow{l}$ axis

$$\overrightarrow{l}=\left[\begin{array}{c}cos\frac{\varphi }{2}\\ sin\frac{\varphi }{2}\\ cos\frac{\varphi }{2}tan\beta \end{array}\right],$$

(8)

with an angle

$$\alpha =4arcsin\left[sin\left(\frac{\varphi }{2}\right)sin\beta \right]=\frac{2\pi }{2J+3}.$$

(9)

In this picture, the state vector $|\psi \rangle =(a+bi)|\tau \rangle +(c+di)|\overline{\tau }\rangle$ is represented as

$${\overrightarrow{r}}_{\psi }=\langle \psi |\overrightarrow{\sigma }|\psi \rangle =\left[\begin{array}{c}2(ac+bd)\\ 2(-bc+ad)\\ a^2+b^2-c^2-d^2\end{array}\right],$$

(10)

where $\overrightarrow{\sigma }={\sigma }_x\overrightarrow{i}+{\sigma }_y\overrightarrow{j}+{\sigma }_z\overrightarrow{k}$ and $\overrightarrow{i}$, $\overrightarrow{j}$, $\overrightarrow{k}$ are the unit vector along the x, y, z axis. The initial state $|{\psi }_i\rangle$ and the marked state $|\tau \rangle$ are represented by

$${\overrightarrow{r}}_i=\left[\begin{array}{c}sin\left(2\beta \right)\\ 0\\ -cos\left(2\beta \right)\end{array}\right],{\overrightarrow{r}}_f=\left[\begin{array}{c}0\hfill \\ 0\hfill \\ 1\hfill \end{array}\right].$$

(11)

Each search step is a rotation of ${\overrightarrow{r}}_{\psi }$ toward ${\overrightarrow{r}}_f$. The SO(3) description of the Grover–Long algorithm is pictured as a circle in Figure 1.

3. Relationship between the Success Rate and Searching Iterations

During each search step of the Grover–Long algorithm, state ${\overrightarrow{r}}_{\psi }=\overline{OA}$ rotates toward ${\overrightarrow{r}}_f=\overline{OB}$, which is described geometrically in Figure 1. In other words, this process is point A moving to point B on the blue circle $\odot r_0$. In this picture, the probability of finding the marked state is $(z_A+1)/2$ [11], where $z_A$ is the Z component of point A. Thus, if one wants to find a marked state with a probability greater than $1-{\delta }^2$, point A of the segment $\overline{r_{o}A}$ must rotate into the arc $\stackrel{⌢}{CD}$, where point C and point D are the intersections of the circle $\odot r_o$ and the red error circle: $x^2+y^2+{(1-2{\delta }^2)}^2=1$. If we can calculate the arc length $\stackrel{⌢}{CD}$, then we obtain a reasonable number of iterations.

For this reason, we focus on the spherical cone, which consists of the unit sphere and the red circle. It is shown in Figure 2. The segment $\overline{BC}$ in Figure 2 is a segment from point $B(0,0,1)$ to point C on the red error circle. In Figure 2, $\overline{OD}=1-2{\delta }^2$, $\overline{OC}=1$, $\overline{BD}=2{\delta }^2$. The following relationship holds:

$$\begin{array}{cc}\hfill \overline{CD}& =\sqrt{{\overline{OC}}^2-{\overline{OD}}^2}\hfill \\ & =\sqrt{1-{(1-2{\delta }^2)}^2}=\sqrt{4{\delta }^2-4{\delta }^4},\hfill \end{array}$$

(12)

$$\begin{array}{cc}\hfill \overline{BC}& =\sqrt{{\overline{CD}}^2+{\overline{BD}}^2}\hfill \\ & =\sqrt{4{\delta }^2-4{\delta }^4+4{\delta }^4}=2\delta \hfill \end{array}$$

(13)

The half length of arc $\stackrel{⌢}{CD}$ is approximated to $\overline{BC}=2\delta$.

Next, we find the radius of the blue circle $\odot r_o$. As shown in Figure 3, point E is the middle of the segment $\overline{AB}$.

In Figure 3, $\angle AOB=\pi -2\beta$, $\overline{OA}=1$, and $\angle A{r}_{o}E=\frac{\angle A{r}_{o}B}{2}=\frac{J+1}{2}\alpha =\frac{(J+1)\pi }{2J+3}$. In $△AOE$ and $△AE{r}_o$:

$$\begin{array}{cc}\hfill \overline{AE}& =\sin \frac{\angle AOB}{2}=\sin \frac{\pi -2\beta }{2}=\cos \beta ,\hfill \end{array}$$

(14)

$$\begin{array}{cc}\hfill \hspace{1em}\hspace{1em}\overline{A{r}_o}& =\overline{AE}\csc \angle A{r}_{o}E=\cos \beta \csc \left(\frac{J+1}{2J+3}\pi \right).\hfill \end{array}$$

(15)

Thus, the number of iterations on the arc length $\stackrel{⌢}{BC}$ is

$$\begin{array}{cc}\hfill \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} J_{\delta }& =⌈\frac{\stackrel{⌢}{BC}}{\overline{A{r}_o}·\alpha }⌉\simeq ⌈\frac{\overline{BC}}{\overline{A{r}_o}·\alpha }⌉\hfill \\ \hfill & =⌈\frac{(2J+3)\delta }{\pi }\sec \beta \sin \left(\frac{J+1}{2J+3}\pi \right)⌉\hfill \end{array}$$

(16)

$$\begin{array}{cc}\hfill & \simeq ⌈\left(\frac{\csc \beta }{2}+\frac{4}{\pi }\right)\delta ⌉,\hfill \end{array}$$

(17)

where ⌈⌉ denotes ceil function. Therefore, after several iterations with a number in $[J+1-J_{\delta },J+1+J_{\delta }]$, the success rate in $[1-{\delta }^2,1]$ will be achieved.

We show the relationship between $1/\lambda$ and the minimum number of queries for a given success rate in Figure 4, which means that if the desired rate of success is not high, the number of queries is correspondingly reduced.

4. Robust Quantum Search with Uncertain Number of Targets

Now, consider the situation where the ratio $M/N$ is not known. Our goal is to find the marked state with high success. Here, we propose a robust search version of the Grover–Long algorithm. In our algorithm, the error is bounded by a parameter $\delta$ over $\Delta /{\lambda }_0$. In fact, our algorithm degenerates to the original Grover–Long algorithm if $\Delta =0$. We proceed our algorithm as follows. The initial state is prepared to the superposition state $|s\rangle$. Then, we find out the target state $|T\rangle$ with success probability higher than $1-{\delta }^2$, in which the overlap $\langle s|T\rangle =\sqrt{\lambda }{e}^{i\xi }$ is nonzero ($\xi$ is the phase difference between $|s\rangle$ and $|T\rangle$) and $\delta \in [0,1]$. We provide the oracle operator $I_{\tau }$ which will flip the ancilla qubit if it matches the target state, that is, $I_{\tau }|T\rangle |a\rangle =|T\rangle |a\oplus 1\rangle$ for $a=\tau$ and $I_{\tau }|\overline{T}\rangle |a\rangle =|\overline{T}\rangle |a\rangle$ for $a\ne \tau$, while $|T\rangle$ are orthogonal to $|\overline{T}\rangle$. Next, we prove how to extract $|\overline{T}\rangle$ by querying $J+1-J_{\mathcal{D}}$ times with the successful probability higher than $1-{\delta }^2$. This algorithm is shown as follows.

Suppose there is a database without exact $\lambda$ but, rather, its upper and lower bounds are denoted as ${\lambda }_0\le \lambda \le {\lambda }_0+\Delta$. If we plug the lower bound ${\lambda }_0$ as the “overlap” into the Grover–Long algorithm, we will obtain

$${\beta }_0=arcsin\left[\sqrt{{\lambda }_0}\right]\le arcsin\left[\sqrt{\lambda }\right]=\beta ,$$

(18)

then

$$J=j_{o{p}_0}=⌊\frac{\pi -2{\beta }_0}{4{\beta }_0}⌋\ge ⌊\frac{\pi -2\beta }{4\beta }⌋=j_{op},$$

(19)

which obeys Equation (2), that $J\ge j_{op}$. Thus, $J+1$ can be chosen as the number of iterations in Grover–Long algorithm, but when plugging J and ${\beta }_0$ into Equation (3), we will not obtain the right matching phase. Thus, we will not obtain the right rotation angle $\alpha$ in Equation (9) for each iteration along the axis $\overrightarrow{l}$ in Equation (10). Instead, we will obtain

$$\begin{array}{cc}\hfill {\alpha }_0& =4arcsin\left[sin\left(\frac{{\varphi }_0}{2}\right)sin\beta \right]\hfill \\ & =4arcsin\left[sin\left(\frac{\pi }{4J+6}\right)\sqrt{\frac{\lambda }{{\lambda }_0}}\right]\hfill \\ & \le \frac{\pi }{2J+3}+tan\left(\frac{\pi }{4J+6}\right)\frac{\Delta }{2{\lambda }_0}.\hfill \end{array}$$

(20)

The angle difference $d\alpha$ between ${\alpha }_0$ and $\alpha$ is

$$d\alpha ={\alpha }_0-\alpha \le tan\left(\frac{\pi }{4J+6}\right)\frac{\Delta }{2{\lambda }_0}.$$

(21)

The total rotation angle difference is

$$\begin{array}{cc}\hfill \mathcal{D}\alpha & =(J+1)d\alpha \hfill \end{array}$$

(22)

$$\begin{array}{cc}\hfill & \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\le (J+1)tan\left(\frac{\pi }{4J+6}\right)\frac{\Delta }{2{\lambda }_0}.\hfill \end{array}$$

(23)

The angle $\mathcal{D}\alpha$ is the overcooked angle $\angle CoB$ or arc $\stackrel{⌢}{CB}$, shown in Figure 2. We define this overcook as $2\delta$:

$$0\le \mathcal{D}\alpha \le (J+1)tan\left(\frac{\pi }{4J+6}\right)\frac{\Delta }{2{\lambda }_0}=2\delta .$$

(24)

We then reduce the number of iterations in order to improve the success rate. The relation between the number of iterations and the error is given by Equation (16). Thus, the reduced number of iterations is

$$\begin{array}{cc}\hfill J_{\delta }& =⌈\left(\frac{csc\beta }{2}+\frac{4}{\pi }\right)\delta ⌉\hfill \\ & \ge ⌈\left(\frac{csc\left(arcsin\sqrt{{\lambda }_0+\Delta }\right)}{2}+\frac{4}{\pi }\right)\delta ⌉\hfill \end{array}$$

(25)

$$=⌈\left(\frac{1}{2\sqrt{{\lambda }_0+\Delta }}+\frac{4}{\pi }\right)\delta ⌉=J_{\mathcal{D}}$$

(26)

which drives the final state into the interval of arc $\stackrel{⌢}{C^{\prime }B}$ instead of $\stackrel{⌢}{CB}$, so the success rate of the final search is greater than $1-{\delta }^2$.

The flowchart of our Algorithm 1 is listed as follows:

Algorithm 1 Robust quantum search with uncertain number of targets.

for a given database, just know the lower bound ${\lambda }_0$ and upper bound ${\lambda }_0+\Delta$ of $\lambda =M/N$, (${\lambda }_0\le \lambda \le {\lambda }_0+\Delta$). Begin Calculate $\beta =\arcsin \left(\sqrt{{\lambda }_0}\right)$ Calculate $J=⌊\left[\right(\pi /2-\beta )/(2\beta \left)\right)]⌋$ Calculate $\varphi =2arcsin\left(\frac{sin\left(\frac{\pi }{4J+6}\right)}{sin\beta }\right)$ Calculate $\delta =(J+1)tan\left(\frac{\pi }{4J+6}\right)\frac{\Delta }{4{\lambda }_0}$ Calculate $J_{\mathcal{D}}=⌈\left(\frac{1}{2\sqrt{{\lambda }_0+\Delta }}+\frac{4}{\pi }\right)\delta ⌉$ Obtain the search operator: $I_{\tau }=I+\left(e^{i\varphi }-1\right)|\tau \rangle \langle \tau |$ $I_0=I+\left(e^{i\varphi }-1\right)|0\rangle \langle 0|$ $Q=-H{I}_{0}H{I}_{\tau }$ Implement the search operator Q on the initial state $|{\psi }_i\rangle$ for $J+1-J_{\mathcal{D}}$ times. Make measurement of the final state and one will find out the marked state with the probability greater than $1-{\delta }^2$. End

Compared with other algorithms, our algorithm maintains quadratic speedup. As shown in Figure 5, our algorithm and Yoder–Low–Chuang algorithm have the same query complexity $O\left(\sqrt{1/\lambda }\right)$ as the standard Grover’s algorithm. Under the condition of output success rate greater than $1-{\delta }^2=0.96$, our algorithm makes eight queries while the Yoder–Low–Chuang algorithm makes 10 queries and the $\pi /3$-algorithm makes 160 queries for $1/{\lambda }_0=100$. For $1/{\lambda }_0=4000$, our algorithm makes 46 queries while the Yoder–Low–Chuang algorithm makes 64 queries and the $\pi /3$-algorithm makes 6437 queries. For $1/{\lambda }_0=$ 10,000, our algorithm makes 72 queries while the Yoder–Low–Chuang algorithm makes 100 queries and the $\pi /3$-algorithm makes 16,094 queries. Both our algorithm and the Yoder–Low–Chuang algorithm have the same query complexity $O\left(\sqrt{1/\lambda }\right)$ as the standard Grover’s algorithm, while the query complexity of $\pi /3$-algorithm is scaled as $1/\lambda$.

5. Discussions

In our algorithm, the infimum bound of the success rate is described by Equation (24). The infimum bound of the success rate is related to $\Delta /{\lambda }_0$. In Figure 6, we show the relationship between the lower success rate and the overlap rate at different uncertainty $\Delta$. When the uncertainty is zero, $100\%$ success rate will be achieved every time, and our algorithm degrades to the standard Grover–Long algorithm. The curve increases sharply with the increase of $\lambda$, and the success rate is above $80\%$ when the uncertainty is double $\lambda$. When the uncertainty is the same order as $\lambda$, one can still achieve a high success rate, as high as $95\%$.

Therefore, our algorithm has a high tolerance to the uncertainty of the ratio $\lambda =M/N$. In order to see the performance of the robustness of our algorithm clearly, especially when the overlap $\lambda$ is small, we provide Figure 7, which shows the relationship between probability and $1/\lambda$. By taking $1/{\lambda }_0$ to infinity, one can see that when $\Delta$ equals zero, our algorithm degrades to the original Grover–Long algorithm. For $\Delta$ equals to $0.8{\lambda }_0$, the success rate of our algorithm exceeds $97\%$, and our algorithm has a success rate of more than $90\%$ when $\Delta$ equals $1.6{\lambda }_0$, and a $78\%$ success rate when $\Delta$ equals $2.4{\lambda }_0$. Even if $\Delta$ equals 3.2${\lambda }_0$, our algorithm still has success rates above 60%.

In the worst-case scenario, one knows nothing about the rate $M/N$. Then, one has to run the quantum counting algorithm to estimate M, which will have an uncertainty $\sqrt{M}$. Our algorithm works well in this case, with a success rate above $96\%$ and keeping the total $O\left(\sqrt{N}\right)$ query complexity as in Grover’s algorithms. After running the quantum counting algorithm, one obtains the ratio with uncertainty, that is $\left(M\pm \sqrt{M}\right)/N$. Thus, $\Delta ={\lambda }_0/\sqrt{M}\le {\lambda }_0$. Plugging this value into Equation (24), the result shows that the success rate of this algorithm is higher than $96\%$.

Our algorithm can be used as a subroutine in any case where amplitude amplification [8] or Grover search are used [24,25,26,27].

In summary, we propose a robust quantum search algorithm with both the advantage of simple search operators, and high success rate over a wide range of $M/N$ values. Therefore, it provides many potential applications [28,29,30,31,32] in future quantum computing.