Quantum walks are quantum analogs of classical random walks. In contrast to the classical random walk, where the walker occupies definite states and the randomness arises due to stochastic transitions between states, in quantum walks randomness arises through:
Quantum superposition of states, Non-random, reversible unitary evolution and, Collapse of the wave function due to state measurements. Quantum walks are a technique for building quantum algorithms. As with classical random walks, quantum walks admit formulations in both discrete time and continuous time.
Motivation 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. Quantum walks also give polynomial speedups over classical algorithms for many practical problems, such as the element distinctness problem, the triangle finding problem, and evaluating NAND trees. The well-known Grover search algorithm can also be viewed as a quantum walk algorithm.
Distinction from classical random walks 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. There is also no randomness in quantum walks. Due to the laws of quantum mechanics, the evolution of an isolated quantum system is deterministic. This means that by using current conditions, you can exactly predict the future behaviors of the system. Randomness only occurs in quantum walks when the system is measured and classical information is gathered. Also, instead of the "coin flip" used in classical systems, quantum walks enlarge the space of the physical system to create more data.
Continuous time
Continuous-time quantum walks arise when one replaces the continuum spatial domain in the Schrödinger equation with a discrete set. That is, instead of having a quantum particle propagate in a continuum, one restricts the set of possible position states to the vertex set V {\displaystyle V} of some graph G = ( V , E ) {\displaystyle G=(V,E)} which can be either finite or countably infinite. Under particular conditions, continuous-time quantum walks can provide a model for universal quantum computation.
Relation to non-relativistic Schrödinger dynamics Consider the dynamics of a non-relativistic, spin-less free quantum particle with mass m {\displaystyle m} propagating on an infinite one-dimensional spatial domain. The particle's motion is completely described by its wave function ψ ( x , t ) : R × R ≥ 0 → C {\displaystyle \psi (x,t):\mathbb {R} \times \mathbb {R} _{\geq 0}\to \mathbb {C} } which satisfies the one-dimensional, free particle Schrödinger equation
i ℏ ∂ ψ ∂ t = − ℏ 2 2 m ∂ 2 ψ ∂ x 2 {\displaystyle {\textbf {i}}\hbar {\frac {\partial \psi }{\partial t}}=-{\frac {\hbar ^{2}}{2m}}{\frac {\partial ^{2}\psi }{\partial x^{2}}}}
where i = − 1 {\displaystyle {\textbf {i}}={\sqrt {-1}}} and ℏ {\displaystyle \hbar } is the reduced Planck constant. Now suppose that only the spatial part of the domain is discretized, R {\displaystyle \mathbb {R} } being replaced with Z Δ x ≡ { … , − 2 Δ x , − Δ x , 0 , Δ x , 2 Δ x , … } {\displaystyle \mathbb {Z} _{\Delta x}\equiv \{\ldots ,-2\,\Delta x,-\Delta x,0,\Delta x,2\,\Delta x,\ldots \}} where Δ x {\displaystyle \Delta x} is the separation between the spatial sites the particle can occupy. The wave function becomes the map ψ : Z Δ x × R ≥ 0 → C {\displaystyle \psi :\mathbb {Z} _{\Delta x}\times \mathbb {R} _{\geq 0}\to \mathbb {C} } and the second spatial partial derivative becomes the discrete laplacian
… excerpt ends here. Continue reading the full article.
