Spatial search on a honeycomb network
Gonzalo Abal, R. DONANGELO, Franklin de Lima Marquezino, R. PORTUGAL · Mathematical Structures in Computer Science · 2010
The spatial search problem consists of minimising the number of steps required to find a given site in a network under the restriction that only oracle queries or translations to neighbouring sites are allowed. We propose a quantum algorithm for the spatial search problem on a honeycomb lattice withNsites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on an hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh (Ambainiset al. 2005) is employed to show that the time complexity of this quantum search algorithm is $O(\sqrt{N \log N})$ .