Quantum algorithms for the ordered search problem via semidefinite programming

One of the most basic computational problems is the task of finding a desired item in an ordered list of $N$ items. While the best classical algorithm for this problem uses ${\log }_{2}N$ queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for the ordered search problem in terms of a semidefinite program, we find quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using $4{\log }_{605}N\approx 0.433{\log }_{2}N$ queries, which improves upon the previously best known exact algorithm.

Figure 1

$Q_t\left(e^{i\theta }\right)$ as a function of $\theta$ for $k=2$ and $N=6$. The solid, long-dashed, and short-dashed lines represent $t=0$, 1, and 2, respectively. The intersections at roots of 1 and $-1$ are indicated by circles and squares, respectively.

Figure 2

Laurent polynomial coefficients $q_i^{\left(t\right)}$ as a function of $i$ for exact, translation-invariant OSP algorithms. (a), (b), and (c) show $k=2$, 3, and 4, with $N=6$, 56, and 605, respectively. The coefficients for $t=0,1,2,3,4$ are indicated by solid, dashed, dashed-dotted, dotted, and dashed-dotted-dotted lines respectively.