Quantum walk based search algorithms

Abstract

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.

16 pages, survey paper

References in corpus (6)

• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms Revisited
• A Quantum Random Walk Search Algorithm
• Quantum measurements and the Abelian Stabilizer Problem
• Quantum Search on Bounded-Error Inputs
• Almost uniform sampling via quantum walks

Cited by in corpus (11)

• Quantum algorithms: an overview
• Coined quantum walks on percolation graphs
• A Survey of Quantum Property Testing
• Quantum algorithms for testing properties of distributions
• Quantum Walks and Electric Networks
• Eigenvalue Measurement of Topologically Protected Edge states in Split-Step Quantum Walks
• Discrete time Dirac quantum walk in 3+1 dimensions
• Efficient quantum walk on the grid with multiple marked elements
• Where to quantum walk
• Spatial search using the discrete time quantum walk
• Quantum Search on Simplicial Complexes