Quantum walks

Quantum walks can be thought of as quantum generalizations of classical random walks.

Random walks have proved to be a fundamental mathematical tool for modeling and simulating complex problems and natural phenomena, with a wide variety of applications in various fields. Quantum walks were originally devised under the same rationale as classical random walks: as a mathematical framework to develop new quantum algorithms.

Due to their inherent nonlinear chaotic dynamic behaviour and quantum interference effects, quantum walks have been shown to outperform random walks at certain computational tasks (Childs 2003, Shenvi 2003, Ambainis 2004, Ambainis 2007).

Review papers on quantum walks
Reference Title
(Venegas-Andraca 2012) Quantum walks: a comprehensive review
(Ambainis 2003) Quantum walks and their algorithmic applications


  1. Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC 03. Association for Computing Machinery (ACM), 2003. Link

  2. Neil Shenvi, Julia Kempe, K. Birgitta Whaley. Quantum random-walk search algorithm. Physical Review A 67 American Physical Society (APS), 2003. Link

  3. A. Ambainis. Quantum search algorithms. ACM SIGACT News 35, 22 Association for Computing Machinery (ACM), 2004. Link

  4. Andris Ambainis. Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing 37, 210–239 Society for Industrial & Applied Mathematics (SIAM), 2007. Link

  5. Salvador Elías Venegas-Andraca. Quantum walks: a comprehensive review. Quantum Information Processing 11, 1015–1106 Springer Nature, 2012. Link

  6. Andris Ambainis. Quantum walks and their algorithmic applications. International Journal of Quantum Information 01, 507–518 World Scientific Pub Co Pte Lt, 2003. Link

[Someone else is editing this]

You are editing this file