On optimality of Grover algorithm with high success probability

It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for every input with probability $1-\epsilon$ rather than the usual $2/3$. Now in terms of $\epsilon$ what would be the appropriate upper and lower bounds?

It is immediate that $O(\sqrt{n} \log(1/\epsilon))$ queries suffices for this task by repeating the Grover algorithm. But from what I recall this is not at all optimal as even plain Grover algorithm if run carefully, i.e. for appropriate number of iterations, can achieve something like $\epsilon=O(1/n)$ with just $O(\sqrt{n})$ iterations. And hence using that one can get an improvement for all $\epsilon$'s. On the other hand, I don't expect that $\Omega(\sqrt{n})$ be the right answer for very small $\epsilon$'s.

But I am interested to see what one can show in terms of $\epsilon$-dependent upper and lower bounds for different ranges of $\epsilon$ especially when $\epsilon$ is very small say $\epsilon= \exp(-\Omega(n))$ or $\epsilon=1/n^k$ for large $k$'s.

(To give some context, the general phenomenon I am getting at is the amplification in context of quantum query complexity. )

• This paper should provide answers to your questions: arxiv.org/abs/cs/9904019v2 – John Watrous Nov 23 '12 at 12:12
• Hmmm I am a bit confused now for the case of $\epsilon=\frac{1}{N}$. It seems this paper arxiv.org/pdf/quant-ph/9605034v1.pdf states that with about $\frac{\pi}{4}\sqrt{N}$ iterations one can get a high probability result, i.e. $\epsilon=\frac{1}{N}$. (page 2 bottom of first column) On the other hand the paper you mentioned says, in page 4 end of section 3, that $o(1)$ failure probability is impossible for $O(\sqrt{N})$ queries. – Mohammad Bavarian Nov 23 '12 at 17:16
• @MohammadBavarian: I think that's only in the case where the number of solutions is known (or there's a unique solution). – Robin Kothari Nov 23 '12 at 18:15

For the sake of completeness, here's an answer.

Let $Q_\epsilon(f)$ denote the $\epsilon$-error quantum query complexity of computing a function $f$ and $\mathsf{OR}_n$ be the OR function on $n$ bits, defined as $\mathsf{OR}_n(x_1,\ldots,x_n)=\bigvee_{i=1}^n x_i$. (Note that this is different from the problem where you are promised that the input has exactly one 1 and the objective is to find that 1. That problem can be solved with no error in $\Theta(\sqrt{n})$ queries.)

Then we have for all $\epsilon \in [2^{-n},1/3]$,

$Q_\epsilon(\mathsf{OR}_n) = \Theta(\sqrt{n\log(1/\epsilon)})$.

This follows from Bounds for Small-Error and Zero-Error Quantum Algorithms.

In fact, we know something more general. For all symmetric functions $f$, which are functions that only depend on the Hamming weight of the input, we have that for all $\epsilon \in [2^{-n},1/3]$,

$Q_\epsilon(f) = \Theta(Q_{1/3}(f)+\sqrt{n\log(1/\epsilon)})$.