Optimal quantum adversary lower bounds for ordered search
arXiv:0708.3396 · doi:10.1007/978-3-540-70575-8_71
Abstract
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.
13 pages, 2 figures
References in corpus (8)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Negative weights make adversaries stronger
- Improved quantum algorithms for the ordered search problem via semidefinite programming
- Invariant Quantum Algorithms for Insertion into an Ordered List
- A Limit on the Speed of Quantum Computation for Insertion into an Ordered List
- Quantum Search in an Ordered List via Adaptive Learning
- The Multiplicative Quantum Adversary
Cited by in corpus (7)
- Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
- Quantum Computation Beyond the Circuit Model
- Quantum Query Algorithms are Completely Bounded Forms
- Reconstructing Strings from Substrings with Quantum Queries
- On the sum-of-squares degree of symmetric quadratic functions
- The Quantum Frontier
- Information-theoretic lower bounds for quantum sorting