<p>For the sake of completeness, here's an answer. </p>

<p>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.)</p>

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

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

<p>This follows from <a href="http://arxiv.org/abs/cs/9904019v2" rel="nofollow">Bounds for Small-Error and Zero-Error Quantum Algorithms</a>.</p>

<p>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]$,</p>

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

<p>This was shown in <a href="http://arxiv.org/abs/0802.1816" rel="nofollow">A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions</a>.</p>

CC BY-SA 3.0
2015-12-22T13:09:53.917Z
2015-12-22T13:09:53.917Z
Robin Kothari
<p>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?</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-11-23T12:12:26.607Z
This paper should provide answers to your questions: http://arxiv.org/abs/cs/9904019v2
John Watrous
CC BY-SA 3.0
2012-11-23T17:16:07.667Z
Hmmm I am a bit confused now for the case of $\epsilon=\frac{1}{N}$. It seems this paper http://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
CC BY-SA 3.0
2012-11-23T18:15:22.587Z
@MohammadBavarian: I think that's only in the case where the number of solutions is known (or there's a unique solution).
Robin Kothari
<cc.complexity-theory><ds.algorithms><quantum-computing><lower-bounds>
On optimality of Grover algorithm with high success probability
Mohammad Bavarian
# On optimality of Grover algorithm with high success probability

(Asked by: username_0 on 2012-11-23)

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. )

**Tags:** cc.complexity-theory, ds.algorithms, quantum-computing, lower-bounds

> **Comments:**
> **username_1**: This paper should provide answers to your questions: http://arxiv.org/abs/cs/9904019v2  
> **username_0**: Hmmm I am a bit confused now for the case of $\epsilon=\frac{1}{N}$. It seems this paper http://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.  
> **username_2**: @MohammadBavarian: I think that's only in the case where the number of solutions is known (or there's a unique solution).  

---

## 1 answers

### Answer by username_2 on 2015-12-22. Score: 3

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](http://arxiv.org/abs/cs/9904019v2).

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)})$.

This was shown in [A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions](http://arxiv.org/abs/0802.1816).


---

