Quantum search with variable times

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.