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

Quantum walk based search methods and algorithmic applications

Katalin Friedl

Published Jan 1, 2014• 3 citations
OpenAlex

Abstract

This thesis provides an introduction to the quantum walk based search method which is the quantum analogue of the classical Markov chain based search. We develop the basic theory of the Markov chain based search together with its quantisation due to Mario Szegedy[Sz2]. We deeply analyse their relationship, and sketch some of the possible algorithmic applications. The thesis also addresses the question of the implementation, which is largely hidden by the high level description. We show how to implement the quantum walk based search algorithm in the case of the element distinctness problem. We implement the necessary operations using only very basic data structures, mainly arrays. Also while we use a weak and basic computational model we could still significantly reduce the exponent of the polylog terms arising from counting non oracle calls. Another interesting achievement is that we could parallelise the Setup operation reducing its circuit depth form O(N ) to O(polylog(N)). Probably the most important tool we introduced for the implementation is the use of reversible sorting networks, but we introduce some other tricks as well. The optimal quantum query algorithm for the element distinctness problem was first described by Andris Ambainis [Amb3] and provided the basis of the generalised method. In this seminal paper Ambainis also addressed the question of implementation. However that implementation method does not fully cast into the general framework which was introduced later. The operations described by Ambainis use some involved data structures, such as skip lists and hash table. Also it uses a strong computational model for example, a qRAM query has cost only 1. In contrast with Ambainis’s single node implementation method ours uses bipartite style approach fitting the general framework of Szegedy. At first sight it may seem unnecessary since it results in a duplication of a large amount of data stored during the walk steps, but in fact it simplifies the implementation process. On the structure of the thesis: Section 1 covers some background on quantum walks and basic techniques related to the quantum walk based search method. Section 2-5 gives a comprehensive description of the general scheme introduced by Szegedy and derives the main theorems showing the quadratic speed-up compared to the classical case. These Sections roughly follow the structure of Szegedy’s original paper [Sz2], but the proofs are restructured, so that I could state the main theorem in a slightly stronger form with a much improved constant. Section 6 addresses the implementation issues already mentioned. Finally, Section 7 gives a brief overview of the further generalised scheme introduced by Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. Quantum walk based search methods and algorithmic applications 2

Related papers

Search via Quantum Walk

Frédéric Magniez, Ashwin Nayak, Jérémie Roland +1 more

We propose a new method for designing quantum search algorithms for finding a “marked” element in the state space of a classical Markov chain. The algorithm is based on a quantum walk à la Szegedy [Quantum speed-up of Markov chain based algorithms, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 32–41] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis [Quantum walk algorithm for Element Distinctness, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 22–31] and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.

arXiv:quant-ph/0608026•SIAM Journal on Computing•Jan 1, 2011•339 citations

Search via Quantum Walk. (arXiv:quant-ph/0608026v4 CROSS LISTED)

Frédéric Magniez, Ashwin Nayak, Jérémie Roland +1 more

We propose a new method for designing quantum search algorithms for finding a element in the state space of a classical Markov chain. The algorithm is based on a quantum walk \'a la Szegedy (2004) that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis (2004) and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.

•Mar 21, 2018•0 citations

Efficient Framework for Quantum Walks and Beyond

Catalin Dohotaru

In the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk $P$ and a single marked state, the quantum walk corresponding to $P$ can find the solution using a number of queries that is quadratically smaller than the classical hitting time of $P$. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.

•Jan 1, 2015•1 citation

Search via quantum walk

Frédéric Magniez, Ashwin Nayak, Jérémie Roland +1 more

We propose a new method for designing quantum search algorithms forfinding a "marked" element in the state space of a classical Markovchain. The algorithm is based on a quantum walk à la Szegedy [25] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantumwalk in order to implement an approximate reflection operator. Thisoperatoris then used in an amplitude amplification scheme. As a result weconsiderably expand the scope of the previous approaches ofAmbainis [6] and Szegedy [25]. Our algorithm combines the benefits of these approaches in terms of beingable to find marked elements, incurring the smaller cost of the two,and being applicable to a larger class of Markov chain. In addition,it is conceptually simple, avoids several technical difficulties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•129 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

Quantum Analogs of Markov Chains

Ashwin Nayak, Peter C. Richter

Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:

•Jan 1, 2015•1 citation
This thesis provides an introduction to the quantum walk based search method which is the quantum analogue of the classical Markov chain based search. We develop the basic theory of the Markov chain based search together with its quantisation due to Mario Szegedy[Sz2]. We deeply analyse their relationship, and sketch some of the possible algorithmic applications. The thesis also addresses the question of the implementation, which is largely hidden by the high level description. We show how to implement the quantum walk based search algorithm in the case of the element distinctness problem. We implement the necessary operations using only very basic data structures, mainly arrays. Also while we use a weak and basic computational model we could still significantly reduce the exponent of the polylog terms arising from counting non oracle calls. Another interesting achievement is that we could parallelise the Setup operation reducing its circuit depth form O(N ) to O(polylog(N)). Probably the most important tool we introduced for the implementation is the use of reversible sorting networks, but we introduce some other tricks as well. The optimal quantum query algorithm for the element distinctness problem was first described by Andris Ambainis [Amb3] and provided the basis of the generalised method. In this seminal paper Ambainis also addressed the question of implementation. However that implementation method does not fully cast into the general framework which was introduced later. The operations described by Ambainis use some involved data structures, such as skip lists and hash table. Also it uses a strong computational model for example, a qRAM query has cost only 1. In contrast with Ambainis’s single node implementation method ours uses bipartite style approach fitting the general framework of Szegedy. At first sight it may seem unnecessary since it results in a duplication of a large amount of data stored during the walk steps, but in fact it simplifies the implementation process. On the structure of the thesis: Section 1 covers some background on quantum walks and basic techniques related to the quantum walk based search method. Section 2-5 gives a comprehensive description of the general scheme introduced by Szegedy and derives the main theorems showing the quadratic speed-up compared to the classical case. These Sections roughly follow the structure of Szegedy’s original paper [Sz2], but the proofs are restructured, so that I could state the main theorem in a slightly stronger form with a much improved constant. Section 6 addresses the implementation issues already mentioned. Finally, Section 7 gives a brief overview of the further generalised scheme introduced by Frederic Magniez, Ashwin Nayak, Jeremie Roland and Miklos Santha. Quantum walk based search methods and algorithmic applications 2
We propose a new method for designing quantum search algorithms for finding a “marked” element in the state space of a classical Markov chain. The algorithm is based on a quantum walk à la Szegedy [Quantum speed-up of Markov chain based algorithms, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 32–41] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis [Quantum walk algorithm for Element Distinctness, in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2004, pp. 22–31] and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.
We propose a new method for designing quantum search algorithms for finding a element in the state space of a classical Markov chain. The algorithm is based on a quantum walk \'a la Szegedy (2004) that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantum walk in order to implement an approximate reflection operator. This operator is then used in an amplitude amplification scheme. As a result we considerably expand the scope of the previous approaches of Ambainis (2004) and Szegedy (2004). Our algorithm combines the benefits of these approaches in terms of being able to find marked elements, incurring the smaller cost of the two, and being applicable to a larger class of Markov chains. In addition, it is conceptually simple and avoids some technical difficulties in the previous analyses of several algorithms based on quantum walk.
In the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk PPP and a single marked state, the quantum walk corresponding to PPP can find the solution using a number of queries that is quadratically smaller than the classical hitting time of PPP. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.
We propose a new method for designing quantum search algorithms forfinding a "marked" element in the state space of a classical Markovchain. The algorithm is based on a quantum walk à la Szegedy [25] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantumwalk in order to implement an approximate reflection operator. Thisoperatoris then used in an amplitude amplification scheme. As a result weconsiderably expand the scope of the previous approaches ofAmbainis [6] and Szegedy [25]. Our algorithm combines the benefits of these approaches in terms of beingable to find marked elements, incurring the smaller cost of the two,and being applicable to a larger class of Markov chain. In addition,it is conceptually simple, avoids several technical difficulties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.
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.
Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification: