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:2007.13564

Lackadaisical quantum walks on triangular and honeycomb 2D grids

Nikolajs Nahimovs

Published Jul 24, 2020• 1 citation
arXivHTMLPDF

Abstract

In the typical model, a discrete-time coined quantum walk search has the same running time of $O(\sqrt{N} \log{N})$ for 2D rectangular, triangular and honeycomb grids. It is known that for 2D rectangular grid the running time can be improved to $O(\sqrt{N \log{N}})$ using several different techniques. One of such techniques is adding a self-loop of weight $4/N$ to each vertex (i.e. making the walk lackadaisical). In this paper we apply lackadaisical approach to quantum walk search on triangular and honeycomb 2D grids. We show that for both types of grids adding a self-loop of weight $6/N$ and $3/N$ for triangular and honeycomb grids, respectively, results in $O(\sqrt{N \log{N}})$ running time.

DOI
10.48550/arxiv.2007.13564

Related papers

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

Lackadaisical quantum walks with multiple marked vertices

Nikolajs Nahimovs

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.

arXiv:1808.00672•Aug 2, 2018•1 citation

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•39 citations

Grover search with lackadaisical quantum walks

Thomas G. Wong

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.

arXiv:1502.04567•Journal of Physics A Mathematical and Theoretical•Oct 7, 2015•102 citations

Search by lackadaisical quantum walks with nonhomogeneous weights

Mason L. Rhodes, Thomas G. Wong

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 ${N}_{1}$ and ${N}_{2}$ vertices in each partite set, and this naturally leads to self-loops in each partite set having different weights ${l}_{1}$ and ${l}_{2}$, respectively. We analytically prove that for large ${N}_{1}$ and ${N}_{2}$, 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 ${l}_{1}=k{N}_{2}/2{N}_{1}$ and ${N}_{2}>(3\ensuremath{-}2\sqrt{2}){N}_{1}$, regardless of ${l}_{2}$. When the initial state is stationary under the quantum walk, however, then the success probability is improved when ${l}_{1}=k{N}_{2}/2{N}_{1}$, now without a constraint on the ratio of ${N}_{1}$ and ${N}_{2}$, and again independent of ${l}_{2}$. 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.

arXiv:1905.05887•Physical Review A•Oct 4, 2019•22 citations

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•6 citations
In the typical model, a discrete-time coined quantum walk search has the same running time of O(Nlog⁡N)O(\sqrt{N} \log{N})O(N​logN) for 2D rectangular, triangular and honeycomb grids. It is known that for 2D rectangular grid the running time can be improved to O(Nlog⁡N)O(\sqrt{N \log{N}})O(NlogN​) using several different techniques. One of such techniques is adding a self-loop of weight 4/N4/N4/N to each vertex (i.e. making the walk lackadaisical). In this paper we apply lackadaisical approach to quantum walk search on triangular and honeycomb 2D grids. We show that for both types of grids adding a self-loop of weight 6/N6/N6/N and 3/N3/N3/N for triangular and honeycomb grids, respectively, results in O(Nlog⁡N)O(\sqrt{N \log{N}})O(NlogN​) running time.
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 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 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 .
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 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{N}_{1}N1​ and N2{N}_{2}N2​ vertices in each partite set, and this naturally leads to self-loops in each partite set having different weights l1{l}_{1}l1​ and l2{l}_{2}l2​, respectively. We analytically prove that for large N1{N}_{1}N1​ and N2{N}_{2}N2​, if the kkk 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{l}_{1}=k{N}_{2}/2{N}_{1}l1​=kN2​/2N1​ and ${N}_{2}>(3\ensuremath{-}2\sqrt{2}){N}_{1}$, regardless of l2{l}_{2}l2​. When the initial state is stationary under the quantum walk, however, then the success probability is improved when l1=kN2/2N1{l}_{1}=k{N}_{2}/2{N}_{1}l1​=kN2​/2N1​, now without a constraint on the ratio of N1{N}_{1}N1​ and N2{N}_{2}N2​, and again independent of l2{l}_{2}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.
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.