On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids

Autor: de Carvalho, Jonathan H. A., de Souza, Luciano S., Neto, Fernando M. de Paula, Ferreira, Tiago A. E.
Rok vydání: 2021
Předmět:
Zdroj: Information Sciences 622 (2023) 873-888
Druh dokumentu: Working Paper
DOI: 10.1016/j.ins.2022.11.142
Popis: 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 $l$. 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 $l$ for such $d$-dimensional grids. It turns out other fits of $l$ 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.
Comment: Accepted manuscript. 23 pages, 7 figures
Databáze: arXiv
Externí odkaz: