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

Exceptional Configurations for Search by Szegedy's Quantum Walk

Thomas G. Wong, Raqueline A. M. Santos

Published Oct 19, 2016• 1 citation
OpenAlex

Abstract

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.

Related papers

Quantum Searching on Markov Chains - The Complete Graph

Min-Ho Lee, Nark Nyul Choi, Gregor Tanner

We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.

Acta Physica Polonica A•Dec 1, 2021•3 citations

Quadratic speedup for finding marked vertices by Quantum walks

Andris Ambainis, András Gilyén, Stacey Jeffery +1 more

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.

arXiv:1903.07493•ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•65 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

Stationary states in quantum walk search

Krišjānis Prūsis, Jevgēnijs Vihrovs, Thomas G. Wong

When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state closest to the initial uniform state of the walk. We further prove theorems on the existence of stationary states, with them conditionally existing if the marked vertices form a bipartite connected component and always existing if nonbipartite. These results utilize the standard oracle in Grover's algorithm, but we show that a different type of oracle prevents stationary states from interfering with the search algorithm.

arXiv:1608.00136•Physical Review A•Sep 29, 2016•13 citations

Adiabatic condition and the quantum hitting time of Markov chains

Hari Krovi, Māris Ozols, Jérémie Roland

We present an adiabatic quantum algorithm for the abstract problem of searching marked vertices in a graph, or spatial search. Given a random walk (or Markov chain) $P$ on a graph with a set of unknown marked vertices, one can define a related absorbing walk ${P}^{'}$ where outgoing transitions from marked vertices are replaced by self-loops. We build a Hamiltonian $H(s)$ from the interpolated Markov chain $P(s)=(1\ensuremath{-}s)P+{\mathit{sP}}^{'}$ and use it in an adiabatic quantum algorithm to drive an initial superposition over all vertices to a superposition over marked vertices. The adiabatic condition implies that, for any reversible Markov chain and any set of marked vertices, the running time of the adiabatic algorithm is given by the square root of the classical hitting time. This algorithm therefore demonstrates a novel connection between the adiabatic condition and the classical notion of hitting time of a random walk. It also significantly extends the scope of previous quantum algorithms for this problem, which could only obtain a full quadratic speedup for state-transitive reversible Markov chains with a unique marked vertex.

arXiv:1004.2721•Physical Review A•Aug 30, 2010•30 citations

Quantum-walk-based search algorithms with multiple marked vertices

Gustavo Alves Bezerra, Pedro H. G. Lugão, Renato Portugal

The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, with Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum-walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.

arXiv:2103.12878•Physical Review A•Jun 1, 2021•27 citations
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.
We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al.Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain.The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques.We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator.By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space.
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.
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.
When classically searching a database, having additional correct answers makes the search easier. For a discrete-time quantum walk searching a graph for a marked vertex, however, additional marked vertices can make the search harder by causing the system to approximately begin in a stationary state, so the system fails to evolve. In this paper, we completely characterize the stationary states, or 1-eigenvectors, of the quantum walk search operator for general graphs and configurations of marked vertices by decomposing their amplitudes into uniform and flip states. This infinitely expands the number of known stationary states and gives an optimization procedure to find the stationary state closest to the initial uniform state of the walk. We further prove theorems on the existence of stationary states, with them conditionally existing if the marked vertices form a bipartite connected component and always existing if nonbipartite. These results utilize the standard oracle in Grover's algorithm, but we show that a different type of oracle prevents stationary states from interfering with the search algorithm.
We present an adiabatic quantum algorithm for the abstract problem of searching marked vertices in a graph, or spatial search. Given a random walk (or Markov chain) PPP on a graph with a set of unknown marked vertices, one can define a related absorbing walk P′{P}^{'}P′ where outgoing transitions from marked vertices are replaced by self-loops. We build a Hamiltonian H(s)H(s)H(s) from the interpolated Markov chain $P(s)=(1\ensuremath{-}s)P+{\mathit{sP}}^{'}$ and use it in an adiabatic quantum algorithm to drive an initial superposition over all vertices to a superposition over marked vertices. The adiabatic condition implies that, for any reversible Markov chain and any set of marked vertices, the running time of the adiabatic algorithm is given by the square root of the classical hitting time. This algorithm therefore demonstrates a novel connection between the adiabatic condition and the classical notion of hitting time of a random walk. It also significantly extends the scope of previous quantum algorithms for this problem, which could only obtain a full quadratic speedup for state-transitive reversible Markov chains with a unique marked vertex.
The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, with Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum-walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.