Complexity of Searching Maximum of a Function on Quantum Computer
Maciej Goćwin · arXiv (Cornell University) · 2005
In this paper we deal with a problem of finding maximum of a function from the Holder class on quantum computer. We present matching lower and upper bounds on the complexity of this problem in the quantum query model. We prove upper bounds by constructing an algorithm that uses the algorithm for finding maximum of discrete sequence. To prove lower bounds we use result for finding logical OR of sequence of bits. We show that quantum computer yields a quadratic speed-up over deterministic and randomized algorithms.