Lackadaisical quantum walks on 2D grids with multiple marked vertices

Abstract

Lackadaisical quantum walk (LQW) is a quantum analog of a classical lazy walk, where each vertex has a self-loop of weight $l$. For a regular $\sqrt{N}\times \sqrt{N}$ 2D grid LQW can find a single marked vertex with $O(1)$ probability in $O(\sqrt{N\log N})$ steps using $l=d/N$, where $d$ is the degree of the vertices of the grid. For multiple marked vertices, however, $l=d/N$ is not optimal as the success probability decreases with the increase of the number of marked vertices. In this paper, we numerically study search by LQW for different types of 2D grids -- triangular, rectangular and honeycomb -- with multiple marked vertices. We show that in all cases the weight $l=m\cdot d/N$, where $m$ is the number of marked vertices, still leads to $O(1)$ success probability.

arXiv comment14 pages, 8 figures. arXiv admin note: text overlap with arXiv:2007.13564

References in corpus (17)

• Quantum Computation and Decision Trees
• A Quantum Random Walk Search Algorithm
• One-Dimensional Three-State Quantum Walk
• Faster quantum walk algorithm for the two dimensional spatial search
• Grover Search with Lackadaisical Quantum Walks
• Quantum Walks
• Faster Search by Lackadaisical Quantum Walk
• Limit distributions of three-state quantum walks: the role of coin eigenstates
• Spatial search in a honeycomb network
• Quantum Search with Multiple Walk Steps per Oracle Query
• Quantum walk-based search algorithms with multiple marked vertices
• Spatial quantum search in a triangular network
• Lackadaisical quantum walk for spatial search
• Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
• Analysis of Lackadaisical Quantum Walks
• Search of clustered marked states with lackadaisical quantum walks

Cited by in corpus (4)

• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
• Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Faster Search of Clustered Marked States with Lackadaisical Quantum Walks