On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids
arXiv:2106.06274 · doi:10.1016/j.ins.2022.11.142
Abstract
Quantum computing promises to improve the information processing power to levels unreachable by classical computation. Quantum walks are heading the development of quantum algorithms for searching information on graphs more efficiently than their classical counterparts. A quantum-walk-based algorithm standing out in the literature is the lackadaisical quantum walk. The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight . This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully. Firstly, we show that only one of the two stopping conditions found in the literature is suitable for simulations. We also demonstrate that the final success probability depends on both the space density of solutions and the relative distance between solutions. Furthermore, this work generalizes the lackadaisical quantum walk to search for multiple solutions on grids of arbitrary dimensions. In addition, we propose an optimal adjustment of the self-loop weight for such -dimensional grids. It turns out other fits of found in the literature are particular cases. Finally, we observe a two-to-one relation between the steps of the lackadaisical quantum walk and Grover's algorithm, which requires modifications in the stopping condition. In conclusion, this work deals with practical issues one should consider when applying the lackadaisical quantum walk, besides expanding the technique to a broader range of search problems.
Accepted manuscript. 23 pages, 7 figures
References in corpus (20)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Universal computation by quantum walk
- Spatial search by quantum walk
- Faster quantum walk algorithm for the two dimensional spatial search
- Quantum computing and the entanglement frontier
- Spatial search and the Dirac equation
- Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
- Connectivity is a Poor Indicator of Fast Quantum Search
- Perfect state transfer and efficient quantum routing: a discrete-time quantum walk approach
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk
- Classical Artificial Neural Network Training Using Quantum Walks as a Search Procedure
- Quantum Walk to Train a Classical Artificial Neural Network
- Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
- Quantum state transfer on the complete bipartite graph
- Lackadaisical quantum walks on 2D grids with multiple marked vertices
- Lackadaisical quantum walk in the hypercube to search for multiple marked vertices
- Search by Lackadaisical Quantum Walk with Symmetry Breaking
- Universal dynamical scaling laws in three-state quantum walks
- Temperature of the three-state quantum walk