Faster Search of Clustered Marked States with Lackadaisical Quantum Walks
arXiv:2107.02049 · doi:10.1007/s11128-022-03606-6
Abstract
The nature of discrete-time quantum walk in the presence of multiple marked states has been studied by Nahimovs and Rivosh. They introduced an exceptional configuration of clustered marked states if the marked states are arranged in a cluster within a grid, where and an odd integer. They showed that finding a single marked state among the multiple ones using quantum walk with AKR (Ambainis, Kempe and Rivosh) coin requires time. Furthermore, Nahimov and Rivosh also showed that the Grover's coin can find the same configuration of marked state both faster and with higher probability compared to that with the AKR coin. In this article, we show that using lackadaisical quantum walk, a variant of a three-state discrete-time quantum walk on a line, the success probability of finding all the clustered marked states of this exceptional configuration is nearly 1 with smaller run-time. We also show that the weights of the self-loop suggested for multiple marked states in the state-of-the-art works are not optimal for this exceptional configuration of clustered mark states. We propose a range of weights of the self-loop from which only one can give the desired result for this configuration.
arXiv comment10 pages, 6 figures
References in corpus (16)
- Quantum random walks - an introductory overview
- A Quantum Random Walk Search Algorithm
- Quantum walks: a comprehensive review
- 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
- Faster Search by Lackadaisical Quantum Walk
- Spatial Search by Continuous-Time Quantum Walk with Multiple Marked Vertices
- Search by Lackadaisical Quantum Walk with Nonhomogeneous Weights
- Lackadaisical quantum walk for spatial search
- Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
- The Lackadaisical Quantum Walker is NOT Lazy at all
- Lackadaisical quantum walks on 2D grids with multiple marked vertices