Quantum Algorithm for Partial Search

Searching and sorting is used as subroutines in many important algorithms. Grover discovered a quantum algorithm that searches faster than any classical algorithm. If we want less information we can do it faster. Partial search used to find an approximate location of the target item. An example: the exact location of the target item is given by a sequence of many bits, but we want to find only some of them. A partial search considers the following problem: a database is separated into several blocks. We want to find a block with the target item, not the target item itself. Efficiency of search algorithms is measured by number of queries to the oracle [total number of iterations]. Partial search can use the same hardware as the full search. Essential references follow:=$>$ 1) K. Grover, Quantum Mechanics helps in searching for a needle in a haystack, Phys. Rev. Letters, 78(2), 325, 1997. 2) L. K. Grover and J.Radhakrishnan, quant-ph/0407122, 3) V. E. Korepin and L. K. Grover, e-print quant-ph/0504157; Quantum Information Processing, vol. 5, issue 1, page 3, 2006, 4) V. E. Korepin, Journal of Physics A: Math. Gen. vol 38, pages L731-L738, 2005 see also quant-ph/0503238 5) V.E. Korepin, J. Liao, quant-ph/0510179 6) B.-S. Choi, T. A. Walker, S. L. Braunstein, e-print quant-ph/0603136 7) B-S Choi, V. E Korepin, quant-ph/0608106 8) V. E. Korepin, B. C. Vallilo, quant-ph/0609205