Optimal quantum adversary lower bounds for ordered search

Details Optimal quantum adversary lower bounds for ordered search Optimal quantum adversary lower bounds for ordered search

2007-08-24

arxiv.org/abs/0708.3396v1

Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Lecture Notes in Computer Science 512

Physics

Quantum Physics

13 pages, 2 figures

Scientific paper

10.1007/978-3-540-70575-8_71

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.

Affiliated with

Also associated with

No associations

Rating

Optimal quantum adversary lower bounds for ordered search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal quantum adversary lower bounds for ordered search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal quantum adversary lower bounds for ordered search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-20755