Measures of quantum computing speedup
Anargyros Papageorgiou, Joseph F. Traub · Physical Review A · 2013
We introduce the concept of strong quantum speedup. We prove that approximating the ground-state energy of an instance of the time-independent Schr\"odinger 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.