Translation-Invariant Quantum Algorithms for Ordered Search are Optimal
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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 2n⌉ queries for a list of length n. Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of log 2n for exact quantum algorithms is only known to lie between (ln 2)/π ≈ 0.221 and 4/log 2605 ≈ 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 7265n ≈ 0.390log 2n quantum queries.