Hi Everyone, Next Thursday at 2:30pm in the Division Room, Professor Joe Traub from Columbia University will be visiting us. He'll present the following talk at group meeting: 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. -- Ryan Babbush | PhD Student in Physics (949) 331-3943 | babbush(a)fas.harvard.edu Harvard University | Aspuru-Guzik Group 12 Oxford Street | Cambridge, MA 02138 _______________________________________________ Aspuru-meetings-list mailing list Aspuru-meetings-list(a)lists.fas.harvard.edu https://lists.fas.harvard.edu/mailman/listinfo/aspuru-meetings-list