Post

A common misconception about quantum computers is that they would solve hard problems by trying all possible solutions in parallel. This vaguely gestures at something true, but the reality is more subtle.

What do they do then? This video builds up to Grover’s algorithm, a general method in quantum computing for finding solutions to any NP problem, i.e., anything where you have a quick way to verify solutions, even if finding them in the first place may be hard.

As a generic stand-in for the kind of problem it solves, suppose you have a function acting on {1, ..., N} which returns True on one and only one value in this set. If all you can do with this function is try it out on numbers, then it takes an average of (1/2)N steps to find the answer.

30/4/25, 12:51 pm0 reposts16 likes

If you translate this setup into a quantum computer (explained in the video), Grover's algorithm offers a "faster" way to do this, in that it's O(√N).

It's known you cannot do better than O(√N), which is certainly not as earth-shattering as an exponential speed-up would be, and questionably useful given the enormous overheads of quantum computing. Nonetheless, it's thought-provoking that such a thing is possible!

Rochelle

@uberwensch.bsky.social