We study the localization and the discrete probability function of a quantum search on the one-dimensional (1D) cycle with self-loops for n vertices and m marked vertices. First, unmarked vertices have no localization since the quantum search on unmarked vertices behaves like the 1D three-state quantum walk (3QW) and localization does not occur with nonlocal initial states on a 3QW, according to residue calculations and the Riemann-Lebesgue theorem. Second, we show that localization does occur on the marked vertices and derive an analytic expression for localization by the degenerate 1-eigenvalues contributing to marked vertices. Therefore localization can contribute to a quantum search. Furthermore, we emphasize that localization comes from the self-loops. Third, using the localization of a quantum search, the asymptotic average probability distribution (AAPD) and the discrete probability function (DPF) of a quantum search are obtained. The DPF shows that Szegedy’s quantum search on the 1D cycle with self-loops spreads ballistically.
We study the localization and the discrete probability function of a quantum search on the one-dimensional (1D) cycle with self-loops for n vertices and m marked vertices. First, unmarked vertices have no localization since the quantum search on unmarked vertices behaves like the 1D three-state quantum walk (3QW) and localization does not occur with nonlocal initial states on a 3QW, according to residue calculations and the Riemann-Lebesgue theorem. Second, we show that localization does occur on the marked vertices and derive an analytic expression for localization by the degenerate 1-eigenvalues contributing to marked vertices. Therefore localization can contribute to a quantum search. Furthermore, we emphasize that localization comes from the self-loops. Third, using the localization of a quantum search, the asymptotic average probability distribution (AAPD) and the discrete probability function (DPF) of a quantum search are obtained. The DPF shows that Szegedy’s quantum search on the 1D cycle with self-loops spreads ballistically.
Abstract In this paper, we study the properties of lackadaisical quantum walks (LQWs) on a line. This model was first proposed in Wong (2015 J. Phys. A: Math. Theor . 48 435304) as a quantum analogue of lazy random walks where each vertex is attached to τ self-loops. We derive an analytic expression for the localization probability of the walker at the origin after infinite steps, and obtain the peak velocities of the walker. We also calculate the wave function of the walker starting from the origin and obtain a long-time approximation for the entire probability density function. As an application of the density function, we prove that lackadaisical quantum walks spread ballistically for arbitrary τ , and give an analytic solution for the variance of the walker’s probability distribution.
Abstract We define a discrete-time, coined quantum walk on weighted graphs that is inspired by Szegedy’s quantum walk. Using this, we prove that many lackadaisical quantum walks, where each vertex has l integer self-loops, can be generalized to a quantum walk where each vertex has a single self-loop of real-valued weight l . We apply this real-valued lackadaisical quantum walk to two problems. First, we analyze it on the line or one-dimensional lattice, showing that it is exactly equivalent to a continuous deformation of the three-state Grover walk with faster ballistic dispersion. Second, we generalize Grover’s algorithm, or search on the complete graph, to have a weighted self-loop at each vertex, yielding an improved success probability when l < 3 + 2 2 ≈ 5.828 .
In seminal work, Szegedy gave a method for quantizing a classical Markov chain that has been especially useful for searching for marked vertices in graphs. We prove, however, that this algorithm fails when searching on the two-dimensional periodic square lattice with a marked diagonal, in the sense that the state of the system only evolves by acquiring minus signs. Then the state is a uniform probability distribution over the vertices for all time, which is equivalent to classically guessing and checking. Furthermore, we prove that this failure also occurs for any configuration of marked vertices on the one-dimensional cycle and for any configuration that reduces to it. Thus, Szegedy's quantum walk has a family of exceptional configurations for which it does not spread. Despite this, we exploit this stationary behavior to construct a quantum walk with an arbitrary polynomial speedup over the classical random walk, and it is the first example of a greater-than-quadratic speedup.
Abstract 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 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 The evolution operator of the lackadaisical quantum walk on a weighted cycle graph with self-loop weight w>0 w > 0 is examined. With Grover oracle, the effect of different values of w w on the success probability of the search under various hyperparameter combinations is analyzed. The success probability function of the first few steps is provided algebraically, which in turn highlights the role of w w in governing the evolutionary behavior of the quantum walk search. These studies subsequently allow the numerical results to be obtained for various hyperparameter combinations, showing that the highest success probability for the weighted cycle graph with N N vertices is achieved using a flip-flop shift operator, a weighted coin superposition initial state, and w=N1.26 w = 1.26 N . A comparison is also made with other known oracle, demonstrating that the proposed configuration provides a better trade-off between success probability and runtime. An extension of the study to the SKW scheme is also included, and it demonstrates that the scheme provides more variability and potential for quantum walk search.