Lower Bounds of Quantum Search for Extreme Point

Abstract

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.

Some minor changes

References in corpus (2)

• Strengths and Weaknesses of Quantum Computing
• Quantum Computers Speed Up Classical with Probability Zero

Cited by in corpus (3)

• Speedup of iterated quantum search by parallel performance
• Quantum computations (course of lectures)
• Entanglement in systems of oscillators and quantum computations