Hi Quanta
On Friday we will have our group meeting at 11:00 in 6-310 and Sean will give us a
presentation on his work. At 1:30 we have our seminar in 6C-442 with Joe Traub. Abstract
below. See you then.
Eddie
ALGORITHMS AND COMPLEXITY FOR QUANTUM
COMPUTING
J.F. TRAUB
COMPUTER SCIENCE DEPARTMENT
COLUMBIA UNIVERSITY
(ON SABBATICAL AT HARVARD)
ABSTRACT
We introduce the notion of strong quantum speedup. To compute this speedup one must
know the classical computational complexity. What is it about the problems of quantum
physics and quantum chemistry that enable us to get lower bounds on the classical
complexity? We then turn to a particular problem, the ground state of the time-independent
Schroedinger equation for a system of p particles. The classical deterministic complexity
of this problem is exponential in p. We provide an algorithm for solving this problem on a
quantum computer with cost linear in p. Thus this problem can be easily solved on a
quantum computer. Some researchers in discrete complexity theory believe that quantum
computation is not effective for eigenvalue problems. One of our goals is to explain this
dissonance. We do not claim separation of the complexity hierarchy since our complexity
estimates are obtained using specific kinds of oracle calls. We end with a selection of
research directions !
and where to learn more.
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Edward Farhi
Cecil and Ida Green Professor of Physics
Director
Center for Theoretical Physics
Massachusetts Institute of Technology
6-300
Cambridge MA 02139
617 253 4871
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip