Abstract

We define and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard walk. Several striking differences between the quantum and classical cases are observed. For example, when unrestricted in either direction, the Hadamard walk has position that is nearly uniformly distributed in the range [-t/\sqrt 2, t/\sqrt 2] after t steps, which is in sharp contrast to the classical random walk, which has distance O(\sqrt t) from the origin with high probability. With an absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/&pgr, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/\sqrt 2 in the limit. In the classical case both values are 1.