Optimal Quantum Adversary Lower Bounds for Ordered Search
| Speaker: | Andrew Childs |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
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.
This talk assumes no knowledge of quantum computation. We will encounter a little combinatorics (hypergeometric sequences) and a lot of optimization (semidefinite programming).
The talk is based on joint work with Troy Lee (Rutgers).