<!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
Reminder</title></head><body>
<div>Next week's MIT QIP seminar will take place as usual on Monday,
the Ides of March at 16:00 in 4-237, and features:</div>
<div><br></div>
<hr>
<div align="center"><font size="+2"><b>Quantum Search on Bounded-Error
Inputs</b></font></div>
<div align="center"><br></div>
<div align="center"><font size="+1"><i>by</i> Prof. Michele Mosca
(<i>Inst. for Quantum Computing, Univ. of Waterloo</i> and<i>
Perimeter Inst. for Theoretical Physics</i>)</font></div>
<div align="center"><br></div>
<div align="center"><u>ABSTRACT</u></div>
<div><br></div>
<blockquote>Suppose we have<i> n</i> algorithms, quantum or classical,
each computing some bit-value with<u> bounded error probability</u>.
We describe a quantum algorithm that uses<i> O</i>(ˆ<i>n</i>)
repetitions of the base algorithms and with high probability finds the
index of a 1-bit among these<i> n</i> bits (if there is such an
index). This shows that it is not necessary to first significantly
reduce the error probability in the base algorithms to<i>
O</i>(1/poly(<i>n</i>)) (which would require
$<i>O</i>(ˆ<i>n</i>/log<i> n</i>)$ repetitions in total). Our
technique is a recursive interleaving of amplitude amplification and
error-reduction, and may be of more general interest. Essentially, it
shows that quantum amplitude amplification can be made to work also
with a<u> bounded-error</u> verifier.</blockquote>
<div><br></div>
<div align="right">(Joint work with Peter Hoyer and Ronald de
Wolf)</div>
<div><br></div>
<div><br></div>
<hr>
<div>No seminar next week due to Spring Break.</div>
</body>
</html>