9
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ This paper should provide answers to your questions: arxiv.org/abs/cs/9904019v2 $\endgroup$ – John Watrous Nov 23 '12 at 12:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Mohammad Bavarian Nov 23 '12 at 17:16
  • 1
    $\begingroup$ @MohammadBavarian: I think that's only in the case where the number of solutions is known (or there's a unique solution). $\endgroup$ – Robin Kothari Nov 23 '12 at 18:15
3
$\begingroup$

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

This was shown in A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.