Search of clustered marked states with lackadaisical quantum walks

Abstract

Nature of quantum walk in presence of multiple marked state has been studied by Nahimovs and Rivosh \cite{10.1007/978-3-662-49192-8_31}. They have shown that if the marked states are arranged in a $\sqrt{k}\times \sqrt{k}$ cluster in a $\sqrt{N}\times \sqrt{N}$ grid, then to find a single marked state among the multiple ones, quantum walk requires $\Omega (\sqrt{N}-\sqrt{k})$ time. In this paper, we show that using lackadaisical quantum walk with the weight of the self-loop as $\frac{4}{N(k+\lfloor \frac{\sqrt{k}}{2}\rfloor )}$, where $k$ is odd, the probability of finding a marked state increases by $\sim 0.2$. Furthermore, we show that instead of applying the quantum walk $\mathcal{O}(k)$ times to find all the marked states, classical search in the vicinity of the marked state found after the first implementation of the quantum walk can find all the marked states in $\mathcal{O}(\sqrt{k})$ time on average.

arXiv comment6 pages (minor corrections made)

References in corpus (13)

• A Quantum Random Walk Search Algorithm
• Exponential algorithmic speedup by quantum walk
• On the relationship between continuous- and discrete-time quantum walk
• Controlling discrete quantum walks: coins and intitial states
• Spatial search and the Dirac equation
• A random walk approach to quantum algorithms
• Grover Search with Lackadaisical Quantum Walks
• Connectivity is a Poor Indicator of Fast Quantum Search
• Faster Search by Lackadaisical Quantum Walk
• Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
• The Lackadaisical Quantum Walker is NOT Lazy at all
• Space Searches with a Quantum Robot
• Adjustable self-loop on discrete-time quantum walk and its application in spatial search

Cited by in corpus (5)

• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
• Lackadaisical quantum walks on 2D grids with multiple marked vertices
• Search by Lackadaisical Quantum Walk with Symmetry Breaking
• High robustness quantum walk search algorithm with qudit Householder traversing coin, machine learning study
• Lackadaisical quantum walks with multiple marked vertices