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:1610.06075 · Quantum Information Processing

Exceptional quantum walk search on the cycle

Thomas G. Wong, Raqueline A. M. Santos

Published May 4, 2017• 13 citations
arXivHTMLPDF
DOI
10.1007/s11128-017-1606-y

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 walks on cycles

Małgorzata Bednarska, Andrzej Grudka, Paweł Kurzyński +2 more

arXiv:quant-ph/0304113•Physics Letters A•Sep 12, 2003•63 citations

Quantum Walks and Search Algorithms

Renato Portugal

Quantum science and technology•Jan 1, 2013•501 citations

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

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

Finding paths with quantum walks

Mark S. Hillery

Bulletin of the American Physical Society•Mar 8, 2019•0 citations
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.
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.
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.