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 algorithm based on phase matching and circuit cmplementation

Hanwu Chen, Ke Li, Shengmei Zhao

As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.

Acta Physica Sinica•Jan 1, 2015•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

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•4 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•1 citation

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•39 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.
As a new quantum computing model, quantum walk has been widely studied in recent years. It consists of discrete time quantum walk and continuous time quantum walk. Discrete time quantum walk includes coin quantum walk and scattering quantum walk. Meanwhile as a quantum search algorithm, Grover algorithm can search an unsorted database in time complexity of O(√N) . Recent years quantum walk has been used to solve search problems and some of them have been proved to be as efficient as Grover algorithm. Making full use of the novel properties of quantum walk, the quantum walk search algorithms on the 2D grid and hypercube have been proposed. Inspired by phase matching condition of Grover algorithm, we propose a new quantum walk search algorithm which is based on coin quantum walk. Firstly we give the graph to the quantum walk, and then describe the algorithm in detail. Algorithm uses different coin operators and shift operators for two different cases and draws the corresponding iteration operators. Then we prove that iteration operators used in the algorithm are unitary operators. Then we analyze the time complexity and probability of success of the algorithm. Analysis indicates that the time complexity of the algorithm is the same as that of Grover algorithm, however when the targets to be searched are more than 1/3 of the total targets, the algorithm probability of success is greater than that of Grover algorithm. Finally we give the circuit implementation of the algorithm.
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.
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.
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 .