Quantum walk  From Wikipedia, the free encyclopedia Jump to:
navigation, search  In quantum computing, quantum walks are the
quantum analogue of classical random walks. Like the classical
random walk, where the walker's current state is described by a
probability distribution over positions, the walker in a quantum
walk is in a superposition of positions. Like classical random
walks, there are two types of quantum walks, discrete-time
quantum walks and continuous-time quantum walks.   Quantum walks
are motivated by the widespread use of classical random walks in
the design of randomized algorithms, and are part of several
quantum algorithms. For some oracular problems, quantum walks
provide an exponential speedup over any classical
algorithm.[1][2] Quantum walks also give polynomial speedups
over classical algorithms for many practical problems, such as
the element distinctness problem,[3] the triangle finding
problem,[4] and evaluating NAND trees.[5] The well-known Grover
search algorithm can also be viewed