Grover's algorithm

Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just ${\displaystyle O({\sqrt {N}})}$ evaluations of the function, where N is the size of the function's domain. It was devised by Lov Grover in 1996.

The analogous problem in classical computation cannot be solved in fewer than ${\displaystyle O(N)}$ evaluations (because, in the worst case, the N-th member of the domain might be the correct member). At roughly the same time that Grover published his algorithm, Bennett, Bernstein, Brassard, and Vazirani proved that no quantum solution to the problem can evaluate the function fewer than ${\displaystyle O({\sqrt {N}})}$ times, so Grover's algorithm is asymptotically optimal.

...
Wikipedia