Spatial search in a honeycomb network

Abstract

The spatial search problem consists in minimizing the number of steps required to find a given site in a network, under the restriction that only oracle queries or translations to neighboring sites are allowed. In this paper, a quantum algorithm for the spatial search problem on a honeycomb lattice with $N$ sites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on a hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh is used to show that the time complexity of this quantum search algorithm is $O(\sqrt{N\log N})$.

10 pages, 2 figures; Minor typos corrected, one Reference added. accepted in Math. Structures in Computer Science, special volume on Quantum Computing

References in corpus (4)

• A Quantum Random Walk Search Algorithm
• Spatial search by quantum walk
• Universal resources for measurement-based quantum computation
• Faster quantum walk algorithm for the two dimensional spatial search

Cited by in corpus (23)

• Staggered Quantum Walks on Graphs
• Faster Search by Lackadaisical Quantum Walk
• The Dirac equation as a quantum walk over the honeycomb and triangular lattices
• Quantum search on graphene lattices
• Establishing the equivalence between Szegedy's and coined quantum walks using the staggered model
• Microwave Experiments Simulating Quantum Search and Directed Transport in Artificial Graphene
• Search on a Fractal Lattice using a Quantum Random Walk
• Quantum walks and quantum search on graphene lattices
• Generalized quantum-classical correspondence for random walks on graphs
• Spatial quantum search in a triangular network
• Extraordinary behaviors in two-dimensional decoherent alternative quantum walk
• Localization in Quantum Walks on a Honeycomb Network
• Quantum walk transport properties on graphene structures
• Continuous-time quantum walks on planar lattices and the role of the magnetic field
• The quantum walk search algorithm: Factors affecting efficiency
• Unveiling and exemplifying the unitary equivalence of discrete time quantum walk models
• Directionally-Unbiased Unitary Optical Devices in Discrete-Time Quantum Walks
• Spatial Search Algorithms on Hanoi Networks
• Spatial Search on Sierpinski Carpet Using Quantum Walk
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Quantum search on Hanoi network
• Quantum Search Algorithms on Hierarchical Networks
• Quantum spatial search with electric potential : long-time dynamics and robustness to noise