01273nas a2200145 4500008004100000245009500041210006900136260001400205490000700219520078700226100002301013700002401036700002301060856004401083 2007 eng d00aImproved quantum algorithms for the ordered search problem via semidefinite programming
0 aImproved quantum algorithms for the ordered search problem via s c2007/3/260 v753 a 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 ordered search in terms of a semidefinite program, we find new 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.
1 aChilds, Andrew, M.1 aLandahl, Andrew, J.1 aParrilo, Pablo, A. uhttp://arxiv.org/abs/quant-ph/0608161v1