4 ms·
Almost certainly the latter. QC is very good at highly specific jobs, like factoring or searching. Similarly to GPUs, getting the data from the CPU to the GPU i
by lvh 10y ago
Almost certainly the latter. QC is very good at highly specific jobs, like factoring or searching. Similarly to GPUs, getting the data from the CPU to the GPU is costly. For now and presumably for a very long time, QC has that problem but way worse. (And it wouldn't give you speed ups yet even if the cost was free -- but Martinis asserts that won't take long.)
- justinpombrio 10y agoGoing 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).