Grover search with multiple solution implementation strategy

I am confused about how to implement a strategy for Grover's search with multiple solutions. My goal is to find all $$t$$ solutions in $$N$$ elements. I got this question because I found people used query complexity $$O(\sqrt{Nt})$$ for analyzing algorithms.

There are two conditions: changed Oracle or constant Oracle. If the Oracle is not modified, the cost of finding each solution is $$O(\sqrt{\frac{N}{t}})$$. In this case, the total complexity is $$O(\sqrt{Nt})$$, which makes sense to me. However, if we use a different strategy, that is changing the Oracle so that the Grover's search will not find a found element, the total complexity is $$O(\sqrt{\frac{N}{t}})+O(\sqrt{\frac{N}{t-1}})+...+O(\sqrt{N})$$. This total complexity cannot be bounded by $$O(\sqrt{Nt})$$.

However, there is a problem for a constant Oracle: Suppose we have 10 elements, and 0,1,2,3 are solutions. Firstly, Grover's search returns a true solution (assume 0 in the first round). In the second and the third round, let's assume the subroutine returns 1 and 2, respectively. The problem may occur in the fourth step: The algorithm still returns a value in [0,1,2], so the subroutine believes there is no more solution and stops. Finally, this subroutine only finds 3 solutions instead of 4.

Is there any idea to tackle this problem? I want to get an strategy to get all t solutions in $$O(\sqrt{Nt})$$ time.

• I think the answer of that link is: you can explicitly exclude any items you've previously found by unmarking them in your oracle step. But in my question, this modification will change the Oracle so that the query complexity will be increased to $O(\sqrt{\frac{N}{t}})+O(\sqrt{\frac{N}{t-1}})+...+O(\sqrt{N})$, which does not make sense to me. Oct 31, 2021 at 4:20
• Some confused, I can't see why it's $O(\sqrt{Nt})$, since repeating the algorithm for $t$ times still can't guarantee we can find all the solutions. Are there some references of your statement about $O(\sqrt{Nt})$? Oct 31, 2021 at 9:22
• This paper link, you can see the quantum BFS in Theorem 1. Nov 1, 2021 at 15:50

I think the issue is that the total complexity of the modified oracle can be bounded. The total complexity will be (up to constant factors):

$$\sum_{j=0}^{t-1}\sqrt{\frac{N}{t-j}} = \sum_{i=1}^t \sqrt{\frac{N}{i}}=\sqrt{N}\sum_{i=1}^t \frac{1}{\sqrt{i}}$$

We can approximate the sum by an integral:

$$\sum_{i=1}^t \frac{1}{\sqrt{i}} \approx \int_1^t \frac{1}{\sqrt{x}}dx$$

which integrates to $$2(\sqrt{t}-1)$$. Thus, the total cost is still $$O(\sqrt{Nt})$$.

For the constant oracle, I don't think you can get a guarantee of finding all solutions. But you can repeat $$O(t\log(t))$$ times (for a total cost of $$O(\sqrt{Nt}\log(t))$$) to have a near guarantee that you find all solutions, via the analysis of the coupon collector's problem.

• It makes sense to me. Thanks for comment. Nov 2, 2021 at 13:24
• I think the approximation should be $\int_0^t$ or $\int_1^{t+1}$ instead of $\int_1^t$. Mar 25 at 11:03