Authors
Nikolajs Nahimovs, Alexander Rivosh
Publication date
2016
Conference
Mathematical and Engineering Methods in Computer Science: 10th International Doctoral Workshop, MEMICS 2015, Telč, Czech Republic, October 23–25, 2015, Revised Selected Papers 10
Pages
79-92
Publisher
Springer International Publishing
Description
We study search by quantum walk on a two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. We show what the most natural coin transformation — Grover’s diffusion transformation — has a wide class of exceptional configurations of marked locations, for which the probability of finding any of the marked locations does not grow over time. This extends the class of known exceptional configurations; until now the only known such configuration was the “diagonal construction” by [AR08].
Scholar articles
N Nahimovs, A Rivosh - Mathematical and Engineering Methods in Computer …, 2016