Quantum Walk Based Search Algorithms

By Miklos Santha. Theory and Applications of Models of Computation, 2008

544 citations recorded by the source corpus.

In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al. will be stated as quantum analogues of classical search procedures. We present a rather detailed description of a somewhat simplified version of the MNRS algorithm. Finally, in the query complexity model, we show how quantum walks can be applied to the following search problems: Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/84114dd5d9f55111cecee5186dfbb47df2eea0c9

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 algorithms: an overview (2015, unknown): “This framework has been used to obtain quantum speedups for a variety of problems [85], ranging from determining whether a list of integers are all distinct [6] to (cid:12)nding triangles in graphs [61].”
Quantum machine learning: a classical perspective (2017, unknown): “Prakash and Kerenidis [52,60] introduced the quantum singular value estimation (QSVE) algorithm, based on Szegedy’s work on quantum walks [81], which runs in time O(‖A‖F log MN/ ).”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “In fact our quantum singular value transformation circuit corresponds to a Szegedy [53] quantum walk in the special case when all phases are set to 2 .”
Simulating chemistry using quantum computers. (2010, background): “However, quantum computers can implement Markov chains corresponding to thermal states of classical Hamiltonians with a quadratic speed-up (121,117,133,106,107,26).”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.”
Quantum speedup of Monte Carlo methods (2015, background): “A construction due to Szegedy [37] defines a quantum walk corresponding to any ergodic Markov chain, such that the dependence on τ in the mixing time can be improved to O( √ τ ) [12].”
Hamiltonian Simulation by Qubitization (2016, background): “orithms – the gap ∆ of eigenvalues λ= 1 −∆ of Hˆ is ampliﬁed to cos−1 (λ) = O( √ ∆) in the phase of the iterate, which resembles spectral gap ampliﬁcation [30], the quantization of stochastic matrices[31],aswellasSzegedy’s[26]andChilds’[24]quantumwalk. Thekeydiﬀerenceliesinthe generalizedencodingoft”
Search via quantum walk (2006, methodology): “As a result we considerably expand the scope of the previous approaches of Ambainis [6] and Szegedy [24].”
Machine learning \& artificial intelligence in the quantum domain (2017, methodology): “The Szegedy (Szegedy, 2004) approach to random walks can be used to specify a unitary random walk operator UP , for a given transition matrix P 121, whose spectral properties are intimately related to those of P itself.”