One-dimensional quantum walks

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 ob- served. For example, when unrestricted in either direction, the Hadamard walk has position that is nearly uniformly distributed in the range [-t/√2, t/√2] after t steps, which is in sharp contrast to the classical random walk, which has distance O(√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/π, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/√2 in the limit. In the classical case both values are 1.