Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

When there are multiple marked elements, grover search provides only superposition of them. If I want to find all the marked elements, not superposition, I could try this:

1) Do Grover search, get superposition of t marked element,

2) observe ele space, get one marked element,

3) remove that element,

4) goto 1)

This takes time step $O(\sqrt{\frac{N}{t}}+\sqrt{\frac{N-1}{t-1}}+\dots+\sqrt{\frac{N-t+1}{1}})$.

My question is, can i do better?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

First note that the sum $O\left(\sqrt{\frac{N}{t}}+\sqrt{\frac{N-1}{t-1}}+\dots+\sqrt{\frac{N-t+1}{1}}\right) = O(\sqrt{Nt})$.

The quantum query complexity of this problem is indeed $\Theta(\sqrt{Nt})$.

The lower bound can be shown by reduction from the problem of deciding whether the input has $t$ marked elements or $t+1$ marked elements. This problem is very similar to $t$-threshold, and has a lower bound of $\Omega(\sqrt{Nt})$. This can be shown using the polynomial method or the adversary method.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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