Lower Bounds of Quantum Search for Extreme Point

Details Lower Bounds of Quantum Search for Extreme Point Lower Bounds of Quantum Search for Extreme Point

1998-05-31

arxiv.org/abs/quant-ph/9806001v3

Proc.Roy.Soc.Lond. A455 (1999) 2165-2172

Physics

Quantum Physics

Some minor changes

Scientific paper

10.1098/rspa.1999.0397

We show that Durr-Hoyer's quantum algorithm of searching for extreme point of integer function can not be sped up for functions chosen randomly. Any other algorithm acting in substantially shorter time $o(\sqrt{2^n})$ gives incorrect answer for the functions with the single point of maximum chosen randomly with probability converging to 1. The lower bound as $\Omega (\sqrt{2^n /b})$ was 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 converging to 1.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds of Quantum Search for Extreme Point 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 Lower Bounds of Quantum Search for Extreme Point, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds of Quantum Search for Extreme Point will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541597