|
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 log2 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 long-standing 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.
|