kernal42 t1_j2hjf1w wrote on January 1, 2023 at 9:35 AM

Consider searching for an item in an unsorted list of length N. There's no classical algorithm that lets you find your item in fewer than N/2 queries, on average. This probably makes sense naively.

Grover's algorithm, a quantum computer algorithm, can find your item in sqrt(N) queries.

This seems impossible, but it works because quantum computing Is fucking magic.

Edit: had algorithm name wrong.

kernal42 t1_j2hk0s2 wrote on January 1, 2023 at 9:45 AM

To add, more seriously, there are other quantum algorithms that would revolutionize (or disrupt) our lives as we know them. The most obvious example is Shor's algorithm which, as Grover's above, can factorize numbers more efficiently than we know how to with classical computers. This matters because a majority of public-key encryption algorithms rely on the difficulty for factorization of large numbers. If/when someone figures out how to build a large enough quantum computer, all messages sent with this encryption (future or past) will be trivially decrypted. This breaks so much.

NB we should all be using elliptic curve public key cryptography because there's no known quantum algorithm to break it (yet?).

Cryptizard t1_j2hzmlw wrote on January 1, 2023 at 1:31 PM

That’s not really how Grover’s algorithm works. It can find the correct preimage of a function with only O(sqrt(N)) calls to the function. It can’t find things in a list in less than O(N) time because it would take that long just to read the list elements into registers.