Quantum walks and their exceptional configurations

Quantum walks are quantum counterparts of classical random walks.
They have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems.
Most of the results, however, consider a search space containing a single marked element only.
We show that if the search space contains more than one marked element the quantum speed-up may disappear.
More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk has no speed-up over the classical exhaustive search.

In my talk I'm going to give an introduction to discreet-time coined quantum walk model,
introduce the concept of the exceptional configurations, i.e. configurations of two or more marked vertices for which probability to be found does not grow, and prove some generic theorems, such as the upper bound on the probability of finding a marked vertex. I will also sketch some possible algorithmic applications of the found phenomenon.