3
$\begingroup$

I find that some algorithms can be sped up using Grover's search, but I have a question about the soundness of new algorithms. Since Grover's search is a probabilistic method, it has a chance to make mistakes during the program, resulting the algorithm result different from classical methods. Do people pay attention to speed up the algorithms with a tolerance on the soundness? Or, is there a way to keep the soundness while the speedup achieves?

$\endgroup$

1 Answer 1

3
$\begingroup$

While the method is strictly a probabilistic method, the ideally functioning algorithm is barely that. If you're searching a database of $N$ entries, your probability of failure is only $O(1/N)$. For any reasonable size problem, this probability is tiny.

Moreover, a standard Grover's search works exactly in the regime where you can recognise a good answer. So, once you've finished your run, you verify it. If it didn't work, you repeat until you're successful. Yes, strictly, you might have to keep running forever to get an answer, but after $k$ runs, the probability of not having found a good answer is $O(1/N^k)$, so you can push this stupidly small really quickly so that there is no realistic chance of making a failure, and the running time is $O(k\sqrt{N})$, which still contains the speedup that you want.

So, there are a couple of ways you might think about this:

  • run the algorithm until it verifies. That way, your algorithm is sound. You don't know the worst case running time, but your average case running time is $O(\sqrt{N})$ and you can bound the probability that it's more than some $\gamma\sqrt{N}$ for some parameter $\gamma$, and that probability should scale as $O(\text{exp}(-\gamma))$.
  • run the algorithm for a maximum number of repetitions, $k$. In which case you have an algorithm with a tolerance on the soundness - it may not give the right result but the probability of that happening is $O(1/N^k)$.
$\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.