Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak +1

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}\…