Disclaimer: I do not know much about quantum computation, but got interested in it only very recently. I'll give you my understanding, take it with a grain of salt.
AFAIU, Grover's algorithm is not really an algorithm of search of unstructured data, like phone book, but rather a quantum algorithm for inverting a function. The way it is related to search is that you have to have a computable function f such that f(x)=1 if 'x' is one of the million 'boxes' and f(x)=0 otherwise. Your goal is to find that one 'x' (assumption being, of course, is that 'f' is not easily inversible).
How would traditional computer solve the problem - by going through all x's and once f(x)=1, you have your x.
The power of quantum computer is that the state of the quantum computer is the quantum superposition of many classic states. As such quantum computer may perform a computation of 'f' at the superposition of many 'x's at one and get a superposition of function results (that can be measured with a certain degree of uncertainty)
The algorithm essentially goes through superpositions narrowing sets of possible candidate x's pretty fast. Algorithm is inherently probabilistic but the point is that you can converge to x that is your correct x with a high degree of certainty in a (relatively) small amount of steps.
If anyone has more qualified explanation to offer I will be happy to stand corrected.
"AFAIU, Grover's algorithm is not really an algorithm of search of unstructured data, like phone book, but rather a quantum algorithm for inverting a function."
Grover's search algorithm works both for inverting a function and for database search. But if you want to use it for database search, then your database needs to be accessible in coherent superposition, i.e., in some sort of "quantum RAM." For many problems, this probably does not make sense.
AFAIU, Grover's algorithm is not really an algorithm of search of unstructured data, like phone book, but rather a quantum algorithm for inverting a function. The way it is related to search is that you have to have a computable function f such that f(x)=1 if 'x' is one of the million 'boxes' and f(x)=0 otherwise. Your goal is to find that one 'x' (assumption being, of course, is that 'f' is not easily inversible).
How would traditional computer solve the problem - by going through all x's and once f(x)=1, you have your x.
The power of quantum computer is that the state of the quantum computer is the quantum superposition of many classic states. As such quantum computer may perform a computation of 'f' at the superposition of many 'x's at one and get a superposition of function results (that can be measured with a certain degree of uncertainty)
The algorithm essentially goes through superpositions narrowing sets of possible candidate x's pretty fast. Algorithm is inherently probabilistic but the point is that you can converge to x that is your correct x with a high degree of certainty in a (relatively) small amount of steps.
If anyone has more qualified explanation to offer I will be happy to stand corrected.