Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses ⌈log2n⌉ queries for a list of length n. Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of log2n for exact quantum algorithms is only known to lie between (ln2)/π≈0.221 and 4/log2605≈0.433. We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any exact, k-query quantum algorithm for ordered search can be implemented by a k-query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses 5log7265n≈0.390log2n quantum queries.