<!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>Next week's MIT QIP seminar will take place on Monday, March 8 at
16:00 in room 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>
<div>I will present two new quantum algorithms based on quantum
walks:</div>
<div><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).</div>
<div><x-tab> </x-tab>- an
O(N^{1/2}\log N) step quantum algorithm for finding a marked item on
2-dimensional grid.</div>
<div>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.<br>
The second algorithm is a joint work with Julia Kempe and Alexander
Rivosh.</div>
<div><br></div>
</body>
</html>