2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ This link might be helpful. $\endgroup$
    – narip
    Oct 31, 2021 at 3:32
  • $\begingroup$ 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. $\endgroup$
    – Jiawei Ren
    Oct 31, 2021 at 4:20
  • $\begingroup$ 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})$? $\endgroup$
    – narip
    Oct 31, 2021 at 9:22
  • $\begingroup$ This paper link, you can see the quantum BFS in Theorem 1. $\endgroup$
    – Jiawei Ren
    Nov 1, 2021 at 15:50

1 Answer 1

Reset to default
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.