Quantum search with variable times

Andris Ambainis
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...