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

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

2005-07-06

arxiv.org/abs/quant-ph/0507060v2

Physics

Quantum Physics

10 pages, LaTeX2e, presentation changed, paper shortered

Scientific paper

We deal with a problem of finding maximum of a function from the Holder 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 the algorithm for finding maximum of a discrete sequence. To prove lower bounds we use results for finding logical OR of sequence of bits. We show that quantum computation yields a quadratic speed-up over deterministic and randomized algorithms.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Searching Maximum of a Function on a Quantum Computer does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Searching Maximum of a Function on a Quantum Computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Searching Maximum of a Function on a Quantum Computer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-611942