6533b7cefe1ef96bd1256ed9

RESEARCH PRODUCT

Exceptional Configurations of Quantum Walks with Grover’s Coin

Alexander RivoshNikolajs Nahimovs

subject

CombinatoricsClass (set theory)Transformation (function)DiagonalQuantum walkComputer Science::Computational ComplexityGridMathematics

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].

yearjournalcountryeditionlanguage
2016-01-01
https://doi.org/10.1007/978-3-319-29817-7_8