# Soundness of Grover's search application

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?

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