Hi Everyone,
This is a reminder that at 2:30 we will meet in the Division room for
Professor Joe Traub's talk:
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.
_______________________________________________
Aspuru-meetings-list mailing list
Aspuru-meetings-list(a)lists.fas.harvard.edu
https://lists.fas.harvard.edu/mailman/listinfo/aspuru-meetings-list