Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121. For more information, contact Diego Dalvit, T-13.

Thursday, March 20, 2008
12:30 PM to 2 PM

Speaker: Andris Ambainis, University of Latvia

Technical Host: Matthew Hastings, T-13

TOPIC: Quantum Random Walks and Quantum Algorithms

Abstract
Quantum walks are quantum counterparts of random walks. In the first part of this talk, we will define quantum walks and describe the basic results about behaviour of quantum walks in one dimension.

In the second part, we will describe some quantum algorithms that are based on quantum walks. Most of those algorithms can be described within one framework, search by a quantum walk. In this framework, we set up a quantum walk on the search space that behaves in one way for the solution elements and in a different way for the non-solution elements. If the quantum walk is set up correctly, it finds a solution element quadratically faster than a conventional random walk. The applications include element distinctness (the problem of finding two equal elements in an array) and search on a k-dimensional grid (k›=2).