  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 and we would like
to find a marked item. We consider a new variant of this problem in which
evaluating the i-th item may take a different number of time steps for
different i.
  Let t_i be the number of time steps required to evaluate the i-th item. 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+...+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.
