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 ₂n queries for a list of length n. Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of ₂n for exact quantum algorithms is only known to lie between (2) /π 0. 221 and 4/₂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 5 ₇₂₆₅n 0. 390 ₂n quantum queries.
Carolan et al. (Thu,) studied this question.