### 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

Abstract:
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