Event Detail

Event Type: 
Probability Seminar
Date/Time: 
Tuesday, November 23, 2010 - 08:00
Location: 
WNGR 201

Speaker Info

Institution: 
Department of Physics, Oregon State University
Abstract: 

We have recently constructed a framework for quantum walks, based on classical walks with memory. This framework reproduces known walks, while it can be used to build walks in systems that are difficult for current approaches. As our first example of its utility, we study a symmetric discrete quantum walk on the infinite binary tree. For a walk starting from a pure state at a given level in the tree we compute the amplitude at the root, as a function of time and starting level. The result is strikingly different from the classical case, as its amplitude spans an order of magnitude, with a power law tail, while the classical one decays exponentially. (For example, for a delayed walk this property yields a polynomial vs. exponential speed up over the classical walk, in delay time.) The breadth of the probability peak indicates that any restriction of the extent of the tree, such as a matching tree, sinks or boundaries, would likely yield algorithms superior to classical. The calculation utilizes a variety of analytical techniques (memoried stochastic processes, combinatorics and path counting, transforms, steepest descent, orthogonal polynomials). This study also brings up interesting general questions about quantum processes on such structures. This talk is based on the joint work with Ian Milligan, Dan Rockwell, Robert M. Burton, Thinh Nguyen and Yevgeniy Kovchegov.