Search via quantum walk

By Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha. Symposium on the Theory of Computing, 2006

469 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/2e817862bd68ab6dff16cf4a38c0cce3d9147295

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, background): “For example, one can show that the update operator of a quantum walk corresponding to a reversible Markov chainM [45] essentially implements a block-encoding of the “discriminant matrix” D(M) of the Markov chain.”
Quantum Walk Based Search Algorithms (2008, methodology): “In a recent work, Magniez, Nayak, Roland and Santha [25] proposed a new quantum walk based search method that expanded the scope of the previous approaches.”
Generalized Quantum Signal Processing (2023, background): “…insight: the majority of prominent quantum algorithms, such as Hamiltonian simulation [1–4], quantum search [5–7], factoring [8], and quantum walks [7, 9], can be fundamentally reduced to the central task of implementing a matrix function of a Hamiltonian, f ( H ), this was shown in [10, 11].”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “This approach was later generalized [35, 50] and applied to quantum algorithms for triangle finding [36], checking matrix multiplication [10], and testing group commutativity [34].”
Quantum algorithms: an overview (2015, unknown): “There are analogous algorithms based on quantum walks which improve the dependence on (cid:14) quadratically, from 1 =(cid:14) to 1 = p (cid:14) [6, 92, 66].”
Quantum walks: a comprehensive review (2012, methodology): “transformations as defined on page 2 of [310].”