Quantum Walks

A major aspect of studies of quantum computation is work toward constructing
algorithms that are particularly well suited for a quantum mechanical computer.
An emerging field in this quest is investigation of "quantum walks," which are
applications of ideas of classical random walks to quantum (unitary) processes.
Following the pervasiveness and successes of randomized algorithms across the
board in science, these approaches are expected to bring dramatic algorithmic
improvements to quantum computing.

One of the main generator of ideas, Markov chains, or random walks on graphs,
have had many uses in physics; and "random walks with memory" are models for
a number of phenomena. The topic of this talk is the study of construction
of quantum walks (stochastic quantum evolution) based on classical Markov
processes "with memory."

Since the publication of a few seminal papers in the early 2000s, the field
of quantum walks has been developing, and by now there are examples of even
super-exponential speedups, a range of promising results, a few interesting
algorithms, and a number of noted works regarding physical implementations.
In other words, this is a rapidly developing field, rife with interesting
problems on the intersection of physics, mathematics and computer science.

While original research results will be presented, the true aim of this talk
is to give a flavor of this field of research, having in mind an audience
without previous exposure to even classical random walks. The talk will start
with a very brief overview of the main point of quantum computing, and will
then carefully introduce via examples ideas from random walks. It will be
shown how these are pursued in the context of quantum computing, and our
results will be sketched.