3 ms·
Going a little further: For a very select set of problems (factoring and discrete log), quantum computers are exponentially faster than classical computers. Fo
by justinpombrio 10y ago
Going a little further:
For a very select set of problems (factoring and discrete log), quantum computers are exponentially faster than classical computers. For a few (including np-complete problems), they are quadratically faster. For everything else, they're no faster. (When I say "faster", I really mean the runtime of the best known quantum algorithms is better.)
For the forseeable future, quantum computers will be much smaller than classical computers -- the article is about Google building a 49 bit QC and how that would be a breakthrough. So for the forseeable future, they'll be separate components, used for special cases.
- lvh 10y agoA little further: factoring and discrete log aren't a complete set (also, that depends on algorithm development). There are a few academic problems that are also exponentially faster, and, more generally to factoring and discrete log: hidden subgroup problems (which are what killed non-supersingular isogeny Diffie-Hellman as a post-quantum key exchange).