Quantum walk

Quantum random walks are quantum mechanical extension of classical random walks where the walker may be in a superposition of positions.

Quantum walks exhibit very different features from classical random walks. In particular, they do not converge to limiting distributions and due to the power of quantum interference they may spread significantly faster or slower than their classical equivalents.

They are largely of interest as source for quantum algorithms.

Continuous time

Label the vertexes of arbitrary graph as independent quantum states. Then a quantum walk in continuous time is specified by using the adjacency matrix for the graph to create a Hamiltonian, so time evolution is specified by the unitary operator $e^{iHt}$.

Continuous quantum walks also provide a model for universal quantum computation.

Discrete time

Probability distribution resulting from one dimensional discrete time random walks. The quantum walk created using the Hadamard coin is plotted (blue) vs a classical walk (red) after 50 time steps.

A quantum walk in discrete time is specified a coin and shift operator, which are applied repeatedly.

References

• Andris Ambainis (2003). "Quantum walks and their algorithmic applications". International Journal of Quantum Information. 1: 507–518.
• Julia Kempe (2003). "Quantum random walks - an introductory overview". Contemporary Physics. 44: 307–327.