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

Quantum walk

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.

Quantum walk

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 of some graph 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 propagating on an infinite one-dimensional spatial domain. The particle's motion is completely described by its wave function which satisfies the one-dimensional, free particle Schrödinger equation

where and is the reduced Planck's constant. Now suppose that only the spatial part of the domain is discretized, being replaced with where is the separation between the spatial sites the particle can occupy. The wave function becomes the map and the second spatial partial derivative becomes the discrete laplacian

The evolution equation for a continuous time quantum walk on is thus

where is a characteristic frequency. This construction naturally generalizes to the case that the discretized spatial domain is an arbitrary graph and the discrete laplacian is replaced by the graph Laplacian where and are the degree matrix and the adjacency matrix, respectively. Common choices of graphs that show up in the study of continuous time quantum walks are the d-dimensional lattices , cycle graphs , d-dimensional discrete tori , the d-dimensional hypercube and random graphs.

Discrete time

Discrete-time quantum walks on

The evolution of a quantum walk in discrete time is specified by the product of two unitary operators: (1) a "coin flip" operator and (2) a conditional shift operator, which are applied repeatedly. The following example is instructive here. Imagine a particle with a spin-1/2-degree of freedom propagating on a linear array of discrete sites. If the number of such sites is countably infinite, we identify the state space with . The particle's state can then be described by a product state

consisting of an internal spin state

and a position state

where is the "coin space" and is the space of physical quantum position states. The product in this setting is the Kronecker (tensor) product. The conditional shift operator for the quantum walk on the line is given by

i.e. the particle jumps right if it has spin up and left if it has spin down. Explicitly, the conditional shift operator acts on product states according to

If we first rotate the spin with some unitary transformation and then apply , we get a non-trivial quantum motion on . A popular choice for such a transformation is the Hadamard gate , which, with respect to the standard z-component spin basis, has matrix representation

When this choice is made for the coin flip operator, the operator itself is called the "Hadamard coin" and the resulting quantum walk is called the "Hadamard walk". If the walker is initialized at the origin and in the spin-up state, a single time step of the Hadamard walk on is