<!doctype html public "-//W3C//DTD W3 HTML//EN">
<html><head><style type="text/css"><!--
blockquote, dl, ul, ol, li { padding-top: 0 ; padding-bottom: 0 }
--></style><title>MIT Quantum Information Processing Seminar
Announcemen</title></head><body>
<div>This week's MIT QIP seminar will take place on Monday, March 8th
at 16:00 in 4-270, and features:</div>
<div><br></div>
<hr>
<div align="center"><font size="+2"><b>Quantum Walk
Algorithms</b></font></div>
<div align="center"><br></div>
<div align="center"><font size="+1"><i>by</i> Andris Ambainis (<i>U.C.
Berkeley</i> and the<i> Inst. for Advanced Studies,
Princeton</i>)</font></div>
<div align="center"><br></div>
<div align="center"><u>ABSTRACT</u></div>
<div><br></div>
<blockquote>I will present two new quantum algorithms based on quantum
walks:</blockquote>
<blockquote><x-tab>
</x-tab>- an O(N^{2/3}) query algorithm for element distinctness (the
problem of finding two equal elements among N given
elements).</blockquote>
<blockquote><x-tab>
</x-tab>- an O(N^{1/2}\log N) step quantum algorithm for finding a
marked item on 2-dimensional grid.</blockquote>
<blockquote>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.</blockquote>
<blockquote>The second algorithm is a joint work with Julia Kempe and
Alexander Rivosh.</blockquote>
<blockquote><br></blockquote>
<hr>
<div>Next week: Michele Mosca (Univ. of Waterloo).</div>
</body>
</html>