Quantum walk

Quantum walks are quantum analogues 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: (1) quantum superposition of states, (2) non-random, reversible unitary evolution and (3) collapse of the wave function due to state measurements. Quantum walks are quantum analogues 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: (1) quantum superposition of states, (2) non-random, reversible unitary evolution and (3) collapse of the wave function due to state measurements. As with classical random walks, quantum walks admit formulations in both discrete time and continuous time. 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. 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. 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. 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 ψ : R × R ≥ 0 → C {displaystyle psi :mathbb {R} imes mathbb {R} _{geq 0} o mathbb {C} } which satisfies the one-dimensional, free particle Schrödinger equation i ℏ ∂ ψ ∂ t = − ℏ 2 2 m ∂ 2 ψ ∂ x 2 {displaystyle { extbf {i}}hbar {frac {partial psi }{partial t}}=-{frac {hbar ^{2}}{2m}}{frac {partial ^{2}psi }{partial x^{2}}}} where i = − 1 {displaystyle { extbf {i}}={sqrt {-1}}} and ℏ {displaystyle hbar } is Planck's 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 {...,-2Delta x,-Delta x,0,Delta x,2Delta x,...}} 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} imes mathbb {R} _{geq 0} o mathbb {C} } and the second spatial partial derivative becomes the discrete laplacian ∂ 2 ψ ∂ x 2 → L Z ψ ( j Δ x , t ) Δ x 2 ≡ ψ ( ( j + 1 ) Δ x , t ) − 2 ψ ( j Δ x , t ) + ψ ( ( j − 1 ) Δ x , t ) Δ x 2 {displaystyle {frac {partial ^{2}psi }{partial x^{2}}} o {frac {L_{mathbb {Z} }psi (jDelta x,t)}{Delta x^{2}}}equiv {frac {psi left((j+1)Delta x,t ight)-2psi left(jDelta x,t ight)+psi left((j-1)Delta x,t ight)}{Delta x^{2}}}}