<p>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})$.</p>

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

<p>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.</p>

CC BY-SA 3.0
2013-02-24T02:20:29.510Z
2013-02-24T02:20:29.510Z
Robin Kothari
<p>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:</p>

<p>1) Do Grover search, get superposition of t marked element, </p>

<p>2) observe ele space, get one marked element,</p>

<p>3) remove that element,</p>

<p>4) goto 1)</p>

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

<p>My question is, can i do better?</p>

CC BY-SA 3.0
2016-10-06T17:11:02.207Z
Cross-posted: http://physics.stackexchange.com/q/54851/24498, http://cstheory.stackexchange.com/q/16612/5038.  
Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
<quantum-computing><quantum-information>
Finding all solutions by Grover search(not superposition)
user13883
# Finding all solutions by Grover search(not superposition)

(Asked by: username_0 on 2013-02-24)

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?

**Tags:** quantum-computing, quantum-information
> **Comments:**
> **username_1**: Cross-posted: http://physics.stackexchange.com/q/54851/24498, http://cstheory.stackexchange.com/q/16612/5038.   Please [do not post the same question on multiple sites](http://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  

---

## 1 answers

### Answer by username_2 on 2013-02-24. Score: 6 | Accepted answer

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.


---

