most recent 30 from http://mathoverflow.net 2013-05-26T00:03:04Z http://mathoverflow.net/feeds/question/103672 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103672/how-can-i-get-all-the-good-items-using-quantum-search-algorithm Eunou 2012-08-01T08:59:21Z 2012-08-09T15:54:40Z

<p>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?</p> <p>I found that all the good items can be found in $O$($\sqrt{Nt}$) time, where t is the number of good items, <a href="http://dl.acm.org/citation.cfm?id=992296" rel="nofollow">here</a>, but I couldn't find how.</p>

http://mathoverflow.net/questions/103672/how-can-i-get-all-the-good-items-using-quantum-search-algorithm/103749#103749 Eunou 2012-08-02T01:08:42Z 2012-08-02T01:08:42Z

<p>Sorry guys.... here is a <a href="http://arxiv.org/pdf/quant-ph/0504012.pdf" rel="nofollow">pdf file</a>, and what I said is in p.2.</p> <p>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.</p>

http://mathoverflow.net/questions/103672/how-can-i-get-all-the-good-items-using-quantum-search-algorithm/104364#104364 Robin Kothari 2012-08-09T15:54:40Z 2012-08-09T15:54:40Z

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