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