quantum computers are known to outperform classical
computers in a variety of computational tasks. this includes search on
various networks or databases, which can be encoded as graphs. the
search is performed using a quantum walk--the quantum mechanical
analogue of a random walk--and quantum walks often search
quadratically faster than random walks. despite this success, we show
that certain graphs and arrangements of marked vertices cause
difficulties for quantum walks, causing them to perform worse than
classical random walks. on the other hand, some of these difficulties
are successes in disguise, and we use them to construct
greater-than-quadratic speedups for spatial search by quantum walk.

this is joint work with krisjanis prusis, jevgenijs vihrovs, and
raqueline santos in http://arxiv.org/abs/1608.00136 and
http://arxiv.org/abs/1610.06075.