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₁,...,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 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.