2001/04/17 by Mark A. Rubin, Rubin, Mark A.
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0104082
12 pages including 1 figure
arxiv created 2001/11/10 · arxiv updated 2009/12/01
The quantum search algorithm of Chen and Diao, which finds with certainty 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, nu0, is a power of four, the new algorithm will with certainty find one of the targets in a database of n items using (1/2)(3(N/nu0)logbase4(3)-1) ≈ (1/2)(3(N/nu0)0.7925-1) oracle calls, where N is the smallest power of four greater than or equal to n. If nu0 is not a power of four, the algorithm will, with a probability of at least one-half, find one of the targets using no more than (1/2)(9(N/nu)logbase4(3)-1) calls, where nu is the smallest power of four greater than or equal to nu0.