Anagyros Papageorgiou, Joseph Traub

Paper #: 13-08-026

We introduce the concept of strong quantum speedup. We prove that approximating the ground state energy of an instance of the time-independent Schrödinger equation, with d degrees of freedom, d large, enjoys strong exponential quantum speedup. It 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 in this paper is to explain this dissonance.