[QIP-Sem] MIT Quantum Information Processing Seminar Announcement

[QIP-Sem Mailing List]

Next week's MIT QIP seminar will take place on Monday, Mar. 15 at 
16:00 in 4-237, and features:


Quantum Search on Bounded-Error Inputs

by Prof. Michele Mosca (Inst. for Quantum Computing, Univ. of 
Waterloo and Perimeter Inst. for Theoretical Physics)

ABSTRACT

Suppose we have n algorithms, quantum or classical, each computing 
some bit-value with bounded error probability. We describe a quantum 
algorithm that uses O(ˆn) repetitions of the base algorithms and with 
high probability finds the index of a 1-bit among these n 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 
O(1/poly(n)) (which would require $O(ˆn/log n)$ 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 bounded-error verifier.

(Joint work with Peter Hoyer and Ronald de Wolf)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.mit.edu/pipermail/qip-sem/attachments/20040310/579993e6/attachment.htm