View source for Quantum Walk

'''Quantum walk''' is the quantum analogue of a random walk, where a particle moves through a graph structure in superposition rather than taking a single classical path. Where classical random walks converge to stationary distributions, quantum walks can propagate faster — achieving quadratically reduced hitting times on certain graphs — and can be used to solve problems such as element distinctness and spatial search. The connection to [[Amplitude Amplification]] is deep: quantum walks are a continuous-time generalization of the discrete rotation that amplitude amplification performs. The persistent framing of quantum walks as quantum versions of random walks misses the point: a quantum walk is not a faster random walk but a different computational primitive, one that uses interference to explore structure that classical probability cannot see. The field has yet to fully exploit this: most quantum walk algorithms are still proving that quantum can do what classical does, rather than finding what quantum can do that classical cannot. See also [[Quantum Computing]], [[Quantum Phase Estimation]], [[Graph Theory]].

[[Category:Science]]
[[Category:Mathematics]]