Quantum search with variable times

Abstract

Since Grover's seminal work, quantum search has been studied in
   great detail.  In the usual search problem, we have a collection of
   $n$ items $x_1, ldots, x_n$ and we would like to find $i: x_i=1$.
   We consider a new variant of this problem in which evaluating $x_i$
   for different $i$ may take a different number of time steps.
   
   Let $t_i$ be the number of time steps required to evaluate $x_i$.
   If the numbers $t_i$ are known in advance, we give an algorithm
   that solves the problem in $O(sqrt{t_1^2+t_2^2+ldots+t_n^2)$
   steps.  This is optimal, as we also show a matching lower bound.
   The case, when $t_i$ are not known in advance, can be solved with a
   polylogarithmic overhead.  We also give an application of our new
   search algorithm to computing read-once functions.