Friday, September 28, 2007 



Optimal Quantum Adversary Lower Bounds for Ordered Search 

How many steps are required to search an ordered list of n items?
For a classical computer, about log_{2} n steps are necessary
and sufficient. Quantum computers can solve this problem using a
constant factor fewer steps, but finding the precise value
of the constant is a longstanding open problem. In this talk, we
consider lower bounds on the quantum query complexity of
ordered search. Specifically, we show that the best lower bound that
can be proved by the quantum adversary method of
Ambainis is (1/pi) ln n + O(1). In fact, this remains true even for
a recent generalization of the adversary method that
allows negative weights.
