Finding quantum algorithms via convex optimization
Andrew M. Childs, Andrew J. Landahl, Pablo A. Parrilo · 2007
In this paper we describe how to use convex optimization to design quantum algorithms for certain computational tasks. In particular, we consider the ordered search problem, where it is desired to find a specific item in an ordered list of N items. While the best classical algorithm for this problem uses log2N queries to the list, a quantum computer can solve this problem much faster. By characterizing a class of quantum query algorithms for ordered search in terms of a semidefinite program, we find quantum algorithms using 4log605N ≈ 0.433 log2N queries, which improves upon the previously best known exact algorithm.