Timeline for How can I get all the good items using quantum search algorithm?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2016 at 12:46 | comment | added | Dominique Unruh | I agree, the coupon collector solution seems to work and gives a better computational complexity bound than mine. | |
| Dec 20, 2016 at 15:18 | comment | added | Robin Kothari | @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. | |
| Dec 20, 2016 at 10:08 | comment | added | Dominique Unruh | 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. | |
| Aug 9, 2012 at 15:54 | history | answered | Robin Kothari | CC BY-SA 3.0 |