Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1502.04567 · Journal of Physics A Mathematical and Theoretical

Grover search with lackadaisical quantum walks

Thomas G. Wong

Published Oct 7, 2015• 94 citations
arXivHTMLPDF

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.

DOI
10.1088/1751-8113/48/43/435304

Related papers

Search by lackadaisical quantum walk with symmetry breaking

Jacob Rapoza, Thomas G. Wong

The lackadaisical quantum walk is a lazy version of a discrete-time, coined quantum walk, where each vertex has a weighted self-loop that permits the walker to stay put. They have been used to speed up spatial search on a variety of graphs, including periodic lattices, strongly regular graphs, Johnson graphs, and the hypercube. In these prior works, the weights of the self-loops preserved the symmetries of the graphs. In this paper, we show that the self-loops can break all the symmetries of vertex-transitive graphs while providing the same computational speedups. Only the weight of the self-loop at the marked vertex matters, and the remaining self-loop weights can be chosen randomly, as long as they are small compared to the degree of the graph.

arXiv:2108.13856•Physical Review A•Dec 22, 2021•5 citations

Coined quantum walks on weighted graphs

Thomas G. Wong

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 .

arXiv:1703.10134•Journal of Physics A Mathematical and Theoretical•Sep 13, 2017•36 citations

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

Luciano S. de Souza, Jonathan H. A. de Carvalho, Henrique C. T. Santos +1 more

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.

arXiv:2305.01121•May 1, 2023•1 citation

Analysis of lackadaisical quantum walks

Peter Høyer, Zhan Yu

The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. We analytically prove that lackadaisical quantum walks can find a unique marked vertex on any regular locally arc-transitive graph with constant success probability quadratically faster than the hitting time. This result proves several speculations and numerical findings in previous work, including the conjectures that the lackadaisical quantum walk finds a unique marked vertex with constant success probability on the torus, cycle, Johnson graphs, and other classes of vertex-transitive graphs. Our proof establishes and uses a relationship between lackadaisical quantum walks and quantum interpolated walks for any regular locally arc-transitive graph.

arXiv:2002.11234•Quantum Information and Computation•Nov 1, 2020•15 citations

Lackadaisical quantum walks on 2D grids with multiple marked vertices

Nikolajs Nahimovs, Raqueline A. M. Santos

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.

arXiv:2104.09955•Journal of Physics A Mathematical and Theoretical•Aug 27, 2021•5 citations

Search algorithm on strongly regular graph by lackadaisical quantum walk

Fangjie Peng, Meng Li, Xiaoming Sun

Abstract Quantum walk is a widely used method in designing quantum algorithms. In this article, we consider the lackadaisical discrete-time quantum walk (DTQW) on strongly regular graphs (SRG). When there is a single marked vertex in a SRG, we prove that lackadaisical DTQW can find the marked vertex with asymptotic success probability 1, with a quadratic speedup compared to classical random walk. This paper deals with any parameter family of SRG and argues that, by adding self-loops with proper weights, the asymptotic success probability can reach 1. The running time and asymptotic success probability matches the result of continuous-time quantum walk, and improves the result of DTQW.

Journal of Physics A Mathematical and Theoretical•Mar 5, 2024•2 citations
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 is a lazy version of a discrete-time, coined quantum walk, where each vertex has a weighted self-loop that permits the walker to stay put. They have been used to speed up spatial search on a variety of graphs, including periodic lattices, strongly regular graphs, Johnson graphs, and the hypercube. In these prior works, the weights of the self-loops preserved the symmetries of the graphs. In this paper, we show that the self-loops can break all the symmetries of vertex-transitive graphs while providing the same computational speedups. Only the weight of the self-loop at the marked vertex matters, and the remaining self-loop weights can be chosen randomly, as long as they are small compared to the degree of the graph.
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 .
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 lll 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 mmm self-loops, with weights l′=l/ml' = l/ml′=l/m, where lll is a real parameter. The phase inversion is based on Grover's algorithm and acts partially, modifying the phase of a given quantity s<ms < ms<m of self-loops. On a hypercube structure, we analyzed the situation where 1⩽m⩽301 \leqslant m \leqslant 301⩽m⩽30. We also propose two new weight values based on two ideal weights lll used in the literature. We investigated the effects of partial phase inversion in the search for 111 to 121212 marked vertices. As a result, this proposal improved the maximum success probabilities to values close to 111 in O((n+m)⋅N)O (\sqrt{(n+m)\cdot N})O((n+m)⋅N​), where nnn is the hypercube degree. This article contributes with a new perspective on the use of quantum interferences in constructing new quantum search algorithms.
The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. We analytically prove that lackadaisical quantum walks can find a unique marked vertex on any regular locally arc-transitive graph with constant success probability quadratically faster than the hitting time. This result proves several speculations and numerical findings in previous work, including the conjectures that the lackadaisical quantum walk finds a unique marked vertex with constant success probability on the torus, cycle, Johnson graphs, and other classes of vertex-transitive graphs. Our proof establishes and uses a relationship between lackadaisical quantum walks and quantum interpolated walks for any regular locally arc-transitive graph.
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.
Abstract Quantum walk is a widely used method in designing quantum algorithms. In this article, we consider the lackadaisical discrete-time quantum walk (DTQW) on strongly regular graphs (SRG). When there is a single marked vertex in a SRG, we prove that lackadaisical DTQW can find the marked vertex with asymptotic success probability 1, with a quadratic speedup compared to classical random walk. This paper deals with any parameter family of SRG and argues that, by adding self-loops with proper weights, the asymptotic success probability can reach 1. The running time and asymptotic success probability matches the result of continuous-time quantum walk, and improves the result of DTQW.