Fastest Quantum Search for Extreme Point
Yuri Ozhigov · arXiv (Cornell University) · 1998
Let F be some integer function on words of length n and some oracle gives the value F(x) for a given x. It is shown how quantum algorithm can find a point of maximum of F with the probability of error 2/3 applying this oracle 32\\sqrt{2^n} times. This algorithm is optimal in within constant factor in the following sense. Any other algorithm acting in substantially shorter time gives incorrect answer for the functions F with the single point of maximum chosen randomly with probability 1. The lower bound as Ømega (\\sqrt{2^n /b}) is established for the quantum search for solution of equations f(x)=1 where f is a Boolean function with b such solutions chosen at random with probability 1, which is a partial amplification of the result of M. Boyer, G. Brassard, P. Hoyer and A. Tapp.