DIMACS Theoretical Computer Science Seminar

Title: Quantum walks and their applications in quantum algorithms

Speaker: Andris Ambainis, IAS

Date: March 29, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


Quantum algorithms provide surprising speedups over classical algorithms, as shown by Shor's quantum algorithm for factoring and Grover's search quantum algorithm.

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.

See Webpage: http://www.cs.rutgers.edu/~muthu/theory.html