Quantum Random Walks on the integer lattice via generating functions.

We analyze several families of one and two-dimensional nearest neighbor Quantum Random Walks. Using a multivariate generating function analysis we give a simplified proof of a known phenomenon for two-chirality walks on the line, namely that the walk has linear speed rather than the diffusive behavior observed in classical random walks. We also demonstrate Airy phenomena between the regions of polynomial and exponential decay. For a three-chirality walk on the line we demonstrate similar behavior, with the addition of a bound state, in which the probability of finding the particle at the origin does not go to zero with time. For each of these walks on the line we obtain exact formulae for the leading asymptotic term of the wave function and the location probabilities. Analyzing two-dimensional walks we again find a region of polynomial decay which grows linearly with time. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. We close with preliminary work concerning walks in higher dimensions.