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

International Journal of Quantum Information

Generalized quantum walk search algorithm

Pulak Ranjan Giri

Published Jul 24, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1142/s0219749926500243

Related papers

Generalized exceptional quantum walk search

Meng Li, Yun Shang

Abstract We mainly study exceptional configuration for coined quantum walk search. For searching on a two-dimensional grid by AKR algorithm, we find some new classes of exceptional configurations that cannot be found by the AKR algorithm effectively and the known diagonal configuration can be regarded as its special case. Meanwhile, we give two modified quantum walk models that can improve the success probability in the exceptional configurations by numerical simulation. Furthermore, we introduce the concept of generalized exceptional configuration and consider search by quantum walk on a cycle with Grover coin. We find that the most common coin combination model (G, −), where G is a Grover diffusion transformation, is a generalized exceptional configuration when just searching one marked vertex on the cycle. In the end, we find generalized exceptional configuration has a different evolution of quantum coherence from exceptional configuration. These extend largely the range of exceptional configuration of quantum walk search in some sense.

arXiv:2011.01629•New Journal of Physics•Nov 13, 2020•10 citations

Quantum walk search for exceptional configurations

Pulak Ranjan Giri

There exist two types of configurations of marked vertices on a two-dimensional grid, known as the exceptional configurations, which are hard to find by the discrete-time quantum walk algorithms. In this article, we provide a comparative study of the quantum walk algorithm with different coins to search these exceptional configurations on a two-dimensional grid. We further extend the analysis to the hypercube, where only one type of exceptional configurations are present. Our observation, backed by numerical results, is that our recently proposed modified coin operator is the only coin which can search both types of exceptional configurations as well as nonexceptional configurations successfully. As a consequence, we observe that the existence of exceptional configurations are not a quantum phenomenon, rather a mere limitation of some of the coin operators.

arXiv:2507.02457•International Journal of Quantum Information•May 17, 2024•2 citations

Quantum walk search for exceptional configurations on one- and two-dimensional lattice with extra long-range edges of Hanoi network of degree four

Satoshi Watanabe, Pulak Ranjan Giri

There exist several types of configurations of marked vertices, referred to as the exceptional configurations, on one- and two-dimensional periodic lattices with additional long-range edges of the Hanoi network of degree four (HN4), which are challenging to find using discrete-time quantum walk algorithms. In this article, we conduct a comparative analysis of the discrete-time quantum walk algorithm utilizing various coin operators to search for these exceptional configurations. First, we study the emergence of several new exceptional configurations/vertices due to the additional long-range edges of the HN4 on both one- and two-dimensional lattices. Second, our study shows that the diagonal configuration on a two-dimensional lattice, which is exceptional in the case without long-range edges, no longer remains an exceptional configuration. Third, it is also shown that a recently proposed modified coin can search all these configurations, including any other configurations in one- and two-dimensional lattices with very high success probability. Additionally, we construct stationary states for the exceptional configurations caused by the additional long-range edges, which explains why the standard and lackadaisical quantum walks with the Grover coin cannot search these configurations.

arXiv:2504.16664•Apr 23, 2025•0 citations

Spatial search algorithms on graphs with multiple targets using discrete-time quantum walk

Xiling Xue, Zhi-Hong Sun, Yue Ruan +1 more

Search algorithms based on discrete-time quantum walk (QW) can be considered as alterations of the standard QW: Use a different coin operator that distinguishes target and nontarget vertices, or, mark the target vertices first followed by the standard QW. Two most frequently used marking coins are [Formula: see text] and [Formula: see text] the negative identity operator and the negative Grover diffusion operator. We show that search algorithms corresponding to these four combinations can be reduced to two, denoted as [Formula: see text] and [Formula: see text], and they are equivalent when searching for nonadjacent multiple targets. For adjacent target vertices, numerical simulations show that the performance of the algorithm [Formula: see text] highly depends on the density of the underlying graph, and it outperforms [Formula: see text] when the density is large enough. At last, a generalized stationary state of both search algorithms on the graphs with even-numbered degree is provided.

International Journal of Quantum Information•Feb 3, 2023•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

