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
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. Although their theoretical properties and algorithmic advantages have been studied extensively, practical gate-level realizations suitable for execution on quantum hardware remain largely unexplored. This gap limits the assessment of lackadaisical quantum walk search under realistic architectural constraints, noise processes, 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 and apply noise-mitigation techniques to improve the measured search performance. Logical-resource analysis shows that, for grids ranging from $8\times8$ to $64\times64$, the algorithmic register increases from 9 to 15 qubits, while 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.

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

Grover search with lackadaisical quantum walks

Thomas G. Wong

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

Coined Quantum Walks on Complex Networks for Quantum Computers

Rei Sato

We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert models. The results show that the circuit depth scales as approximately $N^{1.9}$ regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with $N=4$ and $N=8$. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.

quant-pharXiv:2512.16400•Quantum Information Processing•Dec 19, 2025•0 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. Although their theoretical properties and algorithmic advantages have been studied extensively, practical gate-level realizations suitable for execution on quantum hardware remain largely unexplored. This gap limits the assessment of lackadaisical quantum walk search under realistic architectural constraints, noise processes, 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 and apply noise-mitigation techniques to improve the measured search performance. Logical-resource analysis shows that, for grids ranging from 8×88\times88×8 to 64×6464\times6464×64, the algorithmic register increases from 9 to 15 qubits, while 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.
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.
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.
We propose a quantum circuit design for implementing coined quantum walks on complex networks. In complex networks, the coin and shift operators depend on the varying degrees of the nodes, which makes circuit construction more challenging than for regular networks. To address this issue, we use a dual-register encoding to enable a simplified shift operator and reduces the resource overhead. We implement the circuit using Qmod, a high-level quantum programming language, and evaluated the performance through numerical simulations on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert models. The results show that the circuit depth scales as approximately N1.9N^{1.9}N1.9 regardless of the network topology. Furthermore, we execute the proposed circuits on the ibm\_torino superconducting quantum processor for Watts-Strogatz models with N=4N=4N=4 and N=8N=8N=8. The experiments show that hardware-aware optimization slightly improved the variation distance and Hellinger fidelity for the larger network, whereas connectivity constraints imposed overhead for the smaller one. These results indicate that while current NISQ devices are limited to small-scale validations, the polynomial scaling of our framework makes it suitable for larger-scale implementations in the fault-tolerant quantum computing era.