Joseph F. Traub, Columbia University
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.