Measures of quantum computing speedup

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 and large $d$, 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.