On the Complexity of Searching for a Maximum of a Function on a Quantum Computer

We deal with the problem of finding a maximum of a function from the Hölder class on a quantum computer. We show matching lower and upper bounds on the complexity of this problem. We prove upper bounds by constructing an algorithm that uses a pre-existing quantum algorithm for finding maximum of a discrete sequence. To prove lower bounds we use results for finding the logical OR of sequence of bits. We show that quantum computation yields a quadratic speed-up over deterministic and randomized algorithms.