Quantum Random Walks: 2007 Summer Research Group Homepage
Combinatorics of quantum random walks on integer lattices in one or more dimensions
Project Title: Quantum Random Walks
Description: The goal of this project is to improve our understanding
of quantum random walks. These are relatively simple quantum mechanical
models in which a single particle moves on a lattice while its momentum
at each time step is altered by application of a fixed unitary operator.
Unlike the classical random walk, which spreads out diffusively (after
time n the region in which the particle is likely to be found has
diameter sqrt(n)), the quantum random walk spreads out linearly,
often with strange looking interference patterns, such as in the
illustration on the left-hand side of this website.
Most of the literature on this phenomenon is recent (since 2000)
and only a small portion of that is mathematically rigorous.
Our project focuses on obtaining mathematically rigorous analyses
of the behavior of quantum random walks via analyses of generating
functions. A d-dimensional quantum random walk has an easily
obtained generating function, which is a rational function of
d spatial variables and one time variable.
Our activity this summer will consist of several phases. In the
first phase, the interns and graduate students will familiarize
themselves with the literature on QRW and the literature on
multivariate generating function asymptotics. In the second phase,
we will build a library of QRW examples. Each example will contain
a specification of the QRW, its generating function, a picture of
the probability distribution at a time sufficiently large for
asymptotic behavior to be visible, an algebraic analysis of the
relevant features of the generating function, and a picture of
the predicted re-scaled asymptotic probabilities. In the last phase,
we will produce formulae for the regions of nonexponential decay and
asymptotic probabilities within this region. We will also state and
try to prove conjectures about the classification of these shapes,
their generic behavior, behavior near the boundary, and so forth.