Suppose we need to find out whether or not a set of elements $x_1,...,x_n$ contains any marked items.Show that any quantum algorithm that can solve this problem successfully with zero probability error requires $Ω(n)$ queries to the elements.

I know it is quantum search algorithm, with high probability it is known to have $Ω(\sqrt{n})$ queries, however I don't know how to prove the lower bound when it needs zero error.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.