Quantum walk

In quantum computing, quantum walks are the quantum analogue of classical random walks. Analogous to 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. 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.

Under particular conditions, continuous-time quantum walks can provide a model for universal quantum computation. This does not necessarily imply uniformality.

A quantum walk in discrete time is specified by a coin and shift operator, which are applied repeatedly. The following example is instructive here. Imagine a particle on a line (one-dimensional model) with an inner spin-1/2-degree of freedom, i.e. its state can be described by a product state of a spin state ${\displaystyle |s\rangle \in {\mathcal {H}}_{C}=\{|\uparrow \rangle ,|\downarrow \rangle \}}$ (eigenstates of the z component of the spin operator with eigenvalues +1/2 (spin up) and -1/2 (spin down)) and a position state ${\displaystyle |i\rangle \in {\mathcal {H}}_{P}=\{|n\rangle :n\in \mathbb {Z} \}}$. The product of the states is achieved with the Kronecker product which separates these two degrees of freedom. The space with the spin states will be called coin space. Now a conditional jump of the particle on the line would be described by the operator ${\displaystyle S=|\uparrow \rangle \langle \uparrow |\otimes \sum \limits _{i}|i+1\rangle \langle i|+|\downarrow \rangle \langle \downarrow |\otimes \sum \limits _{i}|i-1\rangle \langle i|}$, i.e. the particle jumps right if it has spin up and jumps left if it has spin down, e.g. if we start with a state like ${\displaystyle |\uparrow \rangle \otimes |0\rangle }$ and apply the conditional jump operation, we get the state ${\displaystyle |\uparrow \rangle \otimes |1\rangle }$. If we first rotate the spin with some unitary transformation ${\displaystyle C}$ in ${\displaystyle {\mathcal {H}}_{C}}$, e.g. a Hadamard transformation, and then apply ${\displaystyle S}$, we get a random motion on the line. Take e.g. the Hadamard coin ${\displaystyle H}$: ${\displaystyle |\uparrow \rangle \otimes |0\rangle {\overset {H}{\longrightarrow }}{\frac {1}{\sqrt {2}}}(|\uparrow \rangle +|\downarrow \rangle )\otimes |0\rangle {\overset {S}{\longrightarrow }}{\frac {1}{\sqrt {2}}}(|\uparrow \rangle \otimes |1\rangle +|\downarrow \rangle \otimes |-1\rangle )}$. If we at this point decided to measure the spin, we would either get an up spin at position 1 or a down spin at position -1 and repeating the procedure would correspond to a classical walk like e.g. Galton's board. Instead the idea of the quantum walk is that we do not measure the state at this point (and therefore do not force a collapse of the wave function) and then repeat the procedure of rotating spin and conditionally jumping. This way, quantum correlations (i.e. the non-collapsed wave function) are preserved and different positions can interfere. This gives a drastically different probability distribution compared to the classical walk (Gaussian distribution) as seen from the figure to the right. Espacially one sees that the distribution is not symmetric: even though the Hadamard coin gives both up and down spin with equal probability, the distribution tends to drift to the right when the initial spin is an up spin. This effect is, broadly speaking, due to the fact that the Hadamard coin gives more destructive interference of the positions for paths going left than for paths going right. One can get a symmetric distribution when using some other coin or when using an input state like ${\displaystyle {\frac {1}{\sqrt {2}}}(|\uparrow \rangle +\mathrm {i} |\downarrow \rangle )\otimes |0\rangle }$ because the Hadamard coin does not introduce complex numbers which is why the spin up and spin down components are not mixed here.

...
Wikipedia