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.

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

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.

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).