Lackadaisical quantum walks are coined quantum walk models in which each vertex is associated with a weighted self-loop, allowing the walker to remain at its current position. They have been shown to effectively enhance spatial search on various graphs under different oracle models, with the cyclic graph being the most fundamental instance. In this paper, lackadaisical quantum walk search is studied on Cayley graphs of dicyclic groups, a non-abelian extension of cyclic groups, under three different oracle models. A preliminary analysis of the search performance is first conducted on dicyclic Cayley graphs with respect to the minimal generating set of the underlying dicyclic group. By expanding the generating sets to enable symmetric exploration and applying an appropriate oracle, the quantum walk search achieves a near-one success probability. Under our proposed configurations, the expected runtime to search on dicyclic Cayley graphs outperforms both quantum walk search on the cycle graph and classical unstructured search.
Quantum walk is the quantum analogue of the classical random walk. Its application in search has demonstrated the capability to solve certain types of problems more efficiently than classical methods. The quantum walk search on the dihedral Cayley graph with 2N vertices is examined under several generating sets
S. With the minimal generating set, the results show that the layout is an exceptional configuration. By adding a self-loop edge with some weight w > 0, which coincides with the lackadaisical quantum walk framework, and extra edges for each vertex, a nearly constant success probability of around 0.80 can be obtained using the proposed weight
w′=N1. The fitted number of steps is given by τ′ = 1.221N − 0.391. A comparison with the cycle graph is made, demonstrating improvement in the expected number of steps under the same vertex set size.
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.
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.
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.
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 .
Lackadaisical quantum walks (LQW) extend discrete-time quantum walks (DTQW) by introducing weighted self-loops, enabling improved spatial-search performance through controlled localization of the walker. Despite substantial theoretical progress, practical gate-level implementations suitable for quantum hardware remain largely unexplored, limiting evaluation under realistic architectural constraints, noise, and resource requirements. In this work, we present a gate-level implementation framework for lackadaisical quantum walk search. The proposed construction encodes the position and coin spaces into qubit registers, and realizes the walk dynamics through oracle, coin, and flip-flop shift operations. We validate the circuit by reproducing the expected search behavior for single and multiple marked vertices and by analyzing the effect of the self-loop weight on the success probability. We further evaluate the implementation under realistic noisy settings using superconducting hardware's noise models. Logical resource analysis shows that, for grids ranging from
8×8 to
64×64, the transpiled gate count increases from
3.63×105 to
4.38×106 and the circuit depth from
2.13×105 to
2.56×106. Finally, fault-tolerant resource estimates based on a surface-code model using the Microsoft Quantum Resource Estimator demonstrate the substantial space-time trade-off associated with magic-state production. The results establish a practical circuit-level pathway for implementing the LQW search and provide a basis for evaluating its performance.