Quantum walk

Quantum walks were first proposed by physicist Richard Feynman and are, in terms of probability, the opposite of a random walk. A random walk might be modeled by a person flipping a coin, and for each flip he steps left for heads and right for tails. In this case, his most probable location is the center, with the probability distribution tapering off in either direction. A quantum walk involves the use of internal states and superpositions, and results in the hypothetical person "exploring" every possible position simultaneously.

When a quantum walker flips a coin, it directs him to move one way, but he maintains an "internal state" that moves the other way, making him a superposition of both directions of movement. During a quantum walk, as the quantum object takes more steps, it becomes "delocalized" over all available positions, as if its presence is blurred.

A second feature of quantum walking is matter-wave interference, as when the person flips heads and next flips tails. The second step makes the new superposition overlap the old one, and the new superposition can either amplify the old position or remove it. After all this occurs and the desired number of steps have been taken, an attempted observation will collapse the superposition and "resolve" the object to a single position.

As previously mentioned, a random walk's probability distribution has a single peak tapering off in either direction. A quantum walk's probability distribution generally has two peaks placed evenly on either side of the starting position. However, this distribution can vary depending on the initial internal state of the particle doing the walking, which can cause the final position to strongly favor one side or the other.

in Ars Technica