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
Speaker: Andris Ambainis, University of Latvia
Technical Host: Matthew Hastings, T-13
TOPIC: Quantum Random Walks and Quantum Algorithms
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).