Re:Unveiling our new Quantum AI campus
by haecceity on Tuesday May 18, 2021 @07:30PM
(#27202668)
Slightly tangential but how significant is O(sqrt(n)) speed up? Fast algorithms are slightly faster but intractable algorithms are still intractable?
[ Parent
| on HN ]
It makes memory, not compute, the limit.
It halves the exponent on the number of operations. 2^128 - reasonably secure by todays standards! 2^64 - horribly insecure.
(CAVEAT: where the speedup is applicable, which is often hard.)
2^64 is hardly horribly insecure. Its on the edge of what a gigantic compute cluster can do. So its not secure, but hardly horribly insecure. Especially even if you can get a quantum computter working, its not going to be on the same level of operations that a million dollars in AWS credits will get you. At least not for a very long time.
Besides,in most places where that is an issue, its trivial to switch to 256bit algorithms
> (CAVEAT: where the speedup is applicable, which is often hard.)
Grover's algorithm has pretty wide applicability. Its the exponential speed ups like shor's algorithm that have super limited applicability.