Quantum random walk

Quantum random walks are a mathematical model for quantum mechanical systems that correspond to classical random walks under the process of continuous measurement, and as a source of algorithms for quantum computing. They are distinguished from classical walks by the variance of their probability distribution often increasing much faster and by the presence of quantum interference.

Definition

A quantum random walk in discrete time starts with:

* $n$ x $n$ unitary matrix
* $n$ predefined chiralities (step sizes and directions)
* starting location
* starting chirality

The random walk can then give a probability distribution of where a particle could be after any number of timesteps. The modeling of each timestep can be broken into two parts. First, the unitary matrix changes the chirality of the particle, splitting it into several particles each with new amplitudes. Second, these new particles move based on their new chiralities. This is a quantum random walk because after several timesteps, the amplitudes of particles may interfere with each other because the amplitudes may be either negative or positive. To find the probability of a particle being at a given location after a given number of steps, sum the squares of the amplitudes of all particles at that location and time.

History and applications

Most of the literature on this phenomenon is recent (since 2000) and only a small portion of that is mathematically rigorous. In 2001, A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous wrote a benchmark paper on one-dimensional QRWs, the proofs of which are still referenced in almost all of today's QRW papers. Today, researchers are examining the possibilities of analyzing these QRWs with generating functions, looking at applications in physics and computer science, and examining higher dimension walks. As discussed in the above paper, “quantum random walks have the potential to offer new tools for quantum algorithms”. Although much more research must be done on the foundations of quantum random walks, the potential for its application is already becoming popular. For example, network routing, search algorithm, and element distinctness are just three arising applications for this remarkable concept.

One-dimensional QRWs

A one-dimensional QRW models the movement of a particle along the number line. Each chirality encodes one choice for how far right or left the particle can move. A particle starts at a certain location, with an amplitude of 1 and a set chirality. During the first step, the unitary matrix splits this particle into n different particles based on the unitary matrix and the original chirality (see diagram below). All of the particles are then moved according to their chiralities. During all future timesteps, the unitary matrix acts upon all of the particles, creating an ever increasing number of particle probabilities. Because amplitudes are allowed to be negative, particles can interfere with each other during the walk. By squaring the amplitudes of all of the particles, and adding the squares of those particles in the same location, the probability distribution of the particles location after $t$ steps can be found. A picture of one such probability distribution is shown to the right.

Higher dimensioned QRWs

For two-dimensional QRW's, a degree of freedom needs to be added both to the location of particles and the chiralities, in order to describe how the particle moves in the new dimension. The unitary matrix still describes how a particle of each chirality breaks down into particles with the other chiralities. To plot a two-dimensional probability distribution, a density plot is used. On the example to the right, the darker sections represent higher probabilities of the particle being at the given location.

External links

* [http://www.math.upenn.edu/~pemantle/Summer2007/First_Page.html UPenn QRW Research Page]