Translation-Invariant Quantum Algorithms for Ordered Search are Optimal
Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak, Luke Schaeffer · ACM Transactions on Quantum Computing · 2026
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 \(\lceil \log _{2}{n}\rceil\) 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})/\pi \approx 0.221\) and \(4/\log _{2}{605} \approx 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 \log _{7265}{n} \approx 0.390 \log _{2}{n}\) quantum queries.