[Colloquium] Andris Ambain is talk – Thu rs. 11/20 12:15 at TTI-C

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK

Speaker: Andris Ambainis
UC Berkeley

Speaker’s homepage: http://www.cs.berkeley.edu/~ambainis/

Time: 12:15pm
Date: Thursday, November. 20th, 2003
Place: TTI-C (1427 East 60th Street, Second Floor - Press Building)
*FREE LUNCH PROVIDED*

Title: Quantum Random Walks and Quantum Algorithms

Abstract: Quantum algorithms provide surprising speedups over classical 
algorithms, as shown by Shor's quantum algorithm for factoring and Grover's 
quantum algorithm for solving arbitrary exhaustive search problem. 

In this talk, I will present a new approach to constructing quantum algorithms 
based on quantum walks (quantum counterparts of random walks). I will start 
with a general introduction to quantum computing. After that, I will present 
quantum walks and two new quantum algorithms based on quantum walks: - O(N^
{2/3}) quantum algorithm for element distinctness; - O(\sqrt{N\log N}) quantum 
algorithm for search on 2-dimensional grid.

If you have questions, or would like to meet the speaker, please contact 
Meridel at: 4-9873 or mtrimble at tti-c.org 

For information on future TTI-C talks or events, please go to the TTI-C Events 
page: http://www.tti-c.org/events.shtml