Re:Quantum Factorization of 143 (2011)
by bollu on Wednesday September 16, 2020 @08:02PM
(#24499561)
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.
[ Parent
| on HN ]
Re:Quantum Factorization of 143 (2011)
by anderskaseorg on Wednesday September 16, 2020 @08:14PM
(#24499670)
We 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.