Lower Bounds for Quantum Search and Derandomization

We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T 2 O( p N) then the error is lower bounded by a constant. If we want error 1=2 N then we need T 2 \Omega\Gamma N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error 1=2 k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a blackbox) , where c ? 0 is a constant independent of k. Furthermore, we prove a lower bound of \Omega\Gamma p log N= log log N) queries for quantum bounded-error search of an ordered list of N items. 1 Introduction Suppose we have an unsorted list of N items and we want to find an item with some specific property. For instance we want to ..