Upperbounds on the probability of finding marked connected components using quantum walks.

Finding a marked vertex in a graph can be a complicated task when using quantum walks. Recent results show that for two or more adjacent marked vertices search by quantum walk with Grover's coin may have no speed-up over classical exhaustive search. In this paper, we analyze the probability of finding a marked vertex and prove several upper bounds for various sets of marked vertices. All upper bounds are given in explicit form.