Optimal quantum adversary lower bounds for ordered search

Understand

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