|
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? |
|||
|
|
|
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. |
|||
|
|