Revisiting one-dimensional discrete-time quantum walks with general coin

Mahesh N. Jayakody, Chandrakala Meena, Priodyuti Pradhan

Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.

Physics Open•Nov 10, 2023•9 citations
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.
Abstract We mainly study exceptional configuration for coined quantum walk search. For searching on a two-dimensional grid by AKR algorithm, we find some new classes of exceptional configurations that cannot be found by the AKR algorithm effectively and the known diagonal configuration can be regarded as its special case. Meanwhile, we give two modified quantum walk models that can improve the success probability in the exceptional configurations by numerical simulation. Furthermore, we introduce the concept of generalized exceptional configuration and consider search by quantum walk on a cycle with Grover coin. We find that the most common coin combination model (G, −), where G is a Grover diffusion transformation, is a generalized exceptional configuration when just searching one marked vertex on the cycle. In the end, we find generalized exceptional configuration has a different evolution of quantum coherence from exceptional configuration. These extend largely the range of exceptional configuration of quantum walk search in some sense.
There exist two types of configurations of marked vertices on a two-dimensional grid, known as the exceptional configurations, which are hard to find by the discrete-time quantum walk algorithms. In this article, we provide a comparative study of the quantum walk algorithm with different coins to search these exceptional configurations on a two-dimensional grid. We further extend the analysis to the hypercube, where only one type of exceptional configurations are present. Our observation, backed by numerical results, is that our recently proposed modified coin operator is the only coin which can search both types of exceptional configurations as well as nonexceptional configurations successfully. As a consequence, we observe that the existence of exceptional configurations are not a quantum phenomenon, rather a mere limitation of some of the coin operators.
There exist several types of configurations of marked vertices, referred to as the exceptional configurations, on one- and two-dimensional periodic lattices with additional long-range edges of the Hanoi network of degree four (HN4), which are challenging to find using discrete-time quantum walk algorithms. In this article, we conduct a comparative analysis of the discrete-time quantum walk algorithm utilizing various coin operators to search for these exceptional configurations. First, we study the emergence of several new exceptional configurations/vertices due to the additional long-range edges of the HN4 on both one- and two-dimensional lattices. Second, our study shows that the diagonal configuration on a two-dimensional lattice, which is exceptional in the case without long-range edges, no longer remains an exceptional configuration. Third, it is also shown that a recently proposed modified coin can search all these configurations, including any other configurations in one- and two-dimensional lattices with very high success probability. Additionally, we construct stationary states for the exceptional configurations caused by the additional long-range edges, which explains why the standard and lackadaisical quantum walks with the Grover coin cannot search these configurations.
Search algorithms based on discrete-time quantum walk (QW) can be considered as alterations of the standard QW: Use a different coin operator that distinguishes target and nontarget vertices, or, mark the target vertices first followed by the standard QW. Two most frequently used marking coins are [Formula: see text] and [Formula: see text] the negative identity operator and the negative Grover diffusion operator. We show that search algorithms corresponding to these four combinations can be reduced to two, denoted as [Formula: see text] and [Formula: see text], and they are equivalent when searching for nonadjacent multiple targets. For adjacent target vertices, numerical simulations show that the performance of the algorithm [Formula: see text] highly depends on the density of the underlying graph, and it outperforms [Formula: see text] when the density is large enough. At last, a generalized stationary state of both search algorithms on the graphs with even-numbered degree is provided.
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.
Quantum walk (QW) is the quantum analog of the random walk. QW is an integral part of the development of numerous quantum algorithms. Hence, an in-depth understanding of QW helps us to grasp the quantum algorithms. We revisit the one-dimensional discrete-time QW and discuss basic steps in detail by incorporating the most general coin operator, constant in both space and time, and a localized initial state using numerical modeling. We investigate the impact of each parameter of the general coin operator on the probability distribution of the quantum walker. We show that by tuning the parameters of the general coin, one can regulate the probability distribution of the walker. We provide an algorithm for the one-dimensional quantum walk driven by the general coin operator. The study on general coin operators also includes the popular coins – Hadamard, Grover, and Fourier.