Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion

• Published in: arXiv.org 2024-11
• Main Authors: de Souza, Luciano S, Jonathan H A de Carvalho, Santos, Henrique C T, Ferreira, Tiago A E
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Hypercubes; Parameters; Phase inversion; Phase shift; Quantum computing; Random walk; Search algorithms; Search process
• ISSN: 2331-8422

The lackadaisical quantum walk, a quantum analog of the lazy random walk, is obtained by adding a weighted self-loop transition to each state. Impacts of the self-loop weight \(l\) on the final success probability in finding a solution make it a key parameter for the search process. The number of self-loops can also be critical for search tasks. This article proposes the quantum search algorithm Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion, which can be defined as a lackadaisical quantum walk with multiple self-loops, where the target state phase is partially inverted. In the proposed algorithm, each vertex has \(m\) self-loops, with weights \(l' = l/m\), where \(l\) is a real parameter. The phase inversion is based on Grover's algorithm and acts partially, modifying the phase of a given quantity \(s < m\) of self-loops. On a hypercube structure, we analyzed the situation where \(1 \leqslant m \leqslant 30\). We also propose two new weight values based on two ideal weights \(l\) used in the literature. We investigated the effects of partial phase inversion in the search for \(1\) to \(12\) marked vertices. As a result, this proposal improved the maximum success probabilities to values close to \(1\) in \(O (\sqrt{(n+m)\cdot N})\), where \(n\) is the hypercube degree. This article contributes with a new perspective on the use of quantum interferences in constructing new quantum search algorithms.