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

Gate-level Implementation and Resource Analysis of Lackadaisical Quantum Walk Search

Amit Saha, Debanjan Kola, Nishanka Das, Amlan Chakrabarti

quant-phcs.ETSubmitted Aug 17, 2026• Announced Aug 19, 2026• 0 citations• Revised Aug 24, 2026 (v2)
v1 · Aug 17, 2026v2 · Aug 24, 2026
arXivHTMLPDF

Abstract

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\times8$ to $64\times64$, the transpiled gate count increases from $3.63\times10^{5}$ to $4.38\times10^{6}$ and the circuit depth from $2.13\times10^{5}$ to $2.56\times10^{6}$. 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.

Comments
27 pages, 15 figures

Related papers

Noise-resilient spatial search with lackadaisical quantum walks

Gabriel Mauricio Oswald Vieira, Nelson Maculan, Franklin de Lima Marquezino

Abstract Quantum walks are a powerful framework for the development of quantum algorithms, with lackadaisical quantum walks (LQWs) standing out as an efficient model for spatial search. In this work, we investigate how broken-link decoherence affects the performance of LQW-based search on a two-dimensional toroidal grid. We show through numerical simulations that while decoherence drives the loopless walk toward a uniform distribution and eliminates its search capability, the inclusion of self-loops significantly mitigates this effect. In particular, even under noise, the marked vertex remains identifiable with probability well above uniform, demonstrating that self-loops enhance the robustness of LQWs in realistic scenarios. These findings extend the known advantages of LQWs from the noiseless setting to noisy environments, consolidating self-loops as a valuable resource for designing resilient quantum search algorithms.

arXiv:2508.13462•Quantum Information Processing•May 20, 2026•0 citations

Discrete-time quantum walk search on the cycle graph with weighted self-loop

Yong Qing Tiong, Kai Lin Ong, Ian K. T. Tan

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=\frac{1.26}{N}$$ 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.

Quantum Information Processing•Oct 3, 2025•2 citations

Quantum Circuits for Quantum Spatial Search on ddd-Dimensional Lattices

Rei Sato

We propose an explicit quantum circuit for quantum spatial search based on discrete-time quantum walks on $d$-dimensional lattices. In this algorithm, the flip-flop shift operator moves the walker to a neighboring site along the selected spatial direction and reverses the corresponding direction label after the move. By encoding each pair of opposite directions so that they differ only in the least significant qubit of the coin register, we implement the shift using coin-controlled modular increment and decrement operations on the position registers, together with a single $X$ gate that reverses the direction label. We verify that the proposed circuits reproduce the theoretical dynamics on two- and three-dimensional periodic lattices. We further extend the circuit construction to systems with position-dependent shift rules, such as non-periodic boundaries, and validate this extension on a two-dimensional lattice. The resource analysis shows logarithmic growth of the circuit width. For the two-dimensional lattice, the synthesized depth is consistent with $O(\sqrt{N}(\log N)^{3/2})$, while the three-dimensional depth empirically follows an $O(\sqrt{N})$ dependence over the investigated range. Under a CX-gate depolarizing noise model, CX-optimized circuits exhibit improved noise robustness. These results provide a practical framework for implementing quantum spatial search on regular lattices and extending it to defective and other irregular lattice structures.

quant-pharXiv:2607.19151•Jul 22, 2026•0 citations

Lackadaisical Quantum Walk Search on Dicyclic Cayley Graphs

Rou Yan Ng, Yong Qing Tiong, Kai Lin Ong

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.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•0 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

Lackadaisical quantum walk for spatial search

Pulak Ranjan Giri, V. E. Korepin

Lackadaisical quantum walk (LQW) has been an efficient technique in searching for a target state in a database which is distributed in a two-dimensional lattice. We numerically study the quantum search algorithm based on the lackadaisical quantum walk in one and two dimensions. It is observed that specific values of the self-loop weight at each vertex of the graph is responsible for such a speedup of the algorithm. Searching for a target state in one-dimensional lattice with periodic boundary conditions is possible using lackadaisical quantum walk, which can find a target state with [Formula: see text] success probability after [Formula: see text] time steps. In two dimensions, our numerical simulation up to [Formula: see text] for specific sets of target states suggests that the lackadaisical quantum walk can search one of the [Formula: see text] target states in [Formula: see text] time steps.

arXiv:1811.06169•Modern Physics Letters A•Dec 3, 2019•24 citations
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×88\times88×8 to 64×6464\times6464×64, the transpiled gate count increases from 3.63×1053.63\times10^{5}3.63×105 to 4.38×1064.38\times10^{6}4.38×106 and the circuit depth from 2.13×1052.13\times10^{5}2.13×105 to 2.56×1062.56\times10^{6}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.
Abstract Quantum walks are a powerful framework for the development of quantum algorithms, with lackadaisical quantum walks (LQWs) standing out as an efficient model for spatial search. In this work, we investigate how broken-link decoherence affects the performance of LQW-based search on a two-dimensional toroidal grid. We show through numerical simulations that while decoherence drives the loopless walk toward a uniform distribution and eliminates its search capability, the inclusion of self-loops significantly mitigates this effect. In particular, even under noise, the marked vertex remains identifiable with probability well above uniform, demonstrating that self-loops enhance the robustness of LQWs in realistic scenarios. These findings extend the known advantages of LQWs from the noiseless setting to noisy environments, consolidating self-loops as a valuable resource for designing resilient quantum search algorithms.
Abstract The evolution operator of the lackadaisical quantum walk on a weighted cycle graph with self-loop weight w>0w>0w>0 w > 0 is examined. With Grover oracle, the effect of different values of www 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 www 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 NNN N vertices is achieved using a flip-flop shift operator, a weighted coin superposition initial state, and w=1.26Nw=\frac{1.26}{N}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.
We propose an explicit quantum circuit for quantum spatial search based on discrete-time quantum walks on ddd-dimensional lattices. In this algorithm, the flip-flop shift operator moves the walker to a neighboring site along the selected spatial direction and reverses the corresponding direction label after the move. By encoding each pair of opposite directions so that they differ only in the least significant qubit of the coin register, we implement the shift using coin-controlled modular increment and decrement operations on the position registers, together with a single XXX gate that reverses the direction label. We verify that the proposed circuits reproduce the theoretical dynamics on two- and three-dimensional periodic lattices. We further extend the circuit construction to systems with position-dependent shift rules, such as non-periodic boundaries, and validate this extension on a two-dimensional lattice. The resource analysis shows logarithmic growth of the circuit width. For the two-dimensional lattice, the synthesized depth is consistent with O(N(log⁡N)3/2)O(\sqrt{N}(\log N)^{3/2})O(N​(logN)3/2), while the three-dimensional depth empirically follows an O(N)O(\sqrt{N})O(N​) dependence over the investigated range. Under a CX-gate depolarizing noise model, CX-optimized circuits exhibit improved noise robustness. These results provide a practical framework for implementing quantum spatial search on regular lattices and extending it to defective and other irregular lattice structures.
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.
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.
Lackadaisical quantum walk (LQW) has been an efficient technique in searching for a target state in a database which is distributed in a two-dimensional lattice. We numerically study the quantum search algorithm based on the lackadaisical quantum walk in one and two dimensions. It is observed that specific values of the self-loop weight at each vertex of the graph is responsible for such a speedup of the algorithm. Searching for a target state in one-dimensional lattice with periodic boundary conditions is possible using lackadaisical quantum walk, which can find a target state with [Formula: see text] success probability after [Formula: see text] time steps. In two dimensions, our numerical simulation up to [Formula: see text] for specific sets of target states suggests that the lackadaisical quantum walk can search one of the [Formula: see text] target states in [Formula: see text] time steps.