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

Quantum Information Processing

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

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

Published Oct 3, 2025• 2 citations
Publisher

Abstract

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.

DOI
10.1007/s11128-025-04945-w

Related papers

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

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

Discrete-time quantum walk search on the dihedral Cayley graph

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

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 \(\mathcal {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^{\prime }=\frac{1}{N}\). 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.

International Conference on Software and Computer Applications (ICSCA)•Feb 3, 2026•0 citations

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

Amit Saha, Debanjan Kola, Nishanka Das +1 more

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.

quant-pharXiv:2608.17136•Aug 19, 2026•0 citations

Generalized quantum walk search algorithm

Pulak Ranjan Giri

Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.

International Journal of Quantum Information•Jul 24, 2026•0 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•21 citations
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.
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 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 .
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\mathcal {S}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′=1Nw^{\prime }=\frac{1}{N}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.
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.
Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.
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.