3 ms·
Grover's search offers quadratic (polynomial) speedup, not exponential. As OP states, adiabatic does not provide for the theoretical possible exponential speedu
by bollu 6y ago
Grover's search offers quadratic (polynomial) speedup, not exponential. As OP states, adiabatic does not provide for the theoretical possible exponential speedup, assuming the hypothetical relations of complexity classes P != (NP = BQP) holds. That is: P and NP are different, so there are "hard exponential problems" like 3-SAT. Also, NP = BQP, so quantum computers can solve these hard problems.
- anderskaseorg 6y agoWe have no evidence that factoring is NP-hard, and some evidence that it probably isn’t: the best known classical algorithms for factoring are much faster than those for NP-complete problems. We have no idea whether NP = BQP, or indeed whether either is contained in the other.
- bollu 6y agoYes, which is why I phrased all of this as "hypothetical relations ..."