Exponentially Fast Quantum Search for a Specified Number of Targets
Mark A. Rubin · arXiv (Cornell University) · 2001
The exponentially fast quantum search algorithm of Chen and Diao, which searches for a single target item in an unsorted database, is modified so as to be capable of searching for an arbitrary specified number of target items. If the number of targets, nu_0, is a power of four, the new algorithm will find one of the targets in a database of N items after ceil[log_4(N)]-log_4(nu_0) +1 iterations. If nu_0 is not a power of four, the algorithm will find one of the targets after no more than ceil[log_4(N)]-ceil[log_4(nu_0)]+2 iterations, with a probability of at least one-half.