Quantum walks: a comprehensive review

By Salvador Elías Venegas-Andraca. Quantum Information Processing, 2012

1,056 citations recorded by the source corpus.

Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of research of quantum computation full of exciting open problems for physicists, computer scientists and engineers. In this paper we review theoretical advances on the foundations of both discrete- and continuous-time quantum walks, together with the role that randomness plays in quantum walks, the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks, the quantumness of quantum walks, a summary of papers published on discrete quantum walks and entanglement as well as a succinct review of experimental proposals and realizations of discrete-time quantum walks. Furthermore, we have reviewed several algorithms based on both discrete- and continuous-time quantum walks as well as a most important result: the computational universality of both continuous- and discrete-time quantum walks.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Experimental and Cognitive Psychology

View Paper: https://www.semanticscholar.org/paper/073d5c81219a52151a4eaab1b0d952b7e414e521

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

1. C. Rosales-Guzmán
2. Yijie Shen
3. Ashley Montanaro
4. Stefan Woerner
5. Daniel J. Egger

In Computational Theory and Mathematics

1. C. Rosales-Guzmán
2. Yijie Shen
3. Ashley Montanaro

In Experimental and Cognitive Psychology

1. C. Rosales-Guzmán
2. Yijie Shen
3. Ashley Montanaro

Citations in the corpus

• Quantum speedup of Monte Carlo methods (2015, background): “It is therefore sufficient to take k = O(σ 2/ 2) to estimate μ up to additive error with, say, 99% success probability.”
• Observing Topological Invariants Using Quantum Walks in Superconducting Circuits (2016, neutral): “Besides simulation, the quantum walk on a circle, which we have realized here, is also of interest from the point of view of algorithms [33], with potential applications in sampling.”
• Nonseparable States of Light: From Quantum to Classical (2022, background): “A typical algorithm is the quantum walk [189].”