Hacker News Reader

Comment by inasio | Hacker News Reader

No. See for example the Grover search algorithm. You can use to find whether an item is inside a list in O(sqrt(n)).

I don't understand what you are saying. The parent comment said that quantum allows a few types of operations to get faster, and your response was "No," followed by a specific algorithm that is faster. Where do you disagree?

I think the point was it doesn't only speed up a small set of linear algebra calculations, but allows other, more complex, operations to be sped up as well.

How big does n need to be before the expected runtime is less than n/2? And at that n, what gate fidelity is necessary to ensure that the answer will usally be correct?

Slightly tangential but how significant is O(sqrt(n)) speed up? Fast algorithms are slightly faster but intractable algorithms are still intractable?

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.

I think the point is it lowers security by a factor of 2 in the exponent. Going from 2^64 to 2^63 lowers the amount of time to bruteforce a key by half.

Reply on news.ycombinator.com