Lower bounds of a quantum search for an extreme point
Yuri Ozhigov · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 1999
We show that Durr and Hoyer's quantum algorithm of searching for an extreme point of an integer function cannot be sped up for functions that are chosen randomly. Any other algorithm acting in a substantially shorter time o(√2n) (n →α) gives an incorrect answer for the functions phi with the single point of maximum chosen randomly with probability Perr →1. The lower bound as Ω(√2n /b) is established for the quantum search for solution of the equation f (x) = 1, where f is a Boolean function with b such solutions chosen at random with asymptotic probability 1 (n→α).