Re:Factoring may be easier than we think (2016)
by wbl on Sunday June 30, 2019 @11:56AM
(#20318846)
That's true but Grover search shows that quantum computers can give big speedups so I don't know why I would believe BPP=BQP.
[ Parent
| on HN ]
Re:Factoring may be easier than we think (2016)
by nabla9 on Sunday June 30, 2019 @12:54PM
(#20319108)
Grover's algorithm still takes exponentially many operations to solve a search problem that can be brute-forced in exponentially many steps. Much faster, but still in EXPTIME. No jump from exponential to polynomial complexity class.