Lackadaisical quantum walk for spatial search

Abstract

Lackadaisical quantum walk(LQW) has been an efficient technique in searching a target state from a database which is distributed on a two-dimensional lattice. We numerically study the quantum search algorithm based on the lackadaisical quantum walk on one- and two-dimensions. It is observed that specific values of the self-loop weight at each vertex of the graph is responsible for such speedup of the algorithm. Searching for a target state on one-dimensional lattice with periodic boundary conditions is possible using lackadaisical quantum walk, which can find a target state with $\mathcal{O}(1)$ success probability after $\mathcal{O}\left(N\right)$ time steps. In two-dimensions, our numerical simulation upto $M=6$ suggests that lackadaisical quantum walk can search one of the $M$ target states in $\mathcal{O}\left(\sqrt{\frac{N}{M}\log \frac{N}{M}}\right)$ time steps.

9 pages, 6 figures

References in corpus (7)

• Spatial search by quantum walk
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search and the Dirac equation
• Connectivity is a Poor Indicator of Fast Quantum Search
• Faster Search by Lackadaisical Quantum Walk
• Coined Quantum Walks on Weighted Graphs
• Quantum Search Algorithms on Hierarchical Networks

Cited by in corpus (12)

• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
• Lazy Open Quantum Walks
• Quantum walk search by Grover search on coin space
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Quantum walk search on a two-dimensional grid with extra edges
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
• Quantum search on Hanoi network
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Quantum walk search for exceptional configurations
• Faster Search of Clustered Marked States with Lackadaisical Quantum Walks
• Spectral analysis of three-state quantum walks with general coin matrices