2
$\begingroup$

One can get a superposition of all good item using quantum search algorithm in $O$($\sqrt{N}$ ) time, but how one can get all the good items using quantum search algorithm?

I found that all the good items can be found in $O$($\sqrt{Nt}$) time, where t is the number of good items, here, but I couldn't find how.

Improve this question
$\endgroup$
2
  • $\begingroup$ What is a "good item"? What is the context for this question? Voting to close. $\endgroup$
    – Igor Rivin
    Commented Aug 1, 2012 at 19:15
  • 3
    $\begingroup$ Eunou, you need to explain your question more. People here are volunteering their time, energy, and expertise, so you need to make it easy for them to help you. As Igor says, you need to define what you mean by a "good item." Also, you link to a paper: is there some specific part of the paper that you don't understand? $\endgroup$
    – MTS
    Commented Aug 1, 2012 at 19:45

2 Answers 2

Reset to default
4
$\begingroup$

This follows from the fact that if you want to find 1 marked item in set of size N, knowing that there are t marked items, it can be found in $O(\sqrt{n/t})$ queries. Once you find 1 marked item, delete it from your search space and continue searching for the rest. The total complexity is $O(\sqrt{nt})$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The total query complexity is $O(\sqrt{nt})$. The time complexity is higher with the algorithm you sketch. You will need to implement the predicate "is a good element and is not in the list of what was found before". This needs a circuit of size $t$. So the time complexity is $O(\sqrt{nt}\cdot t)=O(n^{1/2}t^{3/2})$. You might get close to $O(\sqrt{nt})$ (up to log-factors) in other machine models, if you can do a search in a suitable data structure in log-time, but that's not obvious. $\endgroup$
    – Dominique Unruh
    Commented Dec 20, 2016 at 10:08
  • 3
    $\begingroup$ @DominiqueUnruh: You're right, the upper bound I stated is for query complexity only. If we don't mind being off by log factors, it's possible to get similar time complexity as well by just repeating the procedure that finds a random marked item in $O(\sqrt{n/t})$ queries $O(t\log t)$ times (by the coupon collector problem) to have found all $t$ items with high probability. $\endgroup$
    – Robin Kothari
    Commented Dec 20, 2016 at 15:18
  • $\begingroup$ I agree, the coupon collector solution seems to work and gives a better computational complexity bound than mine. $\endgroup$
    – Dominique Unruh
    Commented Dec 21, 2016 at 12:46
0
$\begingroup$

Sorry guys.... here is a pdf file, and what I said is in p.2.

And for $x\in\{1,2,...,N}$, if $\chi(x)=1$, $x$ is called a good item. The original quantum search algorithm(Grover algorithm) aim to get a superposition of all the good items. But Ambainis above says that it is possible to get the set of all the good items. I'm asking how in this thread.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ When you have more information to add, it's better to edit your question instead of posting an "answer". This will be possible if you "register" and thus don't generate a unique "user" every time you log on. $\endgroup$
    – John Pardon
    Commented Aug 2, 2012 at 2:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .