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 ⌈log 2 n ⌉ queries for a list of length n . Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of log 2 n for exact quantum algorithms is only known to lie between (ln 2)/ π ≈ 0.221 and 4/log 2 605 ≈ 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 bounded-error, 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 5log 7265 n ≈ 0.390log 2 n quantum queries.
Carolan et al. (Thu,) studied this question.