0
$\begingroup$

I read somewhere on internet that brute-forcing a hash on classical computer will take time proportional to the length of data. But somehow if one have possible inputs used, using Grover's algorithm, one can reduce time significantly. So, is this statement true ? If yes how Grover's algorithm do that and it reduces the brute-force time by how much.

$\endgroup$
0
2
$\begingroup$

Yes, this statement is true. If there are $N$ possible items to check, the classical brute force method takes time $O(N)$. Grover's search only takes time $O(\sqrt{N}$). More precisely, if you want to have a probability of at least $1-1/N$, the classical algorithm has to check $N$ possibilities. The quantum algorithm has to perform $$\left\lfloor\frac{\pi}{4\arcsin(1/\sqrt{N})}\right\rfloor$$ checks. Whether the quantum checks take the same length of time as the classical checks, in order to make a fair "real world" comparison is not usually considered; it's just done by counting the number of checks (often described as "calls to the oracle").

How is another question entirely - unless you're happy with the answer "mysterious quantum mumbo-jumbo", there's quite a lot of prerequisite studying to get you to a place where you can understand the answer.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.