In this paper, we analyze the application of the Multi-self-loop Lackadaisical Quantum Walk on the hypercube that uses partial phase inversion to search for multiple adjacent marked vertices. We evaluate the influence of the relative position of non-adjacent marked vertices. The use of self-loops and the composition of their weights are an essential part of the construction process of new quantum search algorithms based on lackadaisical quantum walks, however, other aspects have been considered, such as, for example, the type of marked vertices. Part of the energy of a quantum system is retained in states adjacent to the target state. This behavior causes the probability amplitudes of these states to be amplified to values equivalent to those of the target state, reducing their chances of being observed. Here we show experimentally that with the use of partial phase inversion, it is possible to amplify their probability amplitudes to values close to 1 even in scenarios with adjacent marked vertices. We also show that the relative position of the non-adjacent marked vertices did not significantly influence the results. The lackadaisical quantum walk generalization to only a single self-loop and the ideal composition of a weight value was sufficient to obtain advances to quantum search algorithms based on quantum walks. However, the results show that many other aspects need to be taken into account for the construction of new quantum algorithms. It was possible to add gains in the maximum probabilities of success compared to other results found in the literature. In one of the most significant cases, the probability of success increased from $p \approx 0.38$ to $p > 0.99$. Therefore, the use of partial phase inversion brings new contributions to the development of new quantum search algorithms based on quantum walks and the use of multiple self-loops.
In this paper, we analyze the application of the Multi-self-loop Lackadaisical Quantum Walk on the hypercube that uses partial phase inversion to search for multiple adjacent marked vertices. We evaluate the influence of the relative position of non-adjacent marked vertices. The use of self-loops and the composition of their weights are an essential part of the construction process of new quantum search algorithms based on lackadaisical quantum walks, however, other aspects have been considered, such as, for example, the type of marked vertices. Part of the energy of a quantum system is retained in states adjacent to the target state. This behavior causes the probability amplitudes of these states to be amplified to values equivalent to those of the target state, reducing their chances of being observed. Here we show experimentally that with the use of partial phase inversion, it is possible to amplify their probability amplitudes to values close to 1 even in scenarios with adjacent marked vertices. We also show that the relative position of the non-adjacent marked vertices did not significantly influence the results. The lackadaisical quantum walk generalization to only a single self-loop and the ideal composition of a weight value was sufficient to obtain advances to quantum search algorithms based on quantum walks. However, the results show that many other aspects need to be taken into account for the construction of new quantum algorithms. It was possible to add gains in the maximum probabilities of success compared to other results found in the literature. In one of the most significant cases, the probability of success increased from p≈0.38 to p>0.99. Therefore, the use of partial phase inversion brings new contributions to the development of new quantum search algorithms based on quantum walks and the use of multiple self-loops.
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⩽m⩽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((n+m)⋅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.
The concept of lackadaisical quantum walk -- quantum walk with self loops -- was first introduced for discrete-time quantum walk on one-dimensional line. Later it was successfully applied to improve the running time of the spacial search on two-dimensional grid. In this paper we study search by lackadaisical quantum walk on the two-dimensional grid with multiple marked vertices. First, we show that the lackadaisical quantum walk, similarly to the regular (non-lackadaisical) quantum walk, has exceptional configuration, i.e. placements of marked vertices for which the walk has no speed-up over the classical exhaustive search. Next, we demonstrate that the weight of the self-loop suggested in the previous papers is not optimal for multiple marked vertices. And, last, we show how to adjust the weight of the self-loop to overcome the aforementioned problem.
Abstract Lackadaisical quantum walk (LQW) is a quantum analog of a classical lazy walk, where each vertex has a self-loop of weight l . For a regular N × N 2D grid LQW can find a single marked vertex with O (1) probability in O ( N log N ) steps using l = d / N , where d is the degree of the vertices of the grid [11]. For multiple marked vertices, however, l = d / N is not optimal as the success probability decreases with the increase of the number of marked vertices [12]. In this paper, we numerically study search by LQW for different types of 2D grids—triangular, rectangular and honeycomb—with multiple marked vertices. We show that in all cases the weight l = m ⋅ d / N , where m is the number of marked vertices, still leads to O (1) success probability.
The lazy random walk, where the walker has some probability of staying put, is a useful tool in classical algorithms. We propose a quantum analogue, the lackadaisical quantum walk, where each vertex is given l self-loops, and we investigate its effects on Grover's algorithm when formulated as search for a marked vertex on the complete graph of N vertices. For the discrete-time quantum walk using the phase flip coin, adding a self-loop to each vertex boosts the success probability from 1/2 to 1. Additional self-loops, however, decrease the success probability. Using instead the Shenvi, Kempe, and Whaley (2003) coin, adding self-loops simply slows down the search. These coins also differ in that the first is faster than classical when l scales less than N , while the second requires that l scale less than N 2 . Finally, continuous-time quantum walks differ from both of these discrete-time examples—the self-loops make no difference at all. These behaviors generalize to multiple marked vertices.
The lackadaisical quantum walk, which is a quantum walk with a weighted self-loop at each vertex, has been shown to speed up dispersion on the line and improve spatial search on the complete graph and periodic square lattice. In these investigations, each self-loop had the same weight, owing to each graph's vertex transitivity. In this paper, we propose lackadaisical quantum walks where the self-loops have different weights. We investigate spatial search on the complete bipartite graph, which can be irregular with N1 and N2 vertices in each partite set, and this naturally leads to self-loops in each partite set having different weights l1 and l2, respectively. We analytically prove that for large N1 and N2, if the k marked vertices are confined to, say, the first partite set, then with the typical initial uniform state over the vertices, the success probability is improved from its nonlackadaisical value when l1=kN2/2N1 and ${N}_{2}>(3\ensuremath{-}2\sqrt{2}){N}_{1}$, regardless of l2. When the initial state is stationary under the quantum walk, however, then the success probability is improved when l1=kN2/2N1, now without a constraint on the ratio of N1 and N2, and again independent of l2. Next, when marked vertices lie in both partite sets, then for either initial state there are many configurations for which the self-loops yield no improvement in quantum search, no matter what weights they take.
Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Ω( N ) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjacent marked vertices. The analysis is done for the two-dimensional grid and hypercube, and then is generalized for any graph. Additionally, we consider an algorithmic application of the found effect. We investigate a problem of detection of a perfect matching in a bipartite graph. We use the found effect as an algorithmic building block and construct quantum algorithm which, for a specific class of graphs, outperforms its classical analogs.