Lab Home | Phone | Search
	Center for Nonlinear Studies
	Home  ▶ People   Current   Executive Committee   Postdocs   Visitors   Students   Research   Publications  ▶ Conferences   Workshops   Sponsorship  ▶ Talks   Seminars   Postdoc Seminars Archive   Quantum Lunch   Quantum Lunch Archive   P/T Colloquia   Archive   Ulam Scholar     Postdoc Nominations  ▶ Student Requests   Student Program  ▶ Visitor Requests   Description   Past Visitors  ▶ Services   General     History of CNLS     Maps, Directions   CNLS Office   T-Division   LANL				Thursday, July 26, 201212:30 PM - 2:00 PMT-DO Conference Room Bldg 123, Room 121 Quantum Lunch Algorithms and Complexity for Quantum Computing Joseph TraubCOMPUTER SCIENCE DEPARTMENT COLUMBIA UNIVERSITY AND EXTERNAL PROFESSOR, SANTA FE INSTITUTE Are quantum computers more powerful than classical computers? To answer this question one must know the classical computational complexity. What is it about the problems of quantum chemistry and quantum physics that enables us to get lower bounds on the classical complexity? We also introduce a new classification of quantum speedups. 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 whose cost is linear in p. We discuss whether this exponential separation proves that quantum computers are exponentially more powerful than classical computers. We end with a selection of research directions and where to learn more. Host: Rolando Somma, T-4, somma@lanl.gov