One-dimensional quantum walks

We define and analyze quantum computational variants of walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random , which we call the Hadamard walk. Several striking between the quantum and classical cases are ob- served. For example, when unrestricted in either direction, Hadamard walk has position that is nearly uniformly in the range [-t/√2, t/√2] after t steps, which in sharp contrast to the classical random walk, which has O(√t) from the origin with high probability. With 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.