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

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

Published Apr 23, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2504.16664

Related papers

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

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

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

Quantum search on Hanoi network

Pulak Ranjan Giri, V. E. Korepin

Hanoi network (HN) has a one-dimensional periodic lattice as its main structure with additional long-range edges, which allow having efficient quantum walk algorithm that can find a target state on the network faster than the exhaustive classical search. In this paper, we use regular quantum walks and lackadaisical quantum walks, respectively, to search for a target state. From the curve fitting of the numerical results for HN of degrees three and four, we find that their running time for the regular quantum walks are followed by amplitude amplification scales as [Formula: see text] and [Formula: see text], respectively. For the search by lackadaisical quantum walks, the running time scales are as [Formula: see text] and [Formula: see text], respectively.

arXiv:1903.08020•International Journal of Quantum Information•Oct 1, 2019•5 citations

Quantum hash function using discrete-time quantum walk on Hanoi network

Pulak Ranjan Giri

Quantum walk based hash functions have attracted a lot of attention in recent years because of its faster execution time and robust resistance against attacks compared to classical hash functions. It has been observed that the underlying graph and the way message controls the quantum walk iteration steps play a crucial role for the robustness of the hash function. We propose a quantum hash function based on the discrete-time quantum walk on a Hanoi network--a one dimensional periodic lattice with extra long-range edges of a specific form--which is highly collision resistant. The message bits of our scheme control the flow of probability amplitude through the extra long-range edges and the conditional shift operators. Our method even works for messages with small bit-lengths, contrary to most of the quantum walk based hash functions defined on a cycle, which usually work for messages with bit-lengths more than the length of the cycle.

quant-pharXiv:2512.18271•Modern Physics Letters A•Dec 23, 2025•1 citation

Exceptional Configurations for Search by Szegedy's Quantum Walk

Thomas G. Wong, Raqueline A. M. Santos

In seminal work, Szegedy gave a method for quantizing a classical Markov chain that has been especially useful for searching for marked vertices in graphs. We prove, however, that this algorithm fails when searching on the two-dimensional periodic square lattice with a marked diagonal, in the sense that the state of the system only evolves by acquiring minus signs. Then the state is a uniform probability distribution over the vertices for all time, which is equivalent to classically guessing and checking. Furthermore, we prove that this failure also occurs for any configuration of marked vertices on the one-dimensional cycle and for any configuration that reduces to it. Thus, Szegedy's quantum walk has a family of exceptional configurations for which it does not spread. Despite this, we exploit this stationary behavior to construct a quantum walk with an arbitrary polynomial speedup over the classical random walk, and it is the first example of a greater-than-quadratic speedup.

•Oct 19, 2016•0 citations
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.
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.
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.
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.
Hanoi network (HN) has a one-dimensional periodic lattice as its main structure with additional long-range edges, which allow having efficient quantum walk algorithm that can find a target state on the network faster than the exhaustive classical search. In this paper, we use regular quantum walks and lackadaisical quantum walks, respectively, to search for a target state. From the curve fitting of the numerical results for HN of degrees three and four, we find that their running time for the regular quantum walks are followed by amplitude amplification scales as [Formula: see text] and [Formula: see text], respectively. For the search by lackadaisical quantum walks, the running time scales are as [Formula: see text] and [Formula: see text], respectively.
Quantum walk based hash functions have attracted a lot of attention in recent years because of its faster execution time and robust resistance against attacks compared to classical hash functions. It has been observed that the underlying graph and the way message controls the quantum walk iteration steps play a crucial role for the robustness of the hash function. We propose a quantum hash function based on the discrete-time quantum walk on a Hanoi network--a one dimensional periodic lattice with extra long-range edges of a specific form--which is highly collision resistant. The message bits of our scheme control the flow of probability amplitude through the extra long-range edges and the conditional shift operators. Our method even works for messages with small bit-lengths, contrary to most of the quantum walk based hash functions defined on a cycle, which usually work for messages with bit-lengths more than the length of the cycle.
In seminal work, Szegedy gave a method for quantizing a classical Markov chain that has been especially useful for searching for marked vertices in graphs. We prove, however, that this algorithm fails when searching on the two-dimensional periodic square lattice with a marked diagonal, in the sense that the state of the system only evolves by acquiring minus signs. Then the state is a uniform probability distribution over the vertices for all time, which is equivalent to classically guessing and checking. Furthermore, we prove that this failure also occurs for any configuration of marked vertices on the one-dimensional cycle and for any configuration that reduces to it. Thus, Szegedy's quantum walk has a family of exceptional configurations for which it does not spread. Despite this, we exploit this stationary behavior to construct a quantum walk with an arbitrary polynomial speedup over the classical random walk, and it is the first example of a greater-than-quadratic speedup.