News for hackers. Stuff that matters.
Re:Unveiling our new Quantum AI campus by inasio on Tuesday May 18, 2021 @05:46PM (#27201661)
No. See for example the Grover search algorithm. You can use to find whether an item is inside a list in O(sqrt(n)).
Re:Unveiling our new Quantum AI campus by spxtr on Tuesday May 18, 2021 @06:07PM (#27201913)
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?
Re:Unveiling our new Quantum AI campus by BobbyJo on Wednesday May 19, 2021 @12:07AM (#27204443)
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.
Re:Unveiling our new Quantum AI campus by klyrs on Tuesday May 18, 2021 @07:06PM (#27202457)
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?
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?
Re:Unveiling our new Quantum AI campus by eximius on Tuesday May 18, 2021 @09:14PM (#27203452)
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.)

Re:Unveiling our new Quantum AI campus by bawolff on Wednesday May 19, 2021 @03:35AM (#27205670)
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.

Re:Unveiling our new Quantum AI campus by haecceity on Wednesday May 19, 2021 @03:35PM (#27213382)
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.