Improved Algorithm and Lower Bound for Variable Time Quantum Search

Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs

We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable tim…