01045nas a2200121 4500008004100000245006200041210006200103260001500165520066900180100002300849700001400872856003700886 2007 eng d00aOptimal quantum adversary lower bounds for ordered search0 aOptimal quantum adversary lower bounds for ordered search c2007/08/243 a The goal of the ordered search problem is to find a particular item in an
ordered list of n items. Using the adversary method, Hoyer, Neerbek, and Shi
proved a quantum lower bound for this problem of (1/pi) ln n + Theta(1). Here,
we find the exact value of the best possible quantum adversary lower bound for
a symmetrized version of ordered search (whose query complexity differs from
that of the original problem by at most 1). Thus we show that the best lower
bound for ordered search that can be proved by the adversary method is (1/pi)
ln n + O(1). Furthermore, we show that this remains true for the generalized
adversary method allowing negative weights.
1 aChilds, Andrew, M.1 aLee, Troy uhttp://arxiv.org/abs/0708.3396v1