Bounds for Error Reduction with Few Quantum Queries

We consider the quantum database search problem, where we are given a function f: [N] → {0,1}, and are required to return an x∈[N] (a target address) such that f(x)=1. Recently, Grover [G05] showed that there is an algorithm that after making one quantum query to the database, returns an X∈[N] (a random variable) such that$$ \Pr[f(X)=0] = \epsilon^3,$$ where ε = |f−−1(0)|/N. Using the same idea, Grover derived a t-query quantum algorithm (for infinitely many t) that errs with probability only ε2 t+1. Subsequently, Tulsi, Grover and Patel [TGP05] showed, using a different algorithm, that such a reduction can be achieved for all t. This method can be placed in a more general framework, where given any algorithm that produces a target state for some database f with probability of error ε, one can obtain another that makes t queries to f, and errs with probability ε2t+1. For this method to work, we do not require prior knowledge of ε. Note that no classical randomized algorithm can reduce the error probability to significantly below εt+1, even if ε is known. In this paper, we obtain lower bounds that show that the amplification achieved by these quantum algorithms is essentially optimal. We also present simple alternative algorithms that achieve the same bound as those in Grover [G05], and have some other desirable properties. We then study the best reduction in error that can be achieved by a t-query quantum algorithm, when the initial error ε is known to lie in an interval of the form [ℓ, u]. We generalize our basic algorithms and lower bounds, and obtain nearly tight bounds in this setting.