Measures of quantum computing speedup
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\"odinger 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 …