[QIP-Sem] MIT Quantum Information Processing Seminar Announcement

[QIP-Sem Mailing List]

This week's MIT QIP seminar will take place on Monday, March 8th at 
16:00 in 4-270, and features:


Quantum Walk Algorithms

by Andris Ambainis (U.C. Berkeley and the Inst. for Advanced Studies, 
Princeton)

ABSTRACT

I will present two new quantum algorithms based on quantum walks:
	- an O(N^{2/3}) query algorithm for element distinctness (the 
problem of finding two equal elements among N given elements).
	- an O(N^{1/2}\log N) step quantum algorithm for finding a 
marked item on 2-dimensional grid.
Both algorithms are based on the same general technique. I will also 
describe this technique and show how to decompose it into a sequence 
of steps which can then be applied to other problems.
The second algorithm is a joint work with Julia Kempe and Alexander Rivosh.


Next week: Michele Mosca (Univ. of Waterloo).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.mit.edu/pipermail/qip-sem/attachments/20040307/236588cb/attachment.htm