Quantum walk

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.

Relation to 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.

Continuous time

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

Discrete time

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 | s ⟩ ∈ H C = { | ↑ ⟩ , | ↓ ⟩ } (eigenstates of the z component of the spin operator with eigenvalues +1/2 (spin up) and -1/2 (spin down)) and a position state | i ⟩ ∈ H P = { | n ⟩ : n ∈ 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 S = | ↑ ⟩ ⟨ ↑ | ⊗ ∑ i | i + 1 ⟩ ⟨ i | + | ↓ ⟩ ⟨ ↓ | ⊗ ∑ i | i − 1 ⟩ ⟨ 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 | ↑ ⟩ ⊗ | 0 ⟩ and apply the conditional jump operation, we get the state | ↑ ⟩ ⊗ | 1 ⟩ . If we first rotate the spin with some unitary transformation C in H C , e.g. a Hadamard transformation, and then apply S , we get a random motion on the line. Take e.g. the Hadamard coin H : | ↑ ⟩ ⊗ | 0 ⟩ ⟶ H 1 2 ( | ↑ ⟩ + | ↓ ⟩ ) ⊗ | 0 ⟩ ⟶ S 1 2 ( | ↑ ⟩ ⊗ | 1 ⟩ + | ↓ ⟩ ⊗ | − 1 ⟩ ) . 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 1 2 ( | ↑ ⟩ + i | ↓ ⟩ ) ⊗ | 0 ⟩ because the Hadamard coin does not introduce complex numbers which is why the spin up and spin down components are not mixed here.

Consider what happens when we discretize a massive Dirac operator over one spatial dimension. In the absence of a mass term, we have left-movers and right-movers. They can be characterized by an internal degree of freedom, "spin" or a "coin". When we turn on a mass term, this corresponds to a rotation in this internal "coin" space. A quantum walk corresponds to iterating the shift and coin operators repeatedly.

This is very much like Richard Feynman's model of an electron in 1 (one) spatial and 1 (one) time dimension. He summed up the zigzagging paths, with left-moving segments corresponding to one spin (or coin), and right-moving segments to the other. See Feynman checkerboard for more details.

The transition probability for a 1-dimensional quantum walk behaves like the Hermite functions which (1) asymptotically oscillate in the classically allowed region, (2) is approximated by the Airy function around the wall of the potential, and (3) exponentially decay in the classically hidden region.