In the field of classical algorithms, classical random walks have provided useful
approximation and optimization algorithms, For instance. Schoning’s algorithm,
achieved a complexity of
for 3-SAT. Motivated by the results for classical walks,
researchers in the early 2000s started developing the theory for its quantum analogue.
One of the earliest successes was Ambainis’ quantum walk for element distinctness
problem. In this paper, I’ll provide an overall introduction to quantum walks
and its application to two search problems
- The Historic Quantum random-walk search algorithm
- A recent generalization for Spatial Search